目录一. 认识 list1.1 list 和 vector 的核心区别1.1.1 对比总结二. list 的使用2.1 list 的构造2.2 list 的迭代器2.2.1 迭代器的知识补充2.3 list 的其他函数接口2.4 list 的增删查改2.4.1 list 的增2.4.1.1 push_back() 和 push_front()2.4.1.2 insert2.4.2 list 的删2.4.2.1 pop_back() 和 pop_front()2.4.2.2 erase2.4.3 list 的查2.5 其他常用的函数接口2.5.1 reverse2.5.2 sort三. list 迭代器失效四. initializer_list4.1 认识 initializer_list4.2 代码示例五. list 的实现5.1 list 的构造和赋值运算符重载5.2 迭代器的实现5.3 list 的插入5.4 list 的删除5.5 析构、clear()一. 认识 listlist的本质是双向循环链表且带有一个哨兵位头结点(不存储 有效数据)结构如下双向每个字节包含前驱指针 (prev) 和后继指针 (next) 支持向前向后遍历循环尾节点的 next 指向头结点头结点的 prev 指向尾结点形成闭环哨兵位头结点避免插入/删除时判断是否为空”是否为头结点“的麻烦简化代码逻辑。1.1 list 和 vector 的核心区别对比项list双向链表vector动态数组底层结构每个元素都是独立节点通过prev和next指针连接内存不连续一块连续内存空间存储元素类似可自动扩容的数组插入/删除效率已知迭代器位置时效率高插入删除只需修改前后节点指针时间复杂度 O(1)中间插入或删除需要移动后面的元素时间复杂度 O(N)尾部插入平均 O(1)随机访问不支持下标访问需要从头或尾遍历寻找元素时间复杂度 O(N)支持operator[]和at()可以根据下标直接定位时间复杂度 O(1)迭代器特点插入、删除节点后其他元素的迭代器通常不会失效只影响被删除节点扩容时会重新分配内存导致全部迭代器失效非扩容插入会使插入位置之后的迭代器失效空间利用每个节点额外保存两个指针内存开销较大节点分散可能造成缓存不友好存储空间连续额外空间主要来自预留容量缓存命中率更高适用场景频繁在任意位置插入、删除并且不需要随机访问需要大量访问元素、遍历数据、尾部添加元素查找效率查找必须遍历链表时间复杂度 O(N)支持随机定位但普通查找仍为 O(N)排序操作有成员函数sort()利用链表结构避免大量移动元素通常使用算法库sort()依靠连续内存获得更好的性能1.1.1 对比总结如果程序主要进行中间位置频繁插入和删除并且不经常通过下标访问list更合适。如果程序主要进行随机访问、遍历以及尾部插入优先考虑vector。实际开发中vector往往是默认选择因为连续内存带来的缓存优势通常比链表的插入优势更明显。二. list 的使用2.1 list 的构造构造函数接口说明代码示例list()构造空listlistint l1;空链表仅含头结点list(size_type n, const T val T())构造包含n个val的listlistint l2(5, 3);元素3,3,3,3,3list(const list x)拷贝构造listint l3(l2);l3 是 l2 的副本list(InputIterator first, InputIterator last)使用[first,last)区间构造int arr[] {1,2,3}; listint l4(arr, arr3);元素1,2,3#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint a1; Print_List(a1); listint a2(3, 4); Print_List(a2); listint a3(a2); Print_List(a3); listint a4(a, a sizeof(a) / sizeof(a[0])); Print_List(a4); return 0; }2.2 list 的迭代器list 的迭代器使用和string、vector 几乎没有差别这里就不再赘述。#include iostream using namespace std; #include list int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); //正向遍历 auto it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; //反向遍历 auto _it dict.rbegin(); while (_it ! dict.rend()) { cout *_it ; _it; } cout endl; return 0; }2.2.1 迭代器的知识补充迭代器可以按功能和性质划分功能iterator、reverse_iterator、const_iterator、const_reverse_iterator。性质单向forward_list / unordered_map..... 双向list / map / set.... / - -随机vector / string /deque.... / - - / / -我们也可以在 cpluplus 网站上查看不同迭代器的性质2.3 list 的其他函数接口list 也提供函数size()、clear()、empty()、resize()。但是并没有提供 capacity()、reserve()、shrink_to_fit()。函数声明接口说明代码示例基于l4 {1,2,3,4}size()返回list中有效元素的个数返回类型为无符号整数size_typel4.size();返回4表示l4中有 4 个元素clear()清空list中的所有元素执行后size()变为0l4.clear();执行后l4变为空链表{}empty()检测list是否为空空返回true非空返回falsel4.empty();返回false因为l4中有 4 个元素resize(size_type n, T val T())调整list中有效元素的个数若n size()新增元素并初始化为val若n size()删除多余元素l4.resize(6, 10);修改后l4为{1,2,3,4,10,10}在访问元素方面list 并没有重载[ ] 和 atlist 不支持随机访问而是和 string、vector 一样提供front()、back()访问首尾元素。函数声明接口说明代码示例基于l4 {1,2,3,4}front()返回list第一个元素的引用可用于访问或修改首元素l4.front();返回第一个元素1也可以通过l4.front() 10;修改back()返回list最后一个元素的引用可用于访问或修改尾元素l4.back();返回最后一个元素4也可以通过l4.back() 20;修改2.4 list 的增删查改2.4.1 list 的增2.4.1.1 push_back() 和 push_front()#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); dict.push_back(100); dict.push_front(200); Print_List(dict); return 0; }2.4.1.2 insert#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); dict.insert(dict.begin(), 100); Print_List(dict); dict.insert(dict.begin(),3, 11); Print_List(dict); dict.insert(dict.begin(), a, a sizeof(a) / sizeof(a[0])); Print_List(dict); return 0; }2.4.2 list 的删2.4.2.1 pop_back() 和 pop_front()#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); dict.pop_back(); Print_List(dict); dict.pop_front(); Print_List(dict); return 0; }2.4.2.2 erase#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); dict.erase(dict.begin()); Print_List(dict); dict.erase(dict.begin(),--dict.end()); Print_List(dict); return 0; }2.4.3 list 的查list 和 vector 一样只能使用标准库里的 find():#include iostream using namespace std; #include list int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); listint::iterator it find(dict.begin(), dict.end(), 10); if (it ! dict.end()) { cout 找到了 *it endl; } else { cout 没找到 endl; } return 0; }2.5 其他常用的函数接口2.5.1 reverse#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); Print_List(dict); dict.reverse(); Print_List(dict); return 0; }但是这个函数的实现有点多余我们可以像 string、vector 一样使用标准库的 reverse():而且我们发现标准库的 reverse() 要求至少是双向迭代器不用担心 list 不能使用#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,2,3,4,5,6,7,8,9 }; listint dict(a, a sizeof(a) / sizeof(a[0])); Print_List(dict); reverse(dict.begin(), dict.end()); Print_List(dict); return 0; }2.5.2 sort标准库的 sort 要求迭代器至少是随机迭代器那么 list 是使用不了的 。所以 list 自己实现了 sort#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,4,3,7,5,10,50,8,40 }; listint dict(a, a sizeof(a) / sizeof(a[0])); Print_List(dict); dict.sort(); Print_List(dict); return 0; }三. list 迭代器失效list 和 vector 不一样insert 的时候迭代器不会失效但是 erase 的时候会失效#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,4,3,7,5,10,50,8,40 }; listint dict(a, a sizeof(a) / sizeof(a[0])); auto it dict.begin(); dict.insert(it, -10); Print_List(dict); //迭代器并没有失效仍然指向值为1的节点 dict.insert(it, 100); Print_List(dict); return 0; }#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { int a[] { 1,4,3,7,5,10,50,8,40 }; listint dict(a, a sizeof(a) / sizeof(a[0])); auto it dict.begin(); dict.erase(it); Print_List(dict); //值为1的节点被删除it指向的位置被释放,迭代器失效 dict.erase(it); Print_List(dict); return 0; }四. initializer_list在 C11 中支持用 initializer_list 来构造 list:4.1 认识 initializer_listinitializer_list 是 C11 为{}语法准备的中间桥梁它本身不负责存数据只保存编译器生成的临时数组的访问信息让 vector、list、自定义类都能支持{1,2,3}这种初始化方式。4.2 代码示例#include iostream using namespace std; #include list templateclass Container void Print_List( Container con) { typename Container::iterator it con.begin(); while (it ! con.end()) { cout *it ; it; } cout endl; } int main() { listint dict({ 1,2,3,4,5 }); Print_List(dict); return 0; }initializer_list的构造过程是当编译器遇到{1,2,3}这种初始化列表时会先创建一个隐藏的const数组保存元素然后构造一个initializer_list对象让它保存数组的首地址和大小。initializer_list本身不存储数据只是对这块临时数组的只读访问所以其中的元素不能修改。#include iostream #include initializer_list using namespace std; void Print(initializer_listint il) { for (auto e : il) cout e ; } int main() { initializer_listint il {1, 2, 3}; Print({4, 5, 6}); }大致过程{1,2,3} ↓ 生成隐藏数组 const int temp[]{1,2,3} ↓ initializer_list保存temp地址和大小 ↓ 通过begin/end访问元素五. list 的实现5.1 list 的构造和赋值运算符重载void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } list(initializer_listT il) { empty_init(); for (auto e : il) { push_back(e); } } list(const listT It) { empty_init(); for (auto it : It) { push_back(it); } } void swap( listT It) { std::swap(this-_head, It._head); std::swap(this-_size, It._size); } listT operator( listT It) { swap(It); return *this; }5.2 迭代器的实现templateclass T,class Ref,class Ptr struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT, Ref, Ptr Self; list_iterator(Node* node) :_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-_prev; return tmp; } Self operator(int) { Self tmp *this; _node _node-_next; return tmp; } bool operator(const Self v)const { return _node v._node; } bool operator!(const Self v)const { return _node ! v._node; } Node* _node; }; templateclass T class list { typedef list_nodeT Node; public: typedef list_iteratorT, T, T* iterator; typedef list_iterator T, const T, const T* const_iterator; iterator begin() { iterator it(_head-_next); return it; } const_iterator begin()const { const_iterator it(_head-_next); return it; } iterator end() { return iterator (_head); } const_iterator end()const { return const_iterator (_head); } private Node* _head; size_t _size; }5.3 list 的插入void push_back(const T val ) { Node* newnode new Node(val); newnode-_prev _head-_prev; newnode-_next _head; _head-_prev-_next newnode; _head-_prev newnode; _size; } void push_front(const T val) { insert(begin(), val); } iterator insert(iterator it, const T x) { Node* newnode new Node(x); newnode-_prev it._node-_prev; newnode-_next it._node; it._node-_prev-_next newnode; it._node-_prev newnode; _size; return newnode; }5.4 list 的删除void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator erase(iterator pos) { assert(pos ! end()); iterator it pos._node-_next; pos._node-_prev-_next pos._node-_next; pos._node-_next-_prev pos._node-_prev; delete pos._node; _size--; return it; }5.5 析构、clear()~list() { clear(); delete _head; _head nullptr; } void clear() { iterator it begin(); while (it ! end()) { erase(it); } }