list1. list 的介绍list 的文档介绍list属于 STL 六大组件之一——容器，前面已介绍过两种容器（string/vector），前两种容器都基于顺序表（数组），而list底层则是基于链表（通常为带头双向循环链表）。list作为顺序容器，使用带头双向循环链表为数据结构，其优点之一就是插入/删除操作简便高效，常数时间内即可完成任意位置的插入/删除。相比顺序表，链表的缺点很明显，无法使用下标+方括号[]进行高效的随机访问，对于指定结点，只能遍历查找。底层数据结构带来的这种差异，也体现在了方法的实现上。例如Element access接口（元素的访问接口），list容器只有front方法与back方法，并未保留string/vector中的operator[]运算符重载与at方法。注：at与operator[]功能基本一致，但内部实现时对数组越界访问处理更严格。2. list 的使用2.1 构造函数构造函数同vector，共重载了4个构造函数，其中迭代器区间构造为函数模板。default (1)：全缺省构造，即默认构造。定义list对象时无需传参即可初始化。fill (2)：使用n个value进行初始化的带参构造。range (3)：迭代器区间构造。其实现是模板，允许使用迭代器区间中的各元素进行初始化，换言之，允许使用其他容器中的元素初始化list对象（但要求元素类型一致或可强制类型转换）。copy (4)：拷贝构造。使用另一个list对象中的元素初始化新的list对象。析构赋值重载代码示例 2.1.1#include <iostream> #include <list> // 测试方法 void Test() { // 1、默认构造 std::list<int> lt1; // 无需传参即可初始化 // 2、n个val带参构造 std::list<char> lt2(5, 'a'); // 向list对象中插入5个字符'a' // 3、迭代器区间构造：区间[第二个元素，末尾元素)，左闭右开，最终取中间3个元素 std::list<char> lt3(++lt2.begin(), --lt2.end()); // 迭代器区间初始化lt3 // 4、拷贝构造 std::list<char> lt4(lt2); // 拷贝lt2用于初始化lt4 // 5、赋值重载 lt4 = lt3; // lt3的内容赋值给lt4 } int main() { Test(); // 函数结束，栈帧释放，变量/对象销毁前自动调用析构函数~list() return 0; }初始化结果：赋值lt4后：2.2 listCapacity补充，实际上这3个容器都有resize/clear接口，但vector的clear接口和list的resize/clear接口都不在Capacity中，而是在Modifers中。也就是说这3个容器其实都有接口：empty/size/max_size/resize/clear。相比string/vector，list没有扩容方面的接口，因为链表由一个个结点构成，没有扩容的概念，数组才需要扩容。例如string/vector都有如下接口：reserve接口可用于扩容capacity接口可返回数组容量的大小shrink_to_fit接口可用于缩容string另外还有：length接口可返回字符串长度list只保留了5个更通用的接口：empty判空接口，判断元素/结点个数是否为0size接口，返回元素/结点个数resize接口，list中就不是扩容了，而是插入或删除数据，若插入可选择指定特定值。clear接口，删除所有数据，size归零。max_size接口，返回值为容器最大能存储的数据个数（数据类型是无符号整型 size_t），此接口意义不大。2.3 list Element access相比string/vector，链表不可使用下标访问元素，因此list没有[] 运算符的重载与at接口。只保留了front与back接口，返回首元素/尾元素的引用或const引用（reference或const_reference）。注：这里存在多次重命名，reference即value_type&，value_type即模板参数T，T即容器存储的元素类型。2.4 list 迭代器与迭代器分类list 迭代器迭代器接口与string/vector完全一致，包括正向迭代器begin/end与反向迭代器rbegin/rend，以及对应的const版本迭代器cbegin/cend/crbegin/crend。迭代器分类正向迭代器、反向迭代器以及const迭代器，都是从功能的角度划分迭代器。实际还可从性质的角度来划分，例如：随机迭代器 (Random-access iterator)：forward_list（单向/向前链表）、unordered_map、unordered_set。双向迭代器 (Bidirectional iterator)：list（双向循环链表）、map、set。单向迭代器 (Forward iterator)：vector、string、dequeue（双端队列）。底层结构决定性质，性质不同导致支持不同的运算符重载。例如这3类迭代器都可支持*/->/==/!=/=/++等运算符重载，但未必支持[]/+/-/--。随机迭代器：底层是数组，支持下标随机访问元素，同样支持单向或双向的顺序访问。因此可支持的运算符重载包括+/-/+=/-=/[]/--。双向迭代器：底层是双向链表，不支持随机访问，但支持顺序访问，可向前/向后遍历。因此可支持的运算符重载包括自减--，但不支持+/-/+=/-=/[]。单向迭代器：底层是单向链表，不可随机访问，只支持向前遍历。因此仅支持部分通用的运算符重载，例如自增++，但不支持+/-/+=/-=/[]/--。底层结构同样决定了可支持的算法。如算法库(algorithm) 中的逆置算法reverse，可反转序列次序，其实现为函数模板，模板参数名是BidirectionalIterator；又如排序算法sort，其实现为函数模板，模板参数名是RandomAccessIterator。前者支持双向迭代器，但随机迭代器也兼容；后者支持随机迭代器，不兼容双向迭代器/单向迭代器。sort底层是快排。快排算法递归深度越深，效率越低，为了优化，有三数取中，也有提前结束转堆排等措施，不管哪种，都需要支持[]，不然无法随机访问元素，而且堆排底层就是顺序表，这也是为什么sort只能支持随机迭代器。补充：包含关系：随机>双向>单向，可向上兼容但不可向下兼容。随机可以看作特殊的双向/单向，双向可看作特殊的单向，这种性质关系实际涉及到了继承的概念：子类是特殊的父类。其实这里还引申出了两个不存在的迭代器Input和Output，没有实体对应的迭代器，也称为只读迭代器和只写迭代器。这是抽象层的概念，它们并非任一容器的迭代器类型，实际用处不大，但确实存在这种设计，例如部分算法中可能出现InputIterator（一般不会出现OutputIterator），意味着可以兼容任意类型的迭代器，因为随机/双向/单向都是Input的子类，都是特殊的InputIterator（再次说明：抽象层概念上是继承关系但实际不存在Input这个类型）。代码示例 2.4.1#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试方法1 void test_list1() { std::list<int> lt1; // 向lt1中依次尾插4、3、2、1 lt1.push_back(4); lt1.push_back(3); lt1.push_back(2); lt1.push_back(1); // list 容器访问方式：迭代器（容器通用方式） std::list<int>::iterator it = lt1.begin(); std::cout << "lt1: "; while (it != lt1.end()) { // list 迭代器为Bidirectional iterators 双向迭代器 // 支持解引用*自增++自减--，但不支持加+减-以及方括号[]随机访问 std::cout << *it << " "; ++it; // lt1.erase(it + 3); // it+3 类似写法 list 不再支持，仅适用容器底层数据结构为连续空间的情况。 /* 顺序表，即数组，底层空间是连续的，如 string/vector，其迭代器类型可能就是原生 指针，指针本身就可以加减运算。即使不是原生指针，自定义类型想进行运算符重载也是很轻 松的。但链表不同，各结点空间分别开辟，基本是离散的，结点地址不连续，自然不支持指针 运算，即使重载具备可行性，也完全没有必要。*/ } std::cout << std::endl; // 性质决定可支持的运算符重载，同样决定了算法 // 1. 将待排序的元素存入 vector 对象 std::vector<int> v1(lt1.begin(), lt1.end()); // 2. 在 vector 中排好序 std::sort(v1.begin(), v1.end()); // 3. 将排序完的序列赋值给 list 对象 lt1.assign(v1.begin(), v1.end()); // 通过范围for访问：底层其实仍为迭代器 std::cout << "lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list1(); return 0; }运行结果：2.5 list Modifierslist Modifiers接口和string/vector Modifiers接口大体相似：assign：重新赋值，可用迭代器区间赋值或n个value赋值，替换原元素内容并根据新的元素个数、大小调整数组容量。此处list容器中是替换链表结点内容并根据元素个数调整结点个数，可能开辟或释放结点空间。push_back/emplace_back：这两个接口都是尾插。push_front/emplace_front：这两个接口都是头插。pop_back/pop_front：尾删/头删。insert/emplace：这两个接口都是在中间插入元素/结点。erase：删除指定元素/结点。swap：和另一list对象交换容器内容（元素/结点的值与个数）。补充：push系列和emplace系列功能基本是一致的，push系列有的emplace系列都有，甚至部分情况下emplace系列可能更高效些，但具体区别暂不讨论，涉及到右值引用、模板可变参数、右值引用和完美转发等内容，下面只讨论写法上的一些区别。代码示例 2.5.1#include <iostream> #include <list> class A { public: A(int a1 = 1, int a2 = 1) : _a1(a1) , _a2(a2) { std::cout << "A(int a1 = 1, int a2 = 1)" << std::endl; } A(const A& aa) : _a1(aa._a1) , _a2(aa._a2) { std::cout << "A(const A& aa)" << std::endl; } int _a1; int _a2; }; // 测试方法2 void test_list2() { // push_back/push_front支持的，emplace_back/emplace_front都支持 std::list<A> lt; // 构造有名对象插入list A aa1(1, 1); lt.push_back(aa1); lt.emplace_back(aa1); // 构造匿名对象插入list lt.push_back(A(2, 2)); lt.emplace_back(A(2, 2)); // emplace还支持直接传构造A对象的参数 lt.emplace_back(3, 3); // push_back/push_front 不支持这种写法，因为它们只有1个形参 // lt.push_back(3, 3); for (auto& e : lt) { std::cout << e._a1 << " " << e._a2 << std::endl; } } int main() { test_list2(); return 0; }运行结果：可以观察到，emplace_back直接传构造A对象的参数避免了一次形参的拷贝构造，不管是传匿名对象还是有名对象，都需要构造一次对象再拷贝构造一次形参对象，但直接传参数就只有一次构造。这类情况下，emlace系列也就比push系列更高效些。insert同理。代码示例 2.5.2#include <iostream> #include <list> #include <algorithm> // 测试方法3 void test_list3() { std::list<int> lt; // 依次向list对象中尾插1、2、3、4、5 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); // 链表不再支持随机访问，没有加+减-方括号[]等运算符的重载 // lt.insert(lt.begin() + 2, 10); // 加减运算直接访问指定位置的写法不再支持 // 只能先遍历查找到指定位置并用 it 记录，再向指定位置插入 std::list<int>::iterator it = lt.begin(); // it 指向第一个元素 int k = 2; while (k--) // ++两次指向第三个结点 { // 只支持自增++自减--，遍历查找，时间复杂度为 O(N) it++; } lt.insert(it, 10); // 在第三个元素前插入10，插入效率为 O(1) // 打印 list 对象 for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 输入 val 值 int val; std::cin >> val; // 使用 find 在 lt 中查找特定值 it = std::find(lt.begin(), lt.end(), val); if (it != lt.end()) { // 找到则在其位置上插入20 lt.insert(it, 20); } // 打印 list 对象 for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list3(); return 0; }运行结果：2.6 list Operationslist同样实现了逆置算法reverse成员函数，与算法库中的std::reverse实际是有点冗余的，因为逆置算法支持双向迭代器，list也是双向迭代器，直接使用算法库中的逆置算法即可。代码示例 2.6.1#include <iostream> #include <list> #include <algorithm> // 测试方法4 void test_list4() { std::list<int> lt; // 依次向list对象中尾插1、2、3、4、5、6 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); std::cout << "Before reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 使用 list 自己的逆置算法 reverse lt.reverse(); std::cout << "After std::list::reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 使用算法库的逆置算法 std::reverse std::reverse(lt.begin(), lt.end()); std::cout << "After std::reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list4(); return 0; }运行结果：由于算法库中的排序算法sort只支持随机迭代器，list实现了自己的sort排序（具体实现细节暂不讨论，下面只介绍写法细节）。std::list::sort有两个重载，第一个是函数，第二个是函数模板。默认情况下，sort排升序（包括算法库中的sort），但可以传一个仿函数改为排升序，即形参comp。代码示例 2.6.2#include <iostream> #include <list> #include <algorithm> // 测试方法5 void test_list5() { std::list<int> lt; // 依次向list对象中尾插1、3、4、2、6、5 lt.push_back(1); lt.push_back(3); lt.push_back(4); lt.push_back(2); lt.push_back(6); lt.push_back(5); std::cout << "Before sort: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 算法库的 sort 算法不支持双向迭代器，使用 list 自己的排序算法 lt.sort(); // 默认为升序，但想传也可以传仿函数 less 指定排升序 std::cout << "After std::list::sort (less): "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // sort 默认排升序，可传一个仿函数改为排降序 // greater 大于> 排升序，less 小于< 排降序 std::greater<int> gt; // 构造仿函数对象需要指定元素类型 lt.sort(gt); // 也可传匿名对象 std::greater<int>() std::cout << "After std::list::sort (greater): "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list5(); return 0; }运行结果：list还支持合并算法，可以将两个list对象合并成一个链表，要求两个list对象都已有序（需确保同为升序或降序，且注意，merge同样可以传仿函数，指定合并为升序或降序，需与链表顺序一致）。合并方式其实就是从两个有序链表中，依次取极小值尾插，数据最终放入调用合并算法的容器中。需注意，合并后x链表就为空了，相当于把x链表的结点都移走了。代码示例 2.6.3#include <iostream> #include <list> #include <algorithm> // 测试方法6 void test_list6() { // 构造 list 对象 lt1：2、3、4、1 std::list<int> lt1; lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(1); // 构造 list 对象 lt2：4、3、1、2 std::list<int> lt2; lt2.push_back(4); lt2.push_back(3); lt2.push_back(1); lt2.push_back(2); std::cout << "Before sort, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nBefore sort, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; // 合并前需确保两个链表有序 lt1.sort(std::greater<int>()); lt2.sort(std::greater<int>()); std::cout << "After sort, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nAfter sort, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; // 合并链表，结果放入 lt1 中，合并后 lt2 链表为空 lt1.merge(lt2, std::greater<int>()); std::cout << "After merge, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nAfter merge, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list6(); return 0; }运行结果：list还支持去重算法unique。可去掉链表中的重复元素，只留下一个。同样要求数据必须有序。代码示例 2.6.4#include <iostream> #include <list> #include <algorithm> // 测试方法7 void test_list7() { // 构造 list 对象 lt：1、1、2、2、4、4、3、3 std::list<int> lt; lt.push_back(1); lt.push_back(1); lt.push_back(2); lt.push_back(2); lt.push_back(4); lt.push_back(4); lt.push_back(3); lt.push_back(3); std::cout << "Before sort, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 只能去重有序链表 lt.sort(); std::cout << "After sort, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 去重 lt.unique(); std::cout << "After unique, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list7(); return 0; }运行结果：remove类似erase，但erase需要传迭代器，remove直接传指定值，类似先查找值val是否存在，存在则删，没找到则正常结束，不会报错。remove_if不是删除特定值，而是传一个仿函数，可根据某种规则删除，例如删除所有偶数或者删除所有小于10的数。splice即粘接或者说剪切算法。剪切另一个list对象x的链表结点，转移给调用剪切算法的list对象。重载（1）是剪切链表的全部结点到position位置（position及其后结点均后移）；重载（2）是剪切迭代器i指向的一个结点到position位置；重载（3）是剪切迭代器区间内的所有结点到position位置。代码示例 2.6.5#include <iostream> #include <list> #include <algorithm> // 测试方法8 void test_list8() { std::list<int> lt1, lt2; std::list<int>::iterator it; for (int i = 1; i <= 4; i++) lt1.push_back(i); // lt1：1、2、3、4 for (int i = 1; i <= 3; i++) lt2.push_back(i * 10); // lt2：10、20、30 it = lt1.begin(); // 指向1 it++; // 指向2 // 剪切 lt2 中所有结点到 lt1 的 it 位置 lt1.splice(it, lt2); // 1、10、20、30、2、3、4 for (auto &e : lt1) { std::cout << e << " "; } std::cout << std::endl; // 玩法二：调整当前链表结点顺序，在单个链表内部进行剪切与转移 // 输入指定值 val int val; std::cin >> val; // 查找 val 值的位置，并返回迭代器 it = std::find(lt1.begin(), lt1.end(), val); if (it != lt1.end()) { // 查找成功，将 val 值对应的结点调整到链表头 // iterator position: 插入到 lt1.begin() 链表头 // list& x: 剪切 lt1 的链表 // iterator i: 剪切迭代器 it 所指向的结点 lt1.splice(lt1.begin(), lt1, it); } for (auto& e : lt1) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list8(); return 0; }运行结果：2.7 list实现的sort的效率问题注意，不应在Debug下测试两个sort的性能差异，而应在Release下进行测试。因为标准库中实现的std::sort底层是快排，快排用的是递归，Debug下为了调试函数栈帧申请消耗的资源更多，整体效率更慢。实际上Debug下的性能测试并不具有参考性。代码示例 2.7.1#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试 std::list::sort 与 std::sort 的效率差异（不涉及拷贝） void test_sort() { srand(time(0)); const int N = 10000000; // 1千万 std::list<int> lt; std::vector<int> v; for (int i = 0; i < N; i++) { // 生成一千万个随机数分别存入 list 和 vector // rand 最多生成3万个不同的随机数，+i尽量避免重复 auto e = rand() + i; lt.push_back(e); v.push_back(e); } // 使用算法库的 sort 排序 int begin1 = clock(); std::sort(v.begin(), v.end()); int end1 = clock(); // 使用 list 的 sort 排序 int begin2 = clock(); lt.sort(); int end2 = clock(); // 分别打印两者排序的时间差 printf("std::sort: %d\n", end1 - begin1); printf("list sort: %d\n", end2 - begin2); } int main() { test_sort(); return 0; }测试结果，约3倍：代码示例 2.7.2#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试 std::list::sort 与 std::sort 的效率差异（涉及拷贝） void test_sort2() { srand(time(0)); const int N = 10000000; // 1千万 std::list<int> lt1; std::list<int> lt2; for (int i = 0; i < N; i++) { // 生成一千万个随机数分别存入两个 list 对象 auto e = rand() + i; lt1.push_back(e); lt2.push_back(e); } // 使用算法库的 sort 排序 // 并且多1个拷贝操作，先将list中的数据拷贝到vector中 int begin1 = clock(); std::vector<int> v(lt1.begin(), lt1.end()); std::sort(v.begin(), v.end()); lt1.assign(v.begin(), v.end()); // 排序完再拷贝回来 int end1 = clock(); // 使用 list 的 sort 排序，且没有拷贝操作 int begin2 = clock(); lt2.sort(); int end2 = clock(); // 分别打印两者排序的时间差 printf("std::sort and copy: %d\n", end1 - begin1); printf("list sort no copy: %d\n", end2 - begin2); } int main() { test_sort2(); return 0; }测试结果，仍为3倍（同时可见拷贝效率还是挺可观的）：3. 模拟实现 list 容器头文件代码示例// STL容器list的模拟实现（核心接口） #pragma once #include<iostream> #include<assert.h> using namespace std; namespace fym { // 链表结点类 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) { } }; // list 迭代器 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 = nullptr) :_node(node) {} Ref operator*() { return _node->_data; } Ptr 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& l) const { return _node == l._node; } bool operator!=(const Self& l) const { return _node != l._node; } }; // list 类 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; public: void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() // 默认构造 { empty_init(); } list(const list<T>& lt) // 拷贝构造 { empty_init(); for (auto& e : lt) { push_back(e); } } list<T>& operator=(list<T> lt) // 赋值重载 { swap(lt); return *this; } ~list() // 析构 { clear(); delete _head; _head = nullptr; } list(initializer_list<T> il) // 列表构造 { // C++11规定：类似{1,2,3,4,5,6}列表类型为 std::initializer_list<T> /* initializer_list 底层在栈上开辟数组，有两个指针分别指向数组的开始和结束 ，因此 initializer_list 类型大小32位下为8字节，64位下为16字节。*/ empty_init(); // il 底层封装了一个列表 for (auto &e : il) { push_back(e); } } // Iterators iterator begin() { // 直接返回Node*，通过list_iterator的默认构造隐式类型转换成iterator return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } // Capacity size_t size() const { return _size; } bool empty() const { return _size == 0; } // Modifiers void clear() { auto it = begin(); while (it != end()) { it = erase(it); } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } iterator insert(iterator pos, const T& x) // pos位置插入值为x的结点 { Node* cur = pos._node; // 获取当前结点 Node* prev = cur->_prev; // 获取前驱结点 Node* newNode = new Node(x); // 构造1个新结点 // 调整前驱结点、当前结点、新结点的指向关系 newNode->_next = cur; cur->_prev = newNode; newNode->_prev = prev; prev->_next = newNode; ++_size; return newNode; } void push_back(const T& x){ insert(end(), x); } void push_front(const T& x){ insert(begin(), x); } iterator erase(iterator pos) // 删除pos结点，返回pos位置下一结点 { assert(pos != end()); // 避免删除空链表 Node* next = pos._node->_next; // 获取pos前驱结点 Node* prev = pos._node->_prev; // 获取pos后继结点 // 调整指向关系 next->_prev = prev; prev->_next = next; delete pos._node; // 释放pos结点 _size--; return next; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } private: Node* _head; size_t _size; }; };
list1. list 的介绍list 的文档介绍list属于 STL 六大组件之一——容器，前面已介绍过两种容器（string/vector），前两种容器都基于顺序表（数组），而list底层则是基于链表（通常为带头双向循环链表）。list作为顺序容器，使用带头双向循环链表为数据结构，其优点之一就是插入/删除操作简便高效，常数时间内即可完成任意位置的插入/删除。相比顺序表，链表的缺点很明显，无法使用下标+方括号[]进行高效的随机访问，对于指定结点，只能遍历查找。底层数据结构带来的这种差异，也体现在了方法的实现上。例如Element access接口（元素的访问接口），list容器只有front方法与back方法，并未保留string/vector中的operator[]运算符重载与at方法。注：at与operator[]功能基本一致，但内部实现时对数组越界访问处理更严格。2. list 的使用2.1 构造函数构造函数同vector，共重载了4个构造函数，其中迭代器区间构造为函数模板。default (1)：全缺省构造，即默认构造。定义list对象时无需传参即可初始化。fill (2)：使用n个value进行初始化的带参构造。range (3)：迭代器区间构造。其实现是模板，允许使用迭代器区间中的各元素进行初始化，换言之，允许使用其他容器中的元素初始化list对象（但要求元素类型一致或可强制类型转换）。copy (4)：拷贝构造。使用另一个list对象中的元素初始化新的list对象。析构赋值重载代码示例 2.1.1#include <iostream> #include <list> // 测试方法 void Test() { // 1、默认构造 std::list<int> lt1; // 无需传参即可初始化 // 2、n个val带参构造 std::list<char> lt2(5, 'a'); // 向list对象中插入5个字符'a' // 3、迭代器区间构造：区间[第二个元素，末尾元素)，左闭右开，最终取中间3个元素 std::list<char> lt3(++lt2.begin(), --lt2.end()); // 迭代器区间初始化lt3 // 4、拷贝构造 std::list<char> lt4(lt2); // 拷贝lt2用于初始化lt4 // 5、赋值重载 lt4 = lt3; // lt3的内容赋值给lt4 } int main() { Test(); // 函数结束，栈帧释放，变量/对象销毁前自动调用析构函数~list() return 0; }初始化结果：赋值lt4后：2.2 listCapacity补充，实际上这3个容器都有resize/clear接口，但vector的clear接口和list的resize/clear接口都不在Capacity中，而是在Modifers中。也就是说这3个容器其实都有接口：empty/size/max_size/resize/clear。相比string/vector，list没有扩容方面的接口，因为链表由一个个结点构成，没有扩容的概念，数组才需要扩容。例如string/vector都有如下接口：reserve接口可用于扩容capacity接口可返回数组容量的大小shrink_to_fit接口可用于缩容string另外还有：length接口可返回字符串长度list只保留了5个更通用的接口：empty判空接口，判断元素/结点个数是否为0size接口，返回元素/结点个数resize接口，list中就不是扩容了，而是插入或删除数据，若插入可选择指定特定值。clear接口，删除所有数据，size归零。max_size接口，返回值为容器最大能存储的数据个数（数据类型是无符号整型 size_t），此接口意义不大。2.3 list Element access相比string/vector，链表不可使用下标访问元素，因此list没有[] 运算符的重载与at接口。只保留了front与back接口，返回首元素/尾元素的引用或const引用（reference或const_reference）。注：这里存在多次重命名，reference即value_type&，value_type即模板参数T，T即容器存储的元素类型。2.4 list 迭代器与迭代器分类list 迭代器迭代器接口与string/vector完全一致，包括正向迭代器begin/end与反向迭代器rbegin/rend，以及对应的const版本迭代器cbegin/cend/crbegin/crend。迭代器分类正向迭代器、反向迭代器以及const迭代器，都是从功能的角度划分迭代器。实际还可从性质的角度来划分，例如：随机迭代器 (Random-access iterator)：forward_list（单向/向前链表）、unordered_map、unordered_set。双向迭代器 (Bidirectional iterator)：list（双向循环链表）、map、set。单向迭代器 (Forward iterator)：vector、string、dequeue（双端队列）。底层结构决定性质，性质不同导致支持不同的运算符重载。例如这3类迭代器都可支持*/->/==/!=/=/++等运算符重载，但未必支持[]/+/-/--。随机迭代器：底层是数组，支持下标随机访问元素，同样支持单向或双向的顺序访问。因此可支持的运算符重载包括+/-/+=/-=/[]/--。双向迭代器：底层是双向链表，不支持随机访问，但支持顺序访问，可向前/向后遍历。因此可支持的运算符重载包括自减--，但不支持+/-/+=/-=/[]。单向迭代器：底层是单向链表，不可随机访问，只支持向前遍历。因此仅支持部分通用的运算符重载，例如自增++，但不支持+/-/+=/-=/[]/--。底层结构同样决定了可支持的算法。如算法库(algorithm) 中的逆置算法reverse，可反转序列次序，其实现为函数模板，模板参数名是BidirectionalIterator；又如排序算法sort，其实现为函数模板，模板参数名是RandomAccessIterator。前者支持双向迭代器，但随机迭代器也兼容；后者支持随机迭代器，不兼容双向迭代器/单向迭代器。sort底层是快排。快排算法递归深度越深，效率越低，为了优化，有三数取中，也有提前结束转堆排等措施，不管哪种，都需要支持[]，不然无法随机访问元素，而且堆排底层就是顺序表，这也是为什么sort只能支持随机迭代器。补充：包含关系：随机>双向>单向，可向上兼容但不可向下兼容。随机可以看作特殊的双向/单向，双向可看作特殊的单向，这种性质关系实际涉及到了继承的概念：子类是特殊的父类。其实这里还引申出了两个不存在的迭代器Input和Output，没有实体对应的迭代器，也称为只读迭代器和只写迭代器。这是抽象层的概念，它们并非任一容器的迭代器类型，实际用处不大，但确实存在这种设计，例如部分算法中可能出现InputIterator（一般不会出现OutputIterator），意味着可以兼容任意类型的迭代器，因为随机/双向/单向都是Input的子类，都是特殊的InputIterator（再次说明：抽象层概念上是继承关系但实际不存在Input这个类型）。代码示例 2.4.1#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试方法1 void test_list1() { std::list<int> lt1; // 向lt1中依次尾插4、3、2、1 lt1.push_back(4); lt1.push_back(3); lt1.push_back(2); lt1.push_back(1); // list 容器访问方式：迭代器（容器通用方式） std::list<int>::iterator it = lt1.begin(); std::cout << "lt1: "; while (it != lt1.end()) { // list 迭代器为Bidirectional iterators 双向迭代器 // 支持解引用*自增++自减--，但不支持加+减-以及方括号[]随机访问 std::cout << *it << " "; ++it; // lt1.erase(it + 3); // it+3 类似写法 list 不再支持，仅适用容器底层数据结构为连续空间的情况。 /* 顺序表，即数组，底层空间是连续的，如 string/vector，其迭代器类型可能就是原生 指针，指针本身就可以加减运算。即使不是原生指针，自定义类型想进行运算符重载也是很轻 松的。但链表不同，各结点空间分别开辟，基本是离散的，结点地址不连续，自然不支持指针 运算，即使重载具备可行性，也完全没有必要。*/ } std::cout << std::endl; // 性质决定可支持的运算符重载，同样决定了算法 // 1. 将待排序的元素存入 vector 对象 std::vector<int> v1(lt1.begin(), lt1.end()); // 2. 在 vector 中排好序 std::sort(v1.begin(), v1.end()); // 3. 将排序完的序列赋值给 list 对象 lt1.assign(v1.begin(), v1.end()); // 通过范围for访问：底层其实仍为迭代器 std::cout << "lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list1(); return 0; }运行结果：2.5 list Modifierslist Modifiers接口和string/vector Modifiers接口大体相似：assign：重新赋值，可用迭代器区间赋值或n个value赋值，替换原元素内容并根据新的元素个数、大小调整数组容量。此处list容器中是替换链表结点内容并根据元素个数调整结点个数，可能开辟或释放结点空间。push_back/emplace_back：这两个接口都是尾插。push_front/emplace_front：这两个接口都是头插。pop_back/pop_front：尾删/头删。insert/emplace：这两个接口都是在中间插入元素/结点。erase：删除指定元素/结点。swap：和另一list对象交换容器内容（元素/结点的值与个数）。补充：push系列和emplace系列功能基本是一致的，push系列有的emplace系列都有，甚至部分情况下emplace系列可能更高效些，但具体区别暂不讨论，涉及到右值引用、模板可变参数、右值引用和完美转发等内容，下面只讨论写法上的一些区别。代码示例 2.5.1#include <iostream> #include <list> class A { public: A(int a1 = 1, int a2 = 1) : _a1(a1) , _a2(a2) { std::cout << "A(int a1 = 1, int a2 = 1)" << std::endl; } A(const A& aa) : _a1(aa._a1) , _a2(aa._a2) { std::cout << "A(const A& aa)" << std::endl; } int _a1; int _a2; }; // 测试方法2 void test_list2() { // push_back/push_front支持的，emplace_back/emplace_front都支持 std::list<A> lt; // 构造有名对象插入list A aa1(1, 1); lt.push_back(aa1); lt.emplace_back(aa1); // 构造匿名对象插入list lt.push_back(A(2, 2)); lt.emplace_back(A(2, 2)); // emplace还支持直接传构造A对象的参数 lt.emplace_back(3, 3); // push_back/push_front 不支持这种写法，因为它们只有1个形参 // lt.push_back(3, 3); for (auto& e : lt) { std::cout << e._a1 << " " << e._a2 << std::endl; } } int main() { test_list2(); return 0; }运行结果：可以观察到，emplace_back直接传构造A对象的参数避免了一次形参的拷贝构造，不管是传匿名对象还是有名对象，都需要构造一次对象再拷贝构造一次形参对象，但直接传参数就只有一次构造。这类情况下，emlace系列也就比push系列更高效些。insert同理。代码示例 2.5.2#include <iostream> #include <list> #include <algorithm> // 测试方法3 void test_list3() { std::list<int> lt; // 依次向list对象中尾插1、2、3、4、5 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); // 链表不再支持随机访问，没有加+减-方括号[]等运算符的重载 // lt.insert(lt.begin() + 2, 10); // 加减运算直接访问指定位置的写法不再支持 // 只能先遍历查找到指定位置并用 it 记录，再向指定位置插入 std::list<int>::iterator it = lt.begin(); // it 指向第一个元素 int k = 2; while (k--) // ++两次指向第三个结点 { // 只支持自增++自减--，遍历查找，时间复杂度为 O(N) it++; } lt.insert(it, 10); // 在第三个元素前插入10，插入效率为 O(1) // 打印 list 对象 for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 输入 val 值 int val; std::cin >> val; // 使用 find 在 lt 中查找特定值 it = std::find(lt.begin(), lt.end(), val); if (it != lt.end()) { // 找到则在其位置上插入20 lt.insert(it, 20); } // 打印 list 对象 for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list3(); return 0; }运行结果：2.6 list Operationslist同样实现了逆置算法reverse成员函数，与算法库中的std::reverse实际是有点冗余的，因为逆置算法支持双向迭代器，list也是双向迭代器，直接使用算法库中的逆置算法即可。代码示例 2.6.1#include <iostream> #include <list> #include <algorithm> // 测试方法4 void test_list4() { std::list<int> lt; // 依次向list对象中尾插1、2、3、4、5、6 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); std::cout << "Before reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 使用 list 自己的逆置算法 reverse lt.reverse(); std::cout << "After std::list::reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 使用算法库的逆置算法 std::reverse std::reverse(lt.begin(), lt.end()); std::cout << "After std::reverse: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list4(); return 0; }运行结果：由于算法库中的排序算法sort只支持随机迭代器，list实现了自己的sort排序（具体实现细节暂不讨论，下面只介绍写法细节）。std::list::sort有两个重载，第一个是函数，第二个是函数模板。默认情况下，sort排升序（包括算法库中的sort），但可以传一个仿函数改为排升序，即形参comp。代码示例 2.6.2#include <iostream> #include <list> #include <algorithm> // 测试方法5 void test_list5() { std::list<int> lt; // 依次向list对象中尾插1、3、4、2、6、5 lt.push_back(1); lt.push_back(3); lt.push_back(4); lt.push_back(2); lt.push_back(6); lt.push_back(5); std::cout << "Before sort: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 算法库的 sort 算法不支持双向迭代器，使用 list 自己的排序算法 lt.sort(); // 默认为升序，但想传也可以传仿函数 less 指定排升序 std::cout << "After std::list::sort (less): "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // sort 默认排升序，可传一个仿函数改为排降序 // greater 大于> 排升序，less 小于< 排降序 std::greater<int> gt; // 构造仿函数对象需要指定元素类型 lt.sort(gt); // 也可传匿名对象 std::greater<int>() std::cout << "After std::list::sort (greater): "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list5(); return 0; }运行结果：list还支持合并算法，可以将两个list对象合并成一个链表，要求两个list对象都已有序（需确保同为升序或降序，且注意，merge同样可以传仿函数，指定合并为升序或降序，需与链表顺序一致）。合并方式其实就是从两个有序链表中，依次取极小值尾插，数据最终放入调用合并算法的容器中。需注意，合并后x链表就为空了，相当于把x链表的结点都移走了。代码示例 2.6.3#include <iostream> #include <list> #include <algorithm> // 测试方法6 void test_list6() { // 构造 list 对象 lt1：2、3、4、1 std::list<int> lt1; lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(1); // 构造 list 对象 lt2：4、3、1、2 std::list<int> lt2; lt2.push_back(4); lt2.push_back(3); lt2.push_back(1); lt2.push_back(2); std::cout << "Before sort, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nBefore sort, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; // 合并前需确保两个链表有序 lt1.sort(std::greater<int>()); lt2.sort(std::greater<int>()); std::cout << "After sort, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nAfter sort, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; // 合并链表，结果放入 lt1 中，合并后 lt2 链表为空 lt1.merge(lt2, std::greater<int>()); std::cout << "After merge, lt1: "; for (auto& e : lt1) { std::cout << e << " "; } std::cout << "\nAfter merge, lt2: "; for (auto& e : lt2) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list6(); return 0; }运行结果：list还支持去重算法unique。可去掉链表中的重复元素，只留下一个。同样要求数据必须有序。代码示例 2.6.4#include <iostream> #include <list> #include <algorithm> // 测试方法7 void test_list7() { // 构造 list 对象 lt：1、1、2、2、4、4、3、3 std::list<int> lt; lt.push_back(1); lt.push_back(1); lt.push_back(2); lt.push_back(2); lt.push_back(4); lt.push_back(4); lt.push_back(3); lt.push_back(3); std::cout << "Before sort, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 只能去重有序链表 lt.sort(); std::cout << "After sort, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; // 去重 lt.unique(); std::cout << "After unique, lt: "; for (auto& e : lt) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list7(); return 0; }运行结果：remove类似erase，但erase需要传迭代器，remove直接传指定值，类似先查找值val是否存在，存在则删，没找到则正常结束，不会报错。remove_if不是删除特定值，而是传一个仿函数，可根据某种规则删除，例如删除所有偶数或者删除所有小于10的数。splice即粘接或者说剪切算法。剪切另一个list对象x的链表结点，转移给调用剪切算法的list对象。重载（1）是剪切链表的全部结点到position位置（position及其后结点均后移）；重载（2）是剪切迭代器i指向的一个结点到position位置；重载（3）是剪切迭代器区间内的所有结点到position位置。代码示例 2.6.5#include <iostream> #include <list> #include <algorithm> // 测试方法8 void test_list8() { std::list<int> lt1, lt2; std::list<int>::iterator it; for (int i = 1; i <= 4; i++) lt1.push_back(i); // lt1：1、2、3、4 for (int i = 1; i <= 3; i++) lt2.push_back(i * 10); // lt2：10、20、30 it = lt1.begin(); // 指向1 it++; // 指向2 // 剪切 lt2 中所有结点到 lt1 的 it 位置 lt1.splice(it, lt2); // 1、10、20、30、2、3、4 for (auto &e : lt1) { std::cout << e << " "; } std::cout << std::endl; // 玩法二：调整当前链表结点顺序，在单个链表内部进行剪切与转移 // 输入指定值 val int val; std::cin >> val; // 查找 val 值的位置，并返回迭代器 it = std::find(lt1.begin(), lt1.end(), val); if (it != lt1.end()) { // 查找成功，将 val 值对应的结点调整到链表头 // iterator position: 插入到 lt1.begin() 链表头 // list& x: 剪切 lt1 的链表 // iterator i: 剪切迭代器 it 所指向的结点 lt1.splice(lt1.begin(), lt1, it); } for (auto& e : lt1) { std::cout << e << " "; } std::cout << std::endl; } int main() { test_list8(); return 0; }运行结果：2.7 list实现的sort的效率问题注意，不应在Debug下测试两个sort的性能差异，而应在Release下进行测试。因为标准库中实现的std::sort底层是快排，快排用的是递归，Debug下为了调试函数栈帧申请消耗的资源更多，整体效率更慢。实际上Debug下的性能测试并不具有参考性。代码示例 2.7.1#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试 std::list::sort 与 std::sort 的效率差异（不涉及拷贝） void test_sort() { srand(time(0)); const int N = 10000000; // 1千万 std::list<int> lt; std::vector<int> v; for (int i = 0; i < N; i++) { // 生成一千万个随机数分别存入 list 和 vector // rand 最多生成3万个不同的随机数，+i尽量避免重复 auto e = rand() + i; lt.push_back(e); v.push_back(e); } // 使用算法库的 sort 排序 int begin1 = clock(); std::sort(v.begin(), v.end()); int end1 = clock(); // 使用 list 的 sort 排序 int begin2 = clock(); lt.sort(); int end2 = clock(); // 分别打印两者排序的时间差 printf("std::sort: %d\n", end1 - begin1); printf("list sort: %d\n", end2 - begin2); } int main() { test_sort(); return 0; }测试结果，约3倍：代码示例 2.7.2#include <iostream> #include <list> #include <vector> #include <algorithm> // 测试 std::list::sort 与 std::sort 的效率差异（涉及拷贝） void test_sort2() { srand(time(0)); const int N = 10000000; // 1千万 std::list<int> lt1; std::list<int> lt2; for (int i = 0; i < N; i++) { // 生成一千万个随机数分别存入两个 list 对象 auto e = rand() + i; lt1.push_back(e); lt2.push_back(e); } // 使用算法库的 sort 排序 // 并且多1个拷贝操作，先将list中的数据拷贝到vector中 int begin1 = clock(); std::vector<int> v(lt1.begin(), lt1.end()); std::sort(v.begin(), v.end()); lt1.assign(v.begin(), v.end()); // 排序完再拷贝回来 int end1 = clock(); // 使用 list 的 sort 排序，且没有拷贝操作 int begin2 = clock(); lt2.sort(); int end2 = clock(); // 分别打印两者排序的时间差 printf("std::sort and copy: %d\n", end1 - begin1); printf("list sort no copy: %d\n", end2 - begin2); } int main() { test_sort2(); return 0; }测试结果，仍为3倍（同时可见拷贝效率还是挺可观的）：3. 模拟实现 list 容器头文件代码示例// STL容器list的模拟实现（核心接口） #pragma once #include<iostream> #include<assert.h> using namespace std; namespace fym { // 链表结点类 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) { } }; // list 迭代器 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 = nullptr) :_node(node) {} Ref operator*() { return _node->_data; } Ptr 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& l) const { return _node == l._node; } bool operator!=(const Self& l) const { return _node != l._node; } }; // list 类 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; public: void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() // 默认构造 { empty_init(); } list(const list<T>& lt) // 拷贝构造 { empty_init(); for (auto& e : lt) { push_back(e); } } list<T>& operator=(list<T> lt) // 赋值重载 { swap(lt); return *this; } ~list() // 析构 { clear(); delete _head; _head = nullptr; } list(initializer_list<T> il) // 列表构造 { // C++11规定：类似{1,2,3,4,5,6}列表类型为 std::initializer_list<T> /* initializer_list 底层在栈上开辟数组，有两个指针分别指向数组的开始和结束 ，因此 initializer_list 类型大小32位下为8字节，64位下为16字节。*/ empty_init(); // il 底层封装了一个列表 for (auto &e : il) { push_back(e); } } // Iterators iterator begin() { // 直接返回Node*，通过list_iterator的默认构造隐式类型转换成iterator return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } // Capacity size_t size() const { return _size; } bool empty() const { return _size == 0; } // Modifiers void clear() { auto it = begin(); while (it != end()) { it = erase(it); } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } iterator insert(iterator pos, const T& x) // pos位置插入值为x的结点 { Node* cur = pos._node; // 获取当前结点 Node* prev = cur->_prev; // 获取前驱结点 Node* newNode = new Node(x); // 构造1个新结点 // 调整前驱结点、当前结点、新结点的指向关系 newNode->_next = cur; cur->_prev = newNode; newNode->_prev = prev; prev->_next = newNode; ++_size; return newNode; } void push_back(const T& x){ insert(end(), x); } void push_front(const T& x){ insert(begin(), x); } iterator erase(iterator pos) // 删除pos结点，返回pos位置下一结点 { assert(pos != end()); // 避免删除空链表 Node* next = pos._node->_next; // 获取pos前驱结点 Node* prev = pos._node->_prev; // 获取pos后继结点 // 调整指向关系 next->_prev = prev; prev->_next = next; delete pos._node; // 释放pos结点 _size--; return next; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } private: Node* _head; size_t _size; }; };