c＋＋STL中list介绍，模拟实现和list与vector对比

前言 ：

我们在前几期已经详细介绍了STL中string，vector容器的使用及模拟实现，不难发现，string和vector的结构很相似，他们在物理上都是连续的结构，想访问下一个位置的数据，只需要让相应容器的迭代器自增就可以实现，而我们今天要介绍的list，则无法用这种方法访问下一个位置数据，这也是我们在这一期需要解决的问题。

1. list的介绍及使用

1.1list的介绍·

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素）

 **list的结构就是我们在数据结构篇学过的双向带头循环链表，以这种结构实现的链表，使用起来比一般的链表更加方便，我们只要得到哨兵位就可以轻松得到链表的其他结点，看上去复杂但是实现起来确实最简单的链表。**

1.2 list的使用

与vector一样，list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。**以下为list中一些常见的重要接口**。

1.2.1 list的构造

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

注意事项：

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

以上就是list中核心的日常使用得比较多的接口，当然，list还有许多接口，在需要使用的时候我们可以通过查看文档来学习各个接口的使用方法，这也是作为程序员的基本的能力之一。

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

错误示范：

void TestListIterator1()
{
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;
}
}

改正：

/ 改正
void TestListIterator()
{
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())
{
l.erase(it++);
// it = l.erase(it);
}
}

2. list的模拟实现

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

list.h :

#pragma once
#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;
template<class Container>
void print_Container( Container& v)
{
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;

}

namespace Myobject
{
    template<class T>
    struct list_node
    {
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;
        list_node(const T& data = T())
            :_data(data)
            , _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;

        }

        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;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }
    };

    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;
        

        list()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0;
        }

        
        iterator begin()
        {
            return _head->_next;
        }

        iterator end()
        {
            return _head;
        }

        void push_back(const T& x)
        {
            //问题
            /*Node* newnode = new Node(x);
            Node* tail = _head->_prev;

            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
            ++_size;*/
            insert(end(), x);
        }

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        void insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);

            newnode->_next = cur;
            cur->_prev = newnode;
            newnode->_prev = prev;
            prev->_next = newnode;
            ++_size;

        }

        void erase(iterator pos)
        {
            assert(pos != end());
            Node* prev = pos._node->_prev;
            Node* next = pos._node->_next;

            prev->_next = next;
            next->_prev = prev;
            delete pos._node;
            --_size;
        }
        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }

        size_t size()
        {
            return _size;
        }

        bool empty()
        {
            return _size == 0;
        }

    private:
        Node* _head;
        size_t _size;
    };

    void test()
    {
        list<int> lt;

        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        lt.push_back(5);
        lt.push_front(0);
        lt.pop_back();

        

        struct AA
        {
            int a1 = 1;
            int a2 = 2;
        };

        list<AA> alt;
        alt.push_back(AA());
        alt.push_back(AA());
        alt.push_back(AA());
        alt.push_back(AA());

        list<AA>::iterator ait = alt.begin();

        while (ait != alt.end())
        {
            cout << ait->a1 << ":" <<ait->a2 << endl;
            ait++;
        }

        print_Container(lt);

    }
}

test.c :

#include"list.h"

int main()
{
    Myobject::test();
    return 0;
}

**3. list与vector的对比 **

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

本章完。