初识list
1. list基本概况
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素.
list实现的基本框架：
与string和vector不同，list的遍历需要通过迭代器来实现，list的迭代器也不再是原生指针，而是模拟原生指针行为的一层封装。
对于范围for的实现，本质就是通过迭代器，范围for可以遍历容器的迭代器，对迭代器进行解引用，然后依次拷贝给元素e，所以C++11的范围for没有什么新花样，本质上使用的还是迭代器实现的。
下面我们看看list的使用：
2.list常见的重要接口
先贴上官方文档：list文档介绍
一、 对于list的构造我们有四种构造方式：
构造空的list、构造含有n个值为val的元素初始化list、拷贝构造、区间（first，last）元素构造list。
void TestList1() { list<int> l1; // 构造空的l1 list<int> l2(4, 100); // l2中放4个值为100的元素 list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3 list<int> l4(l3); // 用l3拷贝构造l4 // 以数组为迭代器区间构造l5 int array[] = { 16,2,77,29 }; list<int> l5(array, array + sizeof(array) / sizeof(int)); // 列表格式初始化C++11 list<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，头部插入0 L.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 100000 int 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() { // 用数组来构造list int 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.提供统一的访问方式，降低使用者的使用成本。
- 实现list的迭代器，最底层其实就是一个链表节点结构体的指针，我们知道 迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为! 所以对list要实现迭代器的功能，我们对这个指针进行了封装，所以list的迭代器就是用一个自定义类型来封装 node* 。
- 我们知道对于模板实例化，加上模板参数才是类型，否则就是类名。
- 在实现const版本迭代器时最容易想到的一种方式就是重新构建一个类，类里面原有成员函数都不变，仅仅是将类名做出修改，然后我们把解引用函数的返回值修改成常引用，在使用const_iterator迭代器类型的时候，如果你解引用迭代器则直接调用__list_const_iterator类里面的返回常引用的重载函数。
- == 这样显然是代码冗余的，大佬是怎么做的？其实是通过增加模板参数，在传参数时，根据参数类型的不同实例化出不同的类。==
- 例如用const_iterator时，就是用第二个模板参数为const T&的类模板，等T类型确定时，就会实例化出具体的类，当用iterator时，我们就用第二个模板参数为T&的类模板，等T类型确定时，又会实例化出另一个不同的类。
- 当list存的是结构体类型Pos时，直接打印解引用迭代器后的值就会出现问题，因为解引用迭代器后拿到的是Pos类的对象，所以如果想要打印对象的值，我们可以重载Pos类的流插入运算符来实现，如果Pos类的成员变量是私有的，我们也可以用友元函数来解决。
- 如果是普通指针我们一般就用解引用，如果是结构指针，我们喜欢用→的访问方式。当迭代器指向的数据是一个结构体对象时，我们更偏向于用→来访问，当迭代器指向的数据是单个数据时，我们更偏向于用*来访问。
- 所以下面→解引用的使用方式更舒服一些，因为迭代器it所指向的内容是Pos结构体的对象。但it不是一个结构体指针，不能用→这样的访问方式，这该如何解决呢？因为it是一个对象，我们可以利用运算符重载来解决。
- 这里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
- 实现insert时可以看到所传参数是迭代器，实际就是链表结点的地址，也是一个结构体指针，只不过我们对这个结构体指针进行了封装，这个迭代器就变成了一个对象，在实现上和数据结构初阶实现的带头双向循环链表没什么区别，仅仅是多了一个类的封装。
- 那insert这里迭代器会不会失效？ 不会，pos指向节点没有发生地址改变
- erase这里迭代器失效吗 肯定失效。因为迭代器指向被干掉了。 所以我们可以加个断言啊---- 谁不可以erase？ — 哨兵位头节点
- 迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
- 实现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; }
小问题
- 在实现赋值重载函数时，为什么我们不能传引用？当然不能，因为这里是赋值，不是二者交换，所以应该传参调用其拷贝构造
//赋值重载 list<T>& operator=(const list<T> l) { swap(l); return *this; }
- 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; } };
显示报错报错 没有合适的默认构造函数怎么办？ 提供缺省----缺省函数为什么用 T() :调用其默认构造
这个是很多人的疑惑：const对象在定义时有没有const属性？ 答案是没有的！否则我们如何对数据进行初始化？所以这里是编译器的特殊处理罢了，站在语法的角度，就初始化后在赋予const属性
list与vector的对比
vector
优点：
a.支持下标的随机访问
b.尾插尾删效率高
c.CPU高速缓存命中率高（局部性原理）
缺点：
a.前面部分插入删除数据效率低（插入和删除需要挪动数据，尤其是数据量大时效率较低）
b.扩容有消耗，还存在一定空间浪费（2倍扩容是比较合适的，开大了浪费空间，开小了需要频繁扩容）
list
优点：
a.按需申请释放空间，无需扩容
b.任意位置插入删除的时间复杂度是O(1)，不考虑find查找位置，只是单纯erase和insert。
缺点：
a.不支持下标的随机访问
b.CPU高速缓存命中率低（局部性原理）
vector的insert和erase之后迭代器都会失效，list在insert之后迭代器不会失效，erase之后迭代器会失效
在需要高效存储，支持随机访问，不关心插入删除效率，我们倾向于使用vector
大量插入和删除操作，不关心随机访问的情况，我们倾向于使用list，而且现实中项目中list用的蛮多的
少熬夜，早点休息！
