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::listint lt1; // 无需传参即可初始化 // 2、n个val带参构造 std::listchar lt2(5, a); // 向list对象中插入5个字符a // 3、迭代器区间构造区间[第二个元素末尾元素)左闭右开最终取中间3个元素 std::listchar lt3(lt2.begin(), --lt2.end()); // 迭代器区间初始化lt3 // 4、拷贝构造 std::listchar 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/vectorlist没有扩容方面的接口因为链表由一个个结点构成没有扩容的概念数组才需要扩容。例如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_typevalue_type即模板参数TT即容器存储的元素类型。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::listint lt1; // 向lt1中依次尾插4、3、2、1 lt1.push_back(4); lt1.push_back(3); lt1.push_back(2); lt1.push_back(1); // list 容器访问方式迭代器容器通用方式 std::listint::iterator it lt1.begin(); std::cout lt1: ; while (it ! lt1.end()) { // list 迭代器为Bidirectional iterators 双向迭代器 // 支持解引用*自增自减--但不支持加减-以及方括号[]随机访问 std::cout *it ; it; // lt1.erase(it 3); // it3 类似写法 list 不再支持仅适用容器底层数据结构为连续空间的情况。 /* 顺序表即数组底层空间是连续的如 string/vector其迭代器类型可能就是原生 指针指针本身就可以加减运算。即使不是原生指针自定义类型想进行运算符重载也是很轻 松的。但链表不同各结点空间分别开辟基本是离散的结点地址不连续自然不支持指针 运算即使重载具备可行性也完全没有必要。*/ } std::cout std::endl; // 性质决定可支持的运算符重载同样决定了算法 // 1. 将待排序的元素存入 vector 对象 std::vectorint 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::listA 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::listint 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::listint::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::listint 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::listint 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::greaterint gt; // 构造仿函数对象需要指定元素类型 lt.sort(gt); // 也可传匿名对象 std::greaterint() 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 对象 lt12、3、4、1 std::listint lt1; lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(1); // 构造 list 对象 lt24、3、1、2 std::listint 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::greaterint()); lt2.sort(std::greaterint()); 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::greaterint()); 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 对象 lt1、1、2、2、4、4、3、3 std::listint 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::listint lt1, lt2; std::listint::iterator it; for (int i 1; i 4; i) lt1.push_back(i); // lt11、2、3、4 for (int i 1; i 3; i) lt2.push_back(i * 10); // lt210、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::listint lt; std::vectorint 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::listint lt1; std::listint 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::vectorint 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 #includeiostream #includeassert.h using namespace std; namespace fym { // 链表结点类 templateclass T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T data T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; // list 迭代器 templateclass T, class Ref, class Ptr struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT, 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 类 templateclass T class list { typedef list_nodeT Node; public: typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, 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 listT lt) // 拷贝构造 { empty_init(); for (auto e : lt) { push_back(e); } } listT operator(listT lt) // 赋值重载 { swap(lt); return *this; } ~list() // 析构 { clear(); delete _head; _head nullptr; } list(initializer_listT il) // 列表构造 { // C11规定类似{1,2,3,4,5,6}列表类型为 std::initializer_listT /* 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(listT 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; }; };