前言：学习C++的STL，我们不仅仅要求自己能够熟练地使用各种接口，我们还必须要求自己了解一下其底层的实现方法，这样可以帮助我们写出比较高效的代码程序！

⭐在本篇文章中，list的迭代器是重点，它不像string和vector的迭代器一样可以使用原生指针，至于为啥，您可以继续往下看看！

首先是关于list的基本概念：

⭐1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 

⭐2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

⭐3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

⭐4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

⭐5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问,比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

模拟实现list

首先创建节点和list类，以及使用命名空间来防止冲突。

namespace my_list
{//节点templatestruct ListNode{ListNode* _next;ListNode* _prev;T _data;//new node创建节点的时候，要默认构造初始化ListNode(const T& x):_next(nullptr), _prev(nullptr), _data(x){}};//创建list类templateclass list{typedef ListNode Node;public:private:Node* _head;size_t _size;};
}

构造函数

1.无参构造

因为list的一个带头双向循环链表，因此，构造的时候，第一个节点不带值，做头节点，其指针指向自己。在new node初始化的时候，因为T是泛型，如果T是string类等等，需要调用T的默认构造去初始化，T初始化后再传入节点的构造函数，进行节点的初始化。

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

因为后续的接口实现，多处用到list的空初始化，因此，可以按照实现一个函数，专门用来空初始化list对象。

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

2.迭代器区间构造

		//迭代器区间构造template list(InputIterator first, InputIterator last){//创建哨兵位头节点empty_initialize();while (first != last){push_back(*first);++first;}}

3.拷贝构造

传统写法：

先初始化lt2，然后lt1有多少节点，lt2也尾插多少，数据也得一样。这里需要注意两点：

第一点：for循环中，最好使用引用，因为T是泛型，如果T是string类，是vector类，那么在赋值给e的时候，就会不断地进行拷贝。

第二点：auto前加const，是基于实现了const迭代器的情况，如果没有实现，就不能加const。

		//lt2(lt1)list(const list& lt){//先初始化,搞一个哨兵位的头节点empty_initialize();for (const auto& e : lt){push_back(e);}}

现代版本的写法：

现代写法的思路就是找打工人，然后跟打工人交换。因为默认无论如何，即使是空的链表，也会有一个哨兵位的头节点。如果没有这个哨兵位的头节点，在交换之后，tmp会导致野指针问题，在析构的时候会报错！

		void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

		list(const list& lt){//得有一个哨兵位empty_initialize();list tmp(lt.begin(), lt.end());swap(tmp);}

4.赋值

传统写法：

		list& operator=(const list& lt){//防止自己给自己赋值if (this != <){//先清掉原有的节点clear();for (auto& e : lt){push_back(e);}}return *this;}

现代写法：

赋值不同于拷贝，因为this本来就有自己的哨兵位，因此不需要调用empty_initialize();函数。传参并不是引用传参，原有有两个：第一个是最重要的，如果用了引用，就会修改传进来的参数的值。第二个是：lt是局部变量，出来作用域后会析构带走。而传统写法不会对传进来的参数的值进行修改，选择引用是比较好的，可以省掉一次拷贝构造。

		//lt1 = lt2;list& operator=(const list lt){swap(lt);return *this;}

5.析构函数

先将除头节点外的节点全部删掉，最后再单独释放头节点。clear()的实现在后面~

		~list(){clear();delete _head;_head = nullptr;}

新增节点：

1.push_back(const T& x);

尾插很简单，就是修改一下指针而已。

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

2.insert(iterator pos,const T&x);

		iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._pnode;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}

3.push_front(const T& x);

复用insert就好，push_back()其实也可以服用insert。代码里面的begin()和end()是基于迭代器而实现的接口，迭代器的实现，在文章下面点。

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

		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;insert(end(), x);}

删除节点：

1.erase(iterator pos);

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

解决的方法，便是更新pos，返回pos的下一个位置的即可。

		iterator erase(iterator pos){assert(pos != end());Node* prev = pos._pnode->_prev;Node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;--_size;delete pos._pnode;return iterator(next);}

2.头删跟尾删。

服用erase();即可。尾删的时候，因为end()是最后一个数据的下一个位置，因此需要end()减减一下，则需要在迭代器的类域里面实现operator--()的接口。

		//头删void pop_front(){erase(begin());}//尾删void pop_back(){erase(--end());}

3、清空节点

使用迭代器进行删除，erase函数会返回删除的节点的下一个节点！这里需要注意的是，while循环的条件it!=end()，不能改写为it

		void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase会返回下一个节点}}

list迭代器：

迭代器，它是内嵌类型的，即是在某个类里面的。并且它是行为是像指针一样的！在上层中，每种迭代器的使用方法几乎一样，但是其底层实现的方法压根不一样！

如果我们像实现string类和vector类（官方库中不是使用原生指针）一样，直接使用原生指针，是不可以写出我们需要的迭代器的！

而指针重要的两个行为如下：

1.解引用

2.支持++或--

vector或string类的迭代器是可以使用原生指针，因为它们是一段连续的物理空间，不管是解引用还是++/--，都能够保证获取到指定位置的数据或到达指定的位置（因为指针的++，加的是一个对象的大小，T是多大，就+多大，指针就往前走多少步）。

但是对于链表，它的节点的地址是不连续的！此时原生指针（Node*）不能满足迭代器的行为！此时，类的封装的重要性就体现出来了！类的封装+运算符重载闪亮登场！

此时的迭代器，不再是内置类型，而是一个自定义类型，我们一步步往下讲。

初步写法：

我们初步的写法，便是先将++，解引用和判断相等的功能实现。所谓的解引用，就是返回当前节点的值，而++，链表的++，本质就是到下一个节点，那便是next！

注意这里没有写出拷贝构造，意味着当我们使用赋值的时候，是浅拷贝，这也是我们所需要的，因为需要迭代器的对象跟调用迭代器的对象指向同一个节点！这也是不写析构函数的原因，否则会对同一块空间进行两次析构！

	templatestruct __list_iterator{typedef ListNode node;node* _pnode;__list_iterator(node* p):_pnode(p){}//解引用T& operator*(){return _pnode->_data;}//++__list_iterator& operator++(){_pnode = _pnode->_next;return *this;}//--__list_iterator& operator--(){_pnode = _pnode->_prev;return *this;}//！=bool poerator!=(const __list_iterator& it){return _pnode != it._pnode;}};

此时，就可以在list类里面写出迭代器的两个函数：begin和end。需要注意的是，begin的位置，是头节点的下一个位置，因为这是带头链表。end的位置，是最后一个节点的下一个位置，那就是头节点了。

		typedef __list_iterator iterator;iterator begin(){return iterator(_head->_next);//使用匿名对象}iterator end(){//iterator it(_head);//return it;return iterator(_head);}

const 迭代器

const迭代器，只读不写。那么，const迭代器该如何去实现呢？对于const迭代器的写法，会有以下误写！

第一种错写：直接在使用的迭代器前加个const，如下：

这个是我们自己写的，基于普通迭代器，然后使用的时候，加const

这样写是不行的！因为const迭代器中的const是用于保护指向的对象不被修改，迭代器本身可以被修改。因此，上面这种情况，会让迭代器本身，即it不能被修改，如果不能被修改，那么还怎么去访问数据？即迭代器it不能++往后走了！

第二种错写：在普通迭代器的类里面，加上成员函数的const版本：

 这种错误，是建立在第一种错误之上的！如果我们这样子实现const迭代器后，在使用两种迭代器的时候，const迭代器的使用依然是这样子使用：

const list::iterator it = lt.begin();

我承认，此时，const迭代器对象去解引用的时候，确实是会调用const版本的operator*()，而普通迭代器对象解引用的时候，也是去调用普通版本的operator*()。但是，重点是const版本迭代器不能++，即不能往后走！又回到了第一种错误身上！我们的const迭代器，是只读不写，如果不能让const迭代器++往后走，如何去读？难道实现一个const版本的operator++()吗？那么请operator++()这个函数接口，可以去实现const吗？显然是不行的！

正确的写法：

我们可以单独实现一个const版本的迭代器的类，只需要把operator*()变成const版本，然后其它的不变即可，接着begin()和end()也实现一个const版本即可！这样的话就能明确我们写的迭代器是const版本还是普通版本，然后去调用相应的接口函数。

但是捏，这种想法有个很明显的不好——代码冗余！解决办法就是传多个模板参数！

然后在list类里面，分别重命名两种迭代器，这种做法的本质就是复用代码，实际上是两种类！比如T的类型是int，当使用const_iterator,那么T和Ref就会推演成int和const int&，如果是普通迭代器，那么就会推演成int和int&。

	templatestruct __list_iterator{typedef ListNode node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->_data;}T* operator->(){return &_pnode->_data;}//++it  前置++Self& operator++(){_pnode = _pnode->_next;return *this;}//it++  后置++Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}//--it  前置--Self& operator--(){_pnode = _pnode->_prev;return *this;}//--it  后置--Self operator--(){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}};

 那么，此时begin()和end()当然也要重载一份const版本的出来！

		const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

上面代码完善了以下所需的接口。其中的operator->()需要额外说明一下：

调用这个函数，返回的是数据的地址，比如数据是一个日期的数据，那就是返回Date*，但当我们去调用这个函数并且取其数据的时候，按道理来说，因为会有两个箭头：

第一个箭头，表示的是这个数据的的指针，第二个箭头是原生指针，表示的是解引用后的这个数据本身。

it->->year,it->->month,it->->day

但实际上我们在写的时候却不是这样，我们只需要写一个箭头即可，因为编译器为了可读性，做了特殊的处理，省略掉了一个箭头。

如果一个const迭代器对象使用operator->()并且试图对数据进行修改，我们发现确实被修改了，原因是T* operator->()是普通迭代器的版本，因此，我们需要再额外加一个模板参数，去分成const版本和普通版本！

此时，就完成了我们模拟实现list中，迭代器的最终版

	templatestruct __list_iterator{typedef ListNode node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}//++it  前置++Self& operator++(){_pnode = _pnode->_next;return *this;}//it++  后置++Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}//--it  前置--Self& operator--(){_pnode = _pnode->_prev;return *this;}//--it  后置--Self operator--(){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}};

 总结反思

list和vector的对比：

list和vector，说白了，就是链表跟顺序表这两兄弟的对比，这对活宝很幽默，对方的缺点是自身的优点，对方的优点是自身的缺点，有时候我们会突然区分不清他们的优缺点，因此来总结一下下！

vector的优点：

①下标的随机访问

②尾插尾删比list的效率高

③CPU高速缓冲命中率高。

这三点都是结构的优点！

vector的缺点：

①随机插入或删除数据效率低O(N)

②扩容有消耗，还存在一部分的空间浪费，因此扩两倍或1.5倍是比较合适的，扩容多了会浪费，少了还得再次扩容。

list的优点：

①按需申请释放，无需扩容

②任意位置插入删除，时间复杂度是O(1)

list的缺点：

①不支持下标随机访问

②CPU高速缓冲命中率低

使用情况：

如果大量数据需要在中间（反正不是头和尾）插入删除的时候，就用list，如果是大量在头和尾插入或删除就用vector。

迭代器失效总结

vector的迭代器失效是在insert和erase，即插入和删除数据都有可能导致迭代器失效，因为位置发生了变化。

list的迭代器失效是在erase，即删除节点的时候会导致迭代器失效，因为迭代器指向的节点被删除了。

解决的方法是更新迭代器，即返回迭代器的位置。

而对于string类。string的迭代器也会失效，跟vector类似，但是一般不会去关注string迭代器失效问题。因为vector和list的insert和erase接口，参数给的是迭代器，而string常用的给的是下标，迭代器支持的用得很少。