c++ list详解

list

1. list的介绍

list的底层结构是带头双向循环链表，因为该结构的特性，使list可以在常数范围内在任意位置进行插入和删除，但是不支持[]随机访问。

2. list常见重要的接口

2.1 构造函数

默认构造list()构造n个vallist（n,val_type = val_type()）拷贝构造list（const list& l）迭代区间构造list （InputIterator first,InputIterator last）
代码演示

intmain(){//n个val
    list<int>li(5,1);//拷贝构造
    list<int>li1(li);//迭代器区间构造
    list<int>li2(li.begin(), li.end());return0;}

2.2 iterator

2.2.1 理解

vector的iterator可以简单的理解成指针，事实上底层也是对指针typedef了，但是list的iterator不是这样，因为vector的空间是连续的，对iterator进行++或者–的操作是很自然的指向下一个或上一个元素，但是对于list的空间不是连续的，对list的iterator进行++或–是拿不到相应的元素，所以我们肯定要对++、–等操作符进行重载，但是对于内置类型，进行不了重载的操作，所以底层对该iterator进行了一层封装，变成了一个自定义的类，然后进行运算符重载，就可以得到理想的结果。

//迭代器类template<classT,classRef,classPtr>classListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode =nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}
        Ref operator*(){return _pNode->_data;}
        Ptr operator->(){return&_pNode->_data;}
        Self&operator++(){
            _pNode = _pNode->_next;return*this;}
        Self operator++(int){
            Self tmp(*this);
            _pNode = _pNode->_next;return tmp;}
        Self&operator--(){
            _pNode = _pNode->_pre;return*this;}
        Self&operator--(int){
            Self tmp(*this);
            _pNode = _pNode->_pre;return tmp;}booloperator!=(const Self& l){return _pNode != l._pNode;}booloperator==(const Self& l){return _pNode == l._pNode
        }private:
        PNode _pNode;};

2.2.2 使用

begin()返回第一个元素的迭代器end()返回最后一个元素的下一个元素的迭代器rebegin()返回end位置的反向迭代器rend（）返回begin位置
代码演示

intmain(){//n个val
    list<int>li(5,1);
    list<int>::iterator it = li.begin();while(it != li.end()){
        cout <<*it << endl;
        it++;}return0;}

3. 容量和大小

判断list是否为空empty（）返回list有效节点个数size（）
代码演示

intmain(){//n个val
    list<int>li(5,1);if(li.empty())
        cout <<"list is empty"<< endl;else
        cout << li.size()<< endl;return0;}

4. 查找元素

获取第一个元素front（）获取最后一个元素back（）
代码演示

intmain(){//n个val
    list<int> li;
    li.push_back(1);
    li.push_back(2);
    li.push_back(3);
    li.push_back(4);
    li.push_back(5);
    cout << li.front()<< endl;
    cout << li.back()<< endl;return0;}

5. 增、删、改

push_front(const val_type& x)头插pop_front头删push_back(const val_type& x)尾插pop_back()尾删insert(iterator pos,const val_type& x)在pos位置前面插入元素erase(iterator pos)删除pos位置元素swap（const list& l）交换两个listclear（）清空有效节点
代码演示

intmain(){
    list<int> li;
    li.push_back(1);
    li.push_back(2);
    li.push_back(3);
    li.push_back(4);
    li.push_back(5);
    li.push_front(6);

    li.pop_front();
    li.pop_back();

    list<int>::iterator it = li.begin();
    it++;
    li.insert(it,7);
    it++;
    li.erase(it);

    list<int>li2(5,1);
    li2.swap(li);
    li2.clear();return0;}

3. 迭代器失效

前面介绍vector容器的时候说过，vector在进行插入删除的时候很容易导致迭代器失效，但list只有在删除的时候会发生迭代器失效，而且不会影响其它的迭代器。

voidTestListIterator1(){int array[]={1,2,3,4,5,6,7,8,9,0};
        list<int>l(array, array +sizeof(array)/sizeof(array[0]));auto it = l.begin();while(it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
            其赋值
                l.erase(it);++it;}}

4. vector和list对比

1. 底层结构：vector是动态顺序表，连续空间，list是带头结点的双向循环链表
2. 访问：vector支持[]随机访问，list只能遍历访问
3. 插入删除：vector尾插尾删效率高，但头插头删效率低，所以没该接口，list任意位置插入效率都高。
4. 空间利用率：vector底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据，list底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低。
5. 迭代器：vector为原生指针，list进行了封装。
6. 迭代器失效：vector插入、删除都会导致迭代器失效，list只有在删除时会导致当前迭代器失效。
7. 使用场景：vector适用不关心插入和删除效率，支持随机访问，list适用大量插入和删除操作，不关心随机访问的场景。