文章目录
【写在前面】
在学完 list，大家对 STL 中的迭代器的认知会进一步提高。list 用的虽然不多，但是它的底层有很多经典的东西，尤其是它的迭代器。list 的结构对我们来说应该问题不大，因为在《数据结构》时我们就已经了解过链表了，它的结构是一个带头双向循环链表，之前我们也实现过。
对于 list 没有 reserve 和 resize，因为它的底层不是连续的空间，它是用一个申请一个，不用一个就释放一个。也没有 operator[]，因为它不支持随机访问。同时它有头插、头删、尾插、尾删、任意位置的插入、删除。因为 list 是带头双向循环链表。
有了前面 string 和 vector 的铺垫，我们这里对于 list 的使用就大概过一下即可，因为它们比较类似，重点主要放在 list 的深度剖析及模拟实现。
其实来严格来说 C++ 的 list 有两个：
- <list> 是带头双向循环链表，是我们本章需要学习的知识
- <forward_list> 是单链表，它是 C++11 所增加的，它的使用场景一点也不多，查看文档，可以看到它不支持尾插、尾删，因为对于单链表效率很低。并且它的任意位置插入、删除是在当前位置之后，因为当前位置之前得找前一个，也是一个 O(N) 的实现。单链表对比双向链表的唯一优势就是每个节点少存一个指针。
一、list的介绍及使用
💦 list的介绍
- list 是可以在常数范围内 O(1) 在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
- list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能往前迭代，已让其更简单高效
- 与其它的序列式容器相比(array，vector，deque)，list 通常在任意位置进行插入、移除元 素的执行效率更好
- 与其它序烈式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第 6 个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)
💦 list的使用
1、list的构造
| constructor | 接口说明 |
| list() | 构造空的 list |
| list(size_type n, const value_type& val = value_type()) | 构造 list 中包含 n 个值为 val 的元素 |
| list(const list& x) | 拷贝构造函数 |
| list(InputIterator first, InputIterator last) | 用 (first, last) 区间中的元素构造 list |
#include<iostream> #include<vector> #include<list> using namespace std; namespace std { void test_list1() { list<int> lt1; list<int> lt2(10, 5); list<int> lt3(lt2.begin(), lt2.end()); //同样支持用其它容器的迭代器区间去构造,因为它是模板,并且它可以支持如下写法 vector<int> v = { 1, 2, 3, 4, 5 }; list<int> lt4(v.begin(), v.end()); list<int> lt5(lt4); } } int main() { std::test_list1(); return 0; }
2、list iterator的使用
| iterator | 接口说明 |
| begin + end | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的 reserve_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置 |
#include<iostream> #include<vector> #include<list> using namespace std; namespace std { void test_list1() { vector<int> v = { 1, 2, 3, 4, 5 }; list<int> lt(v.begin(), v.end()); list<int>::iterator it1 = lt.begin(); //注意对于string和vector我们可以用小于或不等于做为判断条件,但是list只能用不等于做为判断条件,这时因为不同的容器中空间连续与否的原因 while(it1 != lt.end()) { cout << *it1 << " "; ++it1; } cout << endl; list<int>::reverse_iterator it2 = lt.rbegin(); while(it2 != lt.rend()) { cout << *it2 << " "; ++it2; } cout << endl; //list里已经不再支持operator[] for(auto e : lt) { cout << e << " "; } cout << endl; } } int main() { std::test_list1(); return 0; }
3、list capacity
| capacity | 接口说明 |
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点的个数 |
4、list element access
| element access | 接口说明 |
| front | 返回 list 的第一个节点的中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
5、list modifiers
| modifiers | 接口说明 |
| push_front | 在 list 首元素前插入值为 val 的元素 |
| pop_front | 删除 list 中第一个元素 |
| push_back | 在 list 尾部插入值为 val 的元素 |
| pop_back | 删除 list 中最后一个元素 |
| insert | 在 list position 位置中插入值为 val 的元素 |
| erase | 删除 list position 位置的元素 |
| swap | 交换两个 list 中的元素 |
| clear | 清空 list 中的有效元素 |
#include<iostream> #include<algorithm> #include<vector> #include<list> #include<functional> #include<time.h> using namespace std; namespace std { void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(10); lt.push_front(20); lt.push_front(30); lt.push_front(40); for(auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_back(); lt.pop_back(); lt.pop_back(); lt.pop_front(); lt.pop_front(); lt.pop_front(); lt.pop_front(); //lt.pop_front();//err,注意在头删、尾删时要保证list里还有数据,否则这里会报断言错误 for(auto e : lt) { cout << e << " "; } } void test_list2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); //list里也没有提供find,所以这里使用algorithm里的 list<int>::iterator pos = find(lt.begin(), lt.end(), 2); if(pos != lt.end()) { lt.insert(pos, 20); } for (auto e : lt) { cout << e << " "; } cout << endl; //clear并不会把头节点清除,这里还可以继续push_back lt.clear(); lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for(auto e : lt) { cout << e << " "; } cout << endl; } void test_list3() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); list<int> lt2; lt2.push_back(2); lt2.push_back(1); list<int> lt3; lt3.push_back(5); lt3.push_back(1); lt3.push_back(3); lt3.push_back(3); //对于swap,在C++98中建议使用容器里的,而不建议使用算法里的。它们效果一样,但是效率不一样,具体见如下说明 lt1.swap(lt2); //swap(lt1, lt2); for(auto e : lt1) { cout << e << " "; } cout << endl; for(auto e : lt2) { cout << e << " "; } cout << endl; //注意所有的排序都满足,>是降序,<是升序,这里默认是升序 //这个也是一个类模板,它是一个仿函数,所在头<functional>后面我们会实现,sort所在头<algorithm> /*greater<int> g; lt3.sort(g);*/ lt3.sort(greater<int>());//同上,可以直接写成匿名对象 for(auto e : lt3) { cout << e << " "; } cout << endl; //unique的功能是去重,所在头<algorithm>,去重的前提是排序,升序降序都行,如果不排序它只去去相邻的数据 lt3.unique(); for(auto e : lt3) { cout << e << " "; } cout << endl; //erase需要先find,而remove可以直接删除,有就全删,没有就不删,所在头<algorithm> lt3.remove(3); for (auto e : lt3) { cout << e << " "; } cout << endl; //reverse的功能是逆置,对于带头双向循环链表的逆置比单链表简单的多,所在头<algorithm> lt3.reverse(); for (auto e : lt3) { cout << e << " "; } cout << endl; //merge的功能是合并 //splice的功能是转移,它转移的是节点不是数据,很特殊的场景下才会使用到,我们以后在了解LRU可能还会再接触到 } void test_OP() { srand(time(0)); const int N = 10000; list<int> lt; vector<int> v; v.resize(N); for (int i = 0; i < N; i++) { v[i] = rand(); lt.push_back(v[i]); } int begin1 = clock(); sort(v.begin(), v.end());//vector用算法里的,它底层使用的是快排的三数取中法 int end1 = clock(); int begin2 = clock(); lt.sort();//list用容器里的 //sort(lt.begin(), lt.end());//err,本质sort会用两个迭代器相减,而list的迭代器不支持减 int end2 = clock(); cout << "vector sort：" << end1 - begin1 << endl; cout << "list sort：" << end2 - begin2 << endl; } } int main() { std::test_list1(); std::test_list2(); std::test_list3(); std::test_OP(); return 0; }
📝说明
- List item
为什么 C++98 建议使用各自容器里的 swap，而不建议使用算法里的 swap ❓
如下可以看到算法里 swap 的 C++98 的实现，无论是 string、vector、list 使用它会涉及深拷贝问题，而且这里的深拷贝代价极大，需要深拷贝 3 次 —— 当 lt1 和 lt2 交换，这里会把 lt1 拷贝构造一份 c，然后把 lt2 赋值于 lt1，c 赋值于 lt2，完成交换。
而如果是容器里的 swap，需要交换 lt1 和 lt2，只需要头指针交换即可。假设是 vector，只要把 lt1 和 lt2 对应的 _start、_finish、_endofstorage 交换即可。相比算法里的 C++98 里的 swap，这里可以认为没有任何代价。
所以说，我们为什么在以后工作中多数不会去写数据结构，而还要学《数据结构》这门学科。因为如果你没有自己去实现数据结构，你不了解链表的结构，我跟你说这 2 个 swap 有深拷贝差异，你可能都听不懂，没有学过《数据结构》的人永远不能理解为什么 top-k 问题用了堆好像效率就高很多。所以我们从 C 语言一路走来，各种各样的模拟实现(小的有 strstr、strcmp；大的有二叉树、list)，其实不是为了造更好的轮子，而是能更好的理解并高效的使用。
- List item
迭代器补充 ❗
容器迭代器的分类：
a) 使用功能的角度可分为，(正向、反向) + const
b) 容器底层结构的角度可分为，单向、双向、随机
比如单链表迭代器、哈希表迭代器就是单向，特征是能 ++，不能 --；双向链表迭代器、map 迭代器就是双向，特征是能 ++、–；string、vector、deque 迭代器就是随机迭代器，特征是能 ++、–、+、-，一般随机迭代器底层都是一个连续的空间。
可以看到算法里的 sort、reverse 的声明，它的模板参数的命名不是 T，也不是 iterator，对于模板参数的命名可以任意，但是它的命名是有含意的。比如说你要用 sort 这个算法，你要用的是随机迭代器；你要用 reverse 这个算法，你要用的是双向迭代器。随机迭代器也可以使用 reverse，因为随机迭代器是一个双向迭代器，因为它满足双向迭代器的所有功能；同理，双向迭代器也是单向迭代器、随机迭代器也是单向迭代器。也就意味着这里模板参数的命令是单向迭代器，那么你的容器可以是单向、双向、随机；模板参数的命令是双向迭代器，那么你的容器可以是双向、随机；模板参数的命令是随机迭代器，那么你的容器可以是随机。后面学了继承，就可以知道它们满足一个继承关系。
所以这里要明白一个关系
6、list迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
#include<iostream> #include<algorithm> #include<list> using namespace std; namespace std { void test_list1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> lt(array, array + sizeof(array) / sizeof(array[0])); list<int>::iterator pos = find(lt.begin(), lt.end(), 5); if(pos != lt.end()) { //不会失效 lt.insert(pos, 45); } for(auto e : lt) { cout << e << " "; } cout << endl; } void test_list2() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> lt(array, array + sizeof(array) / sizeof(array[0])); list<int>::iterator pos = find(lt.begin(), lt.end(), 5); if(pos != lt.end()) { //会失效,可以重新指定迭代器pos lt.erase(pos); //pos = lt.erase(pos);//ok } cout << *pos << endl; cout << endl; } } int main() { std::test_list1(); std::test_list2(); return 0; }
📝说明
