【STL】list剖析及模拟实现

✍作者：阿润菜菜
📖专栏：C++

---

初识list

1. 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实现的基本框架：

1. 与string和vector不同，list的遍历需要通过迭代器来实现，list的迭代器也不再是原生指针，而是模拟原生指针行为的一层封装。
2. 对于范围for的实现，本质就是通过迭代器，范围for可以遍历容器的迭代器，对迭代器进行解引用，然后依次拷贝给元素e，所以C++11的范围for没有什么新花样，本质上使用的还是迭代器实现的。
   下面我们看看list的使用：

2.list常见的重要接口

先贴上官方文档：list文档介绍

一、 对于list的构造我们有四种构造方式：
构造空的list、构造含有n个值为val的元素初始化list、拷贝构造、区间（first，last）元素构造list。

void TestList1()
{list<int> l1;                         // 构造空的l1list<int> l2(4, 100);                 // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3);                    // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}       cout << endl;// C++11范围for的方式遍历for (auto& e : l5)cout << e << " ";cout << endl;
}

二、ist迭代器的使用：
1.在使用上时可以将迭代器理解成一个指针，该指针指向list中的某个节点。同时提供了正向迭代器和反向迭代器。
2… 注意：begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 编译不通过}cout << endl;
}void TestList2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中语法auto it = l.begin();                     // C++11之后推荐写法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}

三、list的空间大小

四、list元素获取

五、list的元素操作
1.对于list来说，insert不会导致迭代器失效，vector存在迭代器失效是因为在扩容时reserve采取异地扩容的方式，这就导致原有迭代器指向了已经被释放的空间。
但list并不存在扩容这样的操作，list直接按需申请空间，你要插入多少个节点，那我就申请多少个节点，然后将所有的节点链接到哨兵节点前面就好了，所以insert之后迭代器依旧可以继续使用，因为他对应的节点空间不会被销毁，依旧好好的存在着。
2.对于list的erase来说就不一样了，erase会释放迭代器对应节点的空间，自然erase之后迭代器就会失效，如果想要继续使用迭代器，则可以利用erase的返回值来更新迭代器，erase会返回被删除节点的下一个节点的迭代器，我们可以用erase的返回值来更新迭代器

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase 
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}

其实list还提供了一个sort函数，但因为效率很低，我们基本上不会用，对比同样的算法库函数sort，如果你要排序list，倒不如先将list的数据拷贝到vector进行排序，等排完序再将数据拷贝回list里面去，就算这样的排序的性能都是要比直接用list进行排序的性能要高不少 ---- 一定要release下进行对比，能差一倍！
测试代码：

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
#include<time.h>#define N 100000int main()
{list<int> lt1,lt2;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}//拷贝到vector进行排序int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end()); //调用算法库sort进行排序size_t i = 0;for (auto& e : lt1) //将数据拷贝回去{e = v[i++];}int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort: %d\n", end2 - begin2);
}

算法库的sort底层用的是快速排序，为了key值选的合适，快排会进行三数取中，所以会进行迭代器的作差，而list的双向迭代器肯定不支持做差，所以调用算法库的sort就会报错。
如果想要排序链表，那就只能调用list类的成员函数sort来进行排序，list的sort底层用的是归并排序。

这里就要引出迭代器从功能上来说，可以分为三类：只能++的单向迭代器（单链表、哈希表），既能++也能 - - 的双向迭代器（list带头双向循环链表），既能++也能 - - 还能±某个具体的数的随机迭代器（string、vector）

resize用于调整链表的空间，如果是调整大一些，那就是一个一个的申请节点，尾插到链表上面去。如果是调整小一些，那也需要一个个的释放节点，相当于尾删节点。

// insert /erase 
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList5()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}

list的模拟实现

list的迭代器 — 精华部分

迭代器的价值是什么：
a.迭代器对底层的实现进行封装，不暴露底层实现的细节。
b.提供统一的访问方式，降低使用者的使用成本。

1. 实现list的迭代器，最底层其实就是一个链表节点结构体的指针，我们知道 迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为! 所以对list要实现迭代器的功能，我们对这个指针进行了封装，所以list的迭代器就是用一个自定义类型来封装 node* 。
2. 我们知道对于模板实例化，加上模板参数才是类型，否则就是类名。
   在实现const版本迭代器时最容易想到的一种方式就是重新构建一个类，类里面原有成员函数都不变，仅仅是将类名做出修改，然后我们把解引用函数的返回值修改成常引用，在使用const_iterator迭代器类型的时候，如果你解引用迭代器则直接调用__list_const_iterator类里面的返回常引用的重载函数。
3. == 这样显然是代码冗余的，大佬是怎么做的？其实是通过增加模板参数，在传参数时，根据参数类型的不同实例化出不同的类。==
   例如用const_iterator时，就是用第二个模板参数为const T&的类模板，等T类型确定时，就会实例化出具体的类，当用iterator时，我们就用第二个模板参数为T&的类模板，等T类型确定时，又会实例化出另一个不同的类。
4. 当list存的是结构体类型Pos时，直接打印解引用迭代器后的值就会出现问题，因为解引用迭代器后拿到的是Pos类的对象，所以如果想要打印对象的值，我们可以重载Pos类的流插入运算符来实现，如果Pos类的成员变量是私有的，我们也可以用友元函数来解决。
5. 如果是普通指针我们一般就用解引用，如果是结构指针，我们喜欢用→的访问方式。当迭代器指向的数据是一个结构体对象时，我们更偏向于用→来访问，当迭代器指向的数据是单个数据时，我们更偏向于用*来访问。
6. 所以下面→解引用的使用方式更舒服一些，因为迭代器it所指向的内容是Pos结构体的对象。但it不是一个结构体指针，不能用→这样的访问方式，这该如何解决呢？因为it是一个对象，我们可以利用运算符重载来解决。
7. 这里template<class T, class Ref, class Ptr>三个模板参数分别是提供 T& 、const T& 和提供解引用访问（→)

//迭代器 --- 自定义类型封装node*//分类：1.原生指针 2.用自定义类型对原生指针的封装，模拟指针的行为//即->迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为！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* n)  // 提供构造函数，遍历使用:_node(n){}Ref operator* ()  //提供const版本迭代器{return _node->_data;}//const 迭代器和普通迭代器的区别是什么？   一个内容可修改 ，一个内容不可被修改Ptr operator->()  //->重载{return &_node->_data;  //引用返回减少拷贝}//++返回什么？  返回迭代器呀！self& operator++()  //遍历  前置++{_node = _node->_next;return *this;}self& operator++(int) //后置++{self tmp(*this); //拷贝构造一下_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}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;}};

9. 那这个迭代器是浅拷贝可以吗？ 可以呀，因为这个是node的指针，浅拷贝后指针指向同一个node是可以的。那为什么没有报错呢？ 因为我们没有提供析构函数。 而且不释放当然是正确的，因为这里结点是属于链表的，释放结点的工作应该交给链表类而不是迭代器类。
   所以当内置类型涉及资源申请时，也并不一定就要写析构函数，还需要视情况而定。迭代器只是一个工具而已，释放也得由开辟空间的对象(list)来释放

10.对于迭代器的封装： 底层物理上都是指向这个对象的4个字节的指针。但语法的千差万别，主要还是运算符重载！

重点的两个接口 — insert 和 erase

1. 实现insert时可以看到所传参数是迭代器，实际就是链表结点的地址，也是一个结构体指针，只不过我们对这个结构体指针进行了封装，这个迭代器就变成了一个对象，在实现上和数据结构初阶实现的带头双向循环链表没什么区别，仅仅是多了一个类的封装。
2. 那insert这里迭代器会不会失效？ 不会，pos指向节点没有发生地址改变
3. erase这里迭代器失效吗 肯定失效。因为迭代器指向被干掉了。 所以我们可以加个断言啊---- 谁不可以erase？ — 哨兵位头节点
4. 迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
5. 实现erase时返回删除位置的下一个位置的迭代器，以便于使用者更新erase之后的迭代器，防止产生迭代器失效问题。

		//insert函数 pos前插入x//insert这里迭代器会不会失效？  不会，pos指向节点不会发生地址改变void insert(iterator pos, const T& x){node* cur = pos._node; //指针node* prev = cur->_prev;node* new_node = new node(x); //堆区申请prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}//erase函数 删除pos位置void erase(iterator pos){assert(pos != end());  //防止删除哨兵节点node* next = pos._node->_next;node* prev = pos._node->_prev;prev->_next = next;next->_prev = prev;delete pos._node;}

小问题

1. 在实现赋值重载函数时，为什么我们不能传引用？当然不能，因为这里是赋值，不是二者交换，所以应该传参调用其拷贝构造
   

//赋值重载list<T>& operator=(const list<T> l){swap(l);return *this;}

2. list的反向迭代器：通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

//反向迭代器// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};

3. 显示报错报错 没有合适的默认构造函数怎么办？ 提供缺省----缺省函数为什么用 T() :调用其默认构造
4. 这个是很多人的疑惑：const对象在定义时有没有const属性？ 答案是没有的！否则我们如何对数据进行初始化？所以这里是编译器的特殊处理罢了，站在语法的角度，就初始化后在赋予const属性

list模拟实现源码参考

list与vector的对比

vector

优点：
a.支持下标的随机访问
b.尾插尾删效率高
c.CPU高速缓存命中率高（局部性原理）
缺点：
a.前面部分插入删除数据效率低（插入和删除需要挪动数据，尤其是数据量大时效率较低）
b.扩容有消耗，还存在一定空间浪费（2倍扩容是比较合适的，开大了浪费空间，开小了需要频繁扩容）

list

优点：
a.按需申请释放空间，无需扩容
b.任意位置插入删除的时间复杂度是O(1)，不考虑find查找位置，只是单纯erase和insert。
缺点：
a.不支持下标的随机访问
b.CPU高速缓存命中率低（局部性原理）

1. vector的insert和erase之后迭代器都会失效，list在insert之后迭代器不会失效，erase之后迭代器会失效
2. 在需要高效存储，支持随机访问，不关心插入删除效率，我们倾向于使用vector
3. 大量插入和删除操作，不关心随机访问的情况，我们倾向于使用list，而且现实中项目中list用的蛮多的

少熬夜，早点休息！