C++ list 容器详解：介绍使用与模拟实现

【补充 1】——push_back 类和 emplace_back 类的区别

（这里涉及到前面几节所讲的拷贝构造，隐式类型转换，直接构造啥的，要是忘记了就复习回来啦，我爱 C++）

int main() { 
    list<Pos> lt; 
    Pos p1(1, 1); //构造 + 拷贝构造 
    lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行 push_back 
    lt.push_back(Pos(2, 2));//匿名对象 
    lt.push_back({ 2,2 });//隐式类型转换 
    lt.emplace_back(p1);//那是一个模版，传一个 Pos 类型的对象，模版参数推出形参的类型为 Pos 
    lt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back 的模版参数也可以推导出为 Pos 类型 
    //lt.emplace_back({ 2,2 }); //直接构造 
    lt.emplace_back(3, 3);//但是可以支持这样玩，直接将初始化 pos 的值给它传过去 
    return 0; 
}

• 下面的拷贝构造，是将形参的 pos 拷贝构造到链表中的节点里面
• lt.push_back({1,1});//本质是隐式类型转换—>这里也是构造 + 拷贝构造（隐式类型转换，实参传给形参，先用 (1,1) 构造一个临时对象，形参引用的是临时对象，这种场景下就解释了为什么形参的部分要加上 const，因为它引用的临时对象具有常性！）
• lt.emplace_back(1, 1);//不仅仅可以传 pos 类型的对象，也可以传构造链表里面 pos 的参数直接最后去构造 pos，所以形参也叫可变模版参数

所以相比于 push_back，emplace_back 的高效之处仅在于直接构造的那种情况！

【补充 2】vector 和 list 使用 sort 的区别

int main() { 
    list<int> lt1 = { -1,90,100,-8,34 }; 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    //排序 sort，默认是升序，less 
    lt1.sort(); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    //排降序 > greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>()); 
    lt1.sort(gt); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    //对于 vector，算法库里面有现成的 sort，现在试用一下 
    vector<int> v1 = { 1,3,-2,90,9 }; 
    for (auto e : v1) { cout << e << " "; } 
    cout << endl; 
    //默认是升序 
    //sort(v1.begin(), v1.end()); 
    sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序 
    for (auto e : v1) { cout << e << " "; } 
    cout << endl; 
    //但是 list 就不可以使用算法库里面的 sort，只能用 STL 里面的 sort 
    //sort(lt1.begin(), lt2.end(), greater<int>()); 
    return 0; 
}

运行结果见下：

（vector 的 sort 底层是递归，算法库里面的 sort 底层是归并）

【vector 下和 list 下 sort 性能的区别—Release】

下面是在 Release 下，对 vector 使用算法库里面的 sort 和 list 使用自己实现的 sort 各自效率的测试

void test_op1() { 
    srand((unsigned int)time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    list<int> lt2; 
    vector<int> v; 
    for (int i = 0; i < N; i++) { 
        auto e = rand() + i; 
        lt1.push_back(e); 
        v.push_back(e); 
    } 
    int begin1 = clock(); 
    //排序，用算法库里面的 sort 给 vector 排序 
    sort(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort();//默认排升序 
    int end2 = clock(); 
    cout << "vector sort:" << end1 - begin1 << endl; 
    cout << "list sort:" << end2 - begin2 << endl; 
} 
void test_op2() { 
    srand((unsigned int)time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    list<int> lt2; 
    for (size_t i = 0; i < N; i++) { 
        auto e = rand(); 
        lt1.push_back(e); 
        lt2.push_back(e); 
    } 
    int begin1 = clock(); 
    //拷贝 vector 
    vector<int> v(lt2.begin(), lt2.end());//用迭代器区间进行构造 
    sort(v.begin(), v.end()); 
    //拷贝回 lt2 
    lt2.assign(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort(); 
    int end2 = clock(); 
    cout << "vector sort(copy):" << end1 - begin1 << endl; 
    cout << "list sort:" << end2 - begin2 << endl; 
} 
int main() { 
    test_op1(); 
    test_op2(); 
    return 0; 
}

运行结果如下：显而易见，要排序的话最好使用 vector，vector 排序的效率更高！

list 中还有一些操作，需要用到时大家可参阅 list 的文档说明。

1.3 关于上面 list 的使用所写的全部代码

#include<iostream> 
#include<list> 
#include<vector> 
#include<algorithm> 
using namespace std;

// 示例 1：基础遍历
/*
int main() { 
    list<int> lt1; 
    lt1.push_back(1); 
    lt1.push_back(2); 
    lt1.push_back(3); 
    lt1.push_back(4); 
    lt1.push_back(5); 
    list<int>::iterator it1 = lt1.begin(); 
    while (it1 != lt1.end()) { 
        cout << *it1 << " "; 
        it1++; 
    } 
    cout << endl; 
    list<int> lt2 = { 1,2,3,4,5,6 }; 
    for (auto e : lt2) { 
        cout << e << " "; 
    } 
    cout << endl; 
    return 0; 
}
*/

class Pos { 
    int _row; 
    int _col; 
public: 
    Pos(int row, int col) :_row(row), _col(col) { } 
};

// 示例 2：push_back vs emplace_back
/*
int main() { 
    list<Pos> lt; 
    Pos p1(1, 1); 
    lt.push_back(p1);
    lt.push_back(Pos(2, 2));
    lt.push_back({ 2,2 });
    lt.emplace_back(p1);
    lt.emplace_back(Pos(2,2));
    lt.emplace_back(3, 3);
    return 0; 
}
*/

// 示例 3：erase 与 reverse
/*
int main() { 
    list<int> lt1 = { 1,2,3,4,5 }; 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    int x; 
    cin >> x; 
    auto it = find(lt1.begin(), lt1.end(), x); 
    if (it != lt1.end()) { 
        lt1.erase(it); 
    } 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    //逆置 
    lt1.reverse(); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    return 0; 
}
*/

// 示例 4：splice (LRU 模拟)
/*
int main() { 
    list<int> lt1 = { 1,2,3,4,5,6 }; 
    int x; 
    while (cin >> x) { 
        auto pos = find(lt1.begin(), lt1.end(), x);
        lt1.splice(lt1.begin(), lt1, pos);
        for (auto e : lt1) { cout << e << " "; } 
        cout << endl; 
    } 
    return 0; 
}
*/

// 示例 5：sort 对比
/*
int main() { 
    list<int> lt1 = { -1,90,100,-8,34 }; 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    lt1.sort(); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    greater<int> gt;
    lt1.sort(gt); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    vector<int> v1 = { 1,3,-2,90,9 }; 
    for (auto e : v1) { cout << e << " "; } 
    cout << endl; 
    sort(v1.begin(), v1.end(), greater<int>()); 
    for (auto e : v1) { cout << e << " "; } 
    cout << endl; 
    return 0; 
}
*/

// 示例 6：性能测试
void test_op1() { 
    srand((unsigned int)time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    vector<int> v; 
    for (int i = 0; i < N; i++) { 
        auto e = rand() + i; 
        lt1.push_back(e); 
        v.push_back(e); 
    } 
    int begin1 = clock(); 
    sort(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort(); 
    int end2 = clock(); 
    cout << "vector sort:" << end1 - begin1 << endl; 
    cout << "list sort:" << end2 - begin2 << endl; 
} 
void test_op2() { 
    srand((unsigned int)time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    list<int> lt2; 
    for (size_t i = 0; i < N; i++) { 
        auto e = rand(); 
        lt1.push_back(e); 
        lt2.push_back(e); 
    } 
    int begin1 = clock(); 
    vector<int> v(lt2.begin(), lt2.end()); 
    sort(v.begin(), v.end()); 
    lt2.assign(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort(); 
    int end2 = clock(); 
    cout << "vector sort(copy):" << end1 - begin1 << endl; 
    cout << "list sort:" << end2 - begin2 << endl; 
} 
int main() { 
    test_op1(); 
    test_op2(); 
    return 0; 
}

二、list 模拟实现

const 容器必须使用 const 迭代器进行遍历，const 迭代器不是迭代器本身不能修改而是迭代器指向的内容不能修改

2.1 模拟实现 list

要模拟实现 list，必须要熟悉 list 的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现 list。

list.h

#pragma once 
#include<assert.h> 
namespace bit { 
    // 惯例 
    // 全部都是公有，一般用 struct 
    template<class T> 
    struct list_node { 
        T _data; 
        list_node<T>* _next; 
        list_node<T>* _prev; 
        list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr) { } 
    }; 
    
    template<class T, class Ref, class Ptr> 
    struct list_iterator { 
        typedef list_node<T> Node; 
        typedef list_iterator<T, Ref, Ptr> Self; 
        Node* _node; 
        list_iterator(Node* node) :_node(node) { } 
        Ref operator*() { return _node->_data; } 
        Ptr operator->() { return &_node->_data; } 
        Self& operator++() { _node = _node->_next; return *this; } 
        Self& operator--() { _node = _node->_prev; return *this; } 
        Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } 
        Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } 
        bool operator!=(const Self& s) { return _node != s._node; } 
        bool operator==(const Self& s) { return _node == s._node; } 
    }; 
    
    template<class T> 
    class list { 
        typedef list_node<T> Node; 
    public: 
        typedef list_iterator<T, T&, T*> iterator; 
        typedef list_iterator<T, const T&, const T*> const_iterator; 
        
        iterator begin() { return iterator(_head->_next); } 
        iterator end() { return iterator(_head); } 
        const_iterator begin() const { return const_iterator(_head->_next); } 
        const_iterator end() const { return const_iterator(_head); } 
        
        void empty_init() { 
            _head = new Node(); 
            _head->_next = _head; 
            _head->_prev = _head; 
            _size = 0; 
        } 
        
        list() { empty_init(); } 
        
        list(const list<T>& lt) { 
            empty_init(); 
            for (auto& e : lt) { push_back(e); } 
        } 
        
        list<T>& operator=(list<T> lt) { 
            swap(lt); 
            return *this; 
        } 
        
        ~list() { 
            clear(); 
            delete _head; 
            _head = nullptr; 
        } 
        
        void swap(list<T>& tmp) { 
            std::swap(_head, tmp._head); 
            std::swap(_size, tmp._size); 
        } 
        
        void clear() { 
            auto it = begin(); 
            while (it != end()) { 
                it = erase(it); 
            } 
        } 
        
        list(size_t n, const T& val = T()) { 
            empty_init(); 
            for (size_t i = 0; i < n; i++) { push_back(val); } 
        } 
        
        void push_back(const T& x) { insert(end(), x); } 
        void push_front(const T& x) { insert(begin(), x); } 
        void pop_front() { erase(begin()); } 
        void pop_back() { erase(--end()); } 
        
        iterator insert(iterator pos, const T& val) { 
            Node* cur = pos._node; 
            Node* newnode = new Node(val); 
            Node* prev = cur->_prev; 
            prev->_next = newnode; 
            newnode->_prev = prev; 
            newnode->_next = cur; 
            cur->_prev = newnode; 
            ++_size; 
            return iterator(newnode); 
        } 
        
        iterator erase(iterator pos) { 
            assert(pos != end()); 
            Node* del = pos._node; 
            Node* prev = del->_prev; 
            Node* next = del->_next; 
            prev->_next = next; 
            next->_prev = prev; 
            delete del; 
            --_size; 
            return iterator(next); 
        } 
        
    private: 
        Node* _head; 
        size_t _size; 
    }; 
    
    template <class T> 
    void swap(T& a, T& b) { 
        T c(a); 
        a = b; 
        b = c; 
    } 
    
    template <class T> 
    void swap(list<T>& a, list<T>& b) { 
        a.swap(b); 
    } 
}

运算符重载 -> ,第一个 -> 的结果是 Pos*,第二个是找 Pos 这个结构体里面的_row。

list.cpp

#define _CRT_SECURE_NO_WARNINGS 1 
#include<iostream> 
#include<algorithm> 
#include<list> 
#include<vector> 
using namespace std;

class Pos { 
public: 
    int _row; 
    int _col; 
    Pos(int row = 0, int col = 0) :_row(row), _col(col) { cout << "Pos(int row, int col)" << endl; } 
    Pos(const Pos& p) :_row(p._row), _col(p._col) { cout << "Pos(const Pos& p)" << endl; } 
};

void test_op1() { 
    srand(time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    list<int> lt2; 
    vector<int> v; 
    for (int i = 0; i < N; ++i) { 
        auto e = rand() + i; 
        lt1.push_back(e); 
        v.push_back(e); 
    } 
    int begin1 = clock(); 
    sort(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort(); 
    int end2 = clock(); 
    printf("vector sort:%d\n", end1 - begin1); 
    printf("list sort:%d\n", end2 - begin2); 
} 
void test_op2() { 
    srand(time(0)); 
    const int N = 1000000; 
    list<int> lt1; 
    list<int> lt2; 
    for (int i = 0; i < N; ++i) { 
        auto e = rand(); 
        lt1.push_back(e); 
        lt2.push_back(e); 
    } 
    int begin1 = clock(); 
    vector<int> v(lt2.begin(), lt2.end()); 
    sort(v.begin(), v.end()); 
    lt2.assign(v.begin(), v.end()); 
    int end1 = clock(); 
    int begin2 = clock(); 
    lt1.sort(); 
    int end2 = clock(); 
    printf("list copy vector sort copy list sort:%d\n", end1 - begin1); 
    printf("list sort:%d\n", end2 - begin2); 
}

#include"List.h"

int main() { 
    bit::list<int> lt1; 
    lt1.push_back(1); 
    lt1.push_back(2); 
    lt1.push_back(3); 
    lt1.push_back(4); 
    lt1.push_front(0); 
    lt1.push_front(-1); 
    bit::list<int> lt2(10, 1); 
    int i = 1, j = 2; 
    bit::swap(i, j); 
    bit::swap(lt1, lt2); 
    for (auto e : lt1) { cout << e << " "; } 
    cout << endl; 
    for (auto e : lt2) { cout << e << " "; } 
    cout << endl; 
    return 0; 
}

list 结束！