1.list概述 List 并非 vector 与 string 那样连续的内存空间，list 每次插入或删除一个元素，都会新配置或释放一个元素的空间，所以list对于空间的使用很充分，一点也没有浪费，对于任意位置的插入或删除元素，时间复杂度都为O(1)，这是 list 相较于 vector 与 string 的优点。
list 与 vector 是我们常用的容器，选择使用哪个容器，要考虑元素的数量，元素是否需要多次访问，元素（构造/赋值）的复杂程度，对容器任意位置的插入或删除有需求。
2.list使用使用部分只有常用的接口才会详细解释，并且使用方法与vector，string重复的只通过语言描述
构造函数
1）默认构造：
第一种形式创建一个空的 list ，可指定分配器（默认使用系统分配器）
2）填充构造函数（fill (2)）
创建一个包含 n 个默认初始化元素的 list 。创建一个包含 n 个值为 val 元素的 list ，也可指定分配器。3） 范围构造函数（range (3)）：
使用迭代器范围 [first, last) 内的元素来初始化 list ，即将这些元素复制到新的 list 中，可指定分配器。
4）复制构造函数（copy (4)）：
第一种形式通过复制另一个 list x 来创建新的 list；第二种形式在指定分配器的情况下复制另一个 list x 。5）移动构造函数（move (5)）：
第一种形式通过移动另一个 list x 来创建新的 list，将 x 的资源转移到新 list ，x 变为有效但未指定状态；第二种形式在指定分配器的情况下进行移动构造。6）初始化列表构造函数（initializer list (6)）
使用初始化列表 il 中的元素来初始化 list ，可指定分配器。
赋值重载
1）复制赋值（copy (1)）
将 list 对象 x 的内容复制到当前 list 中。它会先释放当前 list 已有的内存空间（如果有），然后分配新的内存，再把 x 中的元素逐个复制过来。这是深拷贝操作，两个 list 对象有各自独立的内存存储元素。
2）移动赋值（move (2)）
将 list 对象 x 的资源（如内部节点指针等）移动到当前 list 中。x 会变为有效但未指定状态（通常其内部数据结构被置空等）。此操作是浅拷贝，不进行元素逐个复制，而是直接转移资源所有权，效率较高，适用于 x 不再需要的场景。
#include #include int main() { std::list l1 = {1, 2, 3}; std::list l2; l2 = std::move(l1); // 移动赋值，l2获取l1资源，l1变为有效但未指定状态 for (int i : l2) { std::cout << i << " "; } return 0;}
3）初始化列表赋值（initializer list (3)）
使用初始化列表 il 中的元素来重新初始化当前 list 。它会先释放当前 list 已有的内存，然后根据初始化列表中的元素个数分配内存，并将元素逐个复制（或移动，取决于元素类型）到当前 list 中。
迭代器beginReturn iterator to beginning (public member function )endReturn iterator to end (public member function )rbeginReturn reverse iterator to reverse beginning (public member function )rendReturn reverse iterator to reverse end (public member function )cbeginReturn const_iterator to beginning (public member function )cendReturn const_iterator to end (public member function )crbeginReturn const_reverse_iterator to reverse beginning (public member function )crendReturn const_reverse_iterator to reverse end (public member function ) list 迭代器在使用方法与接口拼写等方面与 vector string 相同不在重复解释
容量empty判断链表是否为空size返回链表元素个数max_size链表能够向内存申请多少个节点大小的空间，基本用不上元素访问front返回第一个元素back返回最后一个元素链表修改接口assigntemplate
使用迭代器范围 [first, last) 内的元素替换当前 list 的所有元素。list 会自动管理内存，根据新元素的数量调整大小。void assign (size_type n, const value_type& val);
将当前 list 的所有元素替换为 n 个值为 val 的元素。list 会根据 n 的大小调整自身容量。void assign (initializer_list
使用初始化列表 il 中的元素替换当前 list 的所有元素。list 会根据初始化列表的元素数量和内容进行调整。emplace_front与emplace_back
emplace_front 用于在 std::list 的头部直接构造并插入一个新元素。与 push_front 不同，push_front 是先创建一个临时对象，然后将其插入到列表头部（涉及对象拷贝或移动）；而 emplace_front 利用可变参数模板 Args&&... args ，直接在列表头部的内存位置，使用传入参数原位构造元素。这样避免了不必要的对象构造、拷贝或移动开销，在元素类型构造开销较大时能显著提高效率。
#include #include class MyClass {public: MyClass(int num, std::string str) : num_(num), str_(str) {}private: int num_; std::string str_;}; int main() { std::list myList; // 在list头部直接构造MyClass对象 myList.emplace_front(10, "hello"); return 0;}
与emplace_front类似，emplace_back是在尾部添加
#include #include class Person {public: Person(std::string name, int age) : name_(name), age_(age) {}private: std::string name_; int age_;}; int main() { std::list people; // 直接在list尾部构造Person对象 people.emplace_back("Alice", 25); return 0;}
插入删除push_back尾插pop_back尾删push_front头插pop_front头删insert
1）插入单个元素（single element (1)）：
在迭代器 position 所指向的元素之前插入一个值为 val 的新元素。由于 list 是双向链表，插入操作通过调整指针实现，不会影响其他元素的内存位置。函数返回指向新插入元素的迭代器。
#include #include int main() { std::list l = {1, 2, 3}; auto it = l.begin(); ++it; // 指向第二个元素 it = l.insert(it, 10); // 在第二个元素前插入10 for (int i : l) { std::cout << i << " "; } return 0;}
2） 插入多个相同元素（fill (2)）
在迭代器 position 所指向的元素之前插入 n 个值为 val 的元素。通过多次调整指针完成插入，返回指向第一个新插入元素的迭代器。
#include #include int main() { std::list l = {1, 2, 3}; auto it = l.begin(); it = l.insert(it, 2, 10); // 在开头插入2个10 for (int i : l) { std::cout << i << " "; } return 0;}
3）插入迭代器范围内元素（range (3)）：
将迭代器范围 [first, last) 内的元素插入到 position 所指向的元素之前。依次调整指针将范围内元素插入链表，返回指向第一个新插入元素的迭代器。
#include #include #include int main() { std::list l1 = {1, 2, 3}; std::vector v = {4, 5, 6}; auto it = l1.begin(); ++it; // 指向第二个元素 it = l1.insert(it, v.begin(), v.end()); // 在第二个元素前插入v的元素 for (int i : l1) { std::cout << i << " "; } return 0;}
4）移动插入单个元素（move (4)）：
在 position 所指向的元素之前插入一个值为 val 的新元素，采用移动语义，将 val 的资源移动到 list 中，原 val 进入有效但未指定状态。适用于避免不必要的拷贝，提高效率，返回指向新插入元素的迭代
#include #include int main() { std::list l = {1, 2, 3}; int x = 10; auto it = l.begin(); ++it; // 指向第二个元素 it = l.insert(it, std::move(x)); // 在第二个元素前移动插入x for (int i : l) { std::cout << i << " "; } return 0;}
5）插入初始化列表元素（initializer list (5)）：
将初始化列表 il 中的元素插入到 position 所指向的元素之前。按顺序调整指针插入元素，返回指向第一个新插入元素的迭代器。
#include #include int main() { std::list l = {1, 2, 3}; auto it = l.begin(); ++it; // 指向第二个元素 it = l.insert(it, {4, 5, 6}); // 在第二个元素前插入初始化列表元素 for (int i : l) { std::cout << i << " "; } return 0;}
eraseiterator erase (const_iterator position);
删除迭代器位置的元素iterator erase (const_iterator first, const_iterator last);
删除一段迭代器区间resizevoid resize (size_type n);
将 list 的大小调整为 n 个元素。
若 n 小于当前 list 大小，会删除从第 n 个元素开始的多余元素。若 n 大于当前 list 大小，会在 list 尾部添加默认初始化的元素，使 list 大小达到 n 。这里元素的默认初始化遵循其类型的默认构造规则，比如 int 类型默认初始化为 0 ，自定义类型若有默认构造函数则调用默认构造函数进行初始化。void resize (size_type n, const value_type& val);
若 n 小于当前 list 大小，同样删除从第 n 个元素开始的多余元素。若 n 大于当前 list 大小，会在 list 尾部添加值为 val 的元素，使 list 大小达到 n clear清理数据
链表操作接口splice
1）移动整个链表：将列表 x 的所有元素移动到当前列表中 position 所指向的元素之前。移动后，列表 x 变为空列表。此操作通过调整内部节点的指针来实现，效率很高，因为没有进行元素的拷贝或构造，只是改变了元素的归属关系。
#include #include int main() { std::list l1 = {1, 2, 3}; std::list l2 = {4, 5, 6}; auto it = l1.begin(); l1.splice(it, l2); // 将l2的所有元素移动到l1的开头 for (int i : l1) { std::cout << i << " "; } std::cout << "\nl2 size: " << l2.size() << std::endl; // l2大小为0 return 0;}
2）移动单个元素：将列表 x 中由迭代器 i 指向的单个元素移动到当前列表中 position 所指向的元素之前。移动后，该元素从列表 x 中移除。同样是通过调整指针来完成操作，不会涉及元素的拷贝构造。
#include #include int main() { std::list l1 = {1, 2, 3}; std::list l2 = {4, 5, 6}; auto it1 = l1.begin(); auto it2 = l2.begin(); ++it2; // 指向l2的第二个元素 l1.splice(it1, l2, it2); // 将l2的第二个元素移动到l1的开头 for (int i : l1) { std::cout << i << " "; } std::cout << "\nl2: "; for (int i : l2) { std::cout << i << " "; } return 0;}
3）移动迭代器范围内的元素：将列表 x 中迭代器范围 [first, last) 内的元素移动到当前列表中 position 所指向的元素之前。移动后，这些元素从列表 x 中移除。通过依次调整范围内元素节点的指针来实现移动操作。
#include #include int main() { std::list l1 = {1, 2, 3}; std::list l2 = {4, 5, 6, 7, 8}; auto it1 = l1.begin(); auto it2_first = l2.begin() + 1; auto it2_last = l2.begin() + 3; l1.splice(it1, l2, it2_first, it2_last); // 将l2中索引1到2的元素移动到l1的开头 for (int i : l1) { std::cout << i << " "; } std::cout << "\nl2: "; for (int i : l2) { std::cout << i << " "; } return 0;}
remove
remove 函数用于从 std::list 中移除所有值等于 val 的元素 。它会遍历整个 list，逐个检查元素是否与给定值 val 相等，若相等则将其从 list 中删除。此操作通过调整链表节点的指针来实现，不会涉及额外的元素拷贝或构造。
#include #include int main() { std::list l = {1, 2, 3, 2, 4, 2}; l.remove(2); // 移除list中所有值为2的元素 for (int i : l) { std::cout << i << " "; } return 0;}
remove_if
remove_if 函数用于从 std::list 中移除满足特定条件的所有元素。其中 Predicate 是一个可调用对象（如函数指针、函数对象、lambda 表达式等），它接受一个 list 元素类型的参数，并返回 bool 类型的值。remove_if 会遍历整个 list，对每个元素应用 pred，若 pred 返回 true，则该元素会被从 list 中移除。通过调整链表节点的指针实现元素移除，不涉及额外的元素拷贝或构造。
#include #include bool is_even(int num) { return num % 2 == 0;} int main() { std::list l = {1, 2, 3, 4, 5}; l.remove_if(is_even); // 移除list中所有偶数 for (int i : l) { std::cout << i << " "; } return 0;}
unique
1) 移除 list 中所有相邻的重复元素。它会从列表的第二个元素开始，依次与前一个元素进行比较（使用元素类型的 operator== 进行比较），如果相等则移除当前元素，直到遍历完整个列表。
#include #include int main() { std::list l = {1, 1, 2, 2, 3, 2, 3}; l.unique(); for (int i : l) { std::cout << i << " "; } return 0;}
2）根据自定义的二元判断条件 binary_pred 来移除相邻的重复元素。binary_pred 是一个可调用对象（如函数指针、函数对象、lambda 表达式等），它接受两个 list 元素类型的参数，并返回 bool 类型的值。unique 会使用 binary_pred 对相邻元素进行比较，如果 binary_pred 返回 true ，则移除后面的元素。
#include #include int main() { std::list l = {1, 2, 3, 2, 1}; l.unique([](int a, int b) { return a + b == 3; }); for (int i : l) { std::cout << i << " "; } return 0;}
这里定义的 lambda 表达式 [](int a, int b) { return a + b == 3; } 表示当相邻两个元素之和为 3 时，认为它们是 “重复” 的，会移除后面的元素。输出可能为 1 2 2 1 （具体输出顺序取决于实现细节）。
merge
1）将列表 x 合并到当前列表中，要求当前列表和 x 列表在合并前都已经按元素类型的默认比较规则（通常是 operator< ）排好序。合并后，x 列表变为空列表，当前列表包含了两个列表原来的所有元素，并且仍然是有序的。
#include #include int main() { std::list l1 = {1, 3, 5}; std::list l2 = {2, 4, 6}; l1.merge(l2); for (int i : l1) { std::cout << i << " "; } std::cout << "\nl2 size: " << l2.size() << std::endl; // l2大小为0 return 0;}
2）按照用户自定义的比较规则 comp ，将列表 x 合并到当前列表中。Compare 是一个可调用对象（如函数指针、函数对象、lambda 表达式等），它接受两个元素类型的参数，并返回 bool 类型的值，用于判断两个元素的顺序关系。同样，合并前两个列表都应是有序的（按 comp 规则），合并后 x 列表为空，当前列表包含两个列表的所有元素且有序。
#include #include int main() { std::list l1 = {3, 2, 1}; std::list l2 = {6, 5, 4}; l1.merge(l2, [](int a, int b) { return a > b; }); // 按从大到小的顺序合并 for (int i : l1) { std::cout << i << " "; } std::cout << "\nl2 size: " << l2.size() << std::endl; // l2大小为0 return 0;}
reverse使链表反向
sort这是list的迭代器类型：双向迭代器
这是算法库中的sort函数，算法库函数模板要求的迭代器类型为随机迭代器
该sort算法的原理是快速排序，要求迭代器能够随机访问
单项迭代器：
单向迭代器：（单项链表）单向迭代器指该容器的迭代器只能++双向迭代器：（双向链表）双向迭代器指该容器的迭代器可以++/--随机迭代器：（vector/string）随机迭代器既能++/--，也能+n。
单向迭代器的参数可以传单向，双向和随机迭代器；
双向迭代器参数可以传双向和随机迭代器；
随机迭代器只能传随机迭代器
由上可知，因为 list 的空间是不连续的，它的迭代器是双向迭代器，所以不能使用算法库中的sort函数，而 list 中的sort使用的是归并排序的原理
以下代码展示了 list 自带的 sort 接口与算法库中 sort 的效率对比：
void test_op1(){ srand(time(0)); const int N = 1000000; list lt1; vector v; for (int i = 0; i < N; ++i) { auto e = rand() + i; lt1.push_back(e); v.push_back(e); } int begin1 = clock(); // 排序 sort(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); lt1.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1);//vector sort:22//100w数据时vector sort:256 printf("list sort:%d\n", end2 - begin2);//list sort:28//100w数据时list sort:386}
针对这个代码：
电脑配置不同，每次代码的运行都可能使这个运行时间有所误差，但数量级都是一样的算法库中的sort排序效率更快所以如果只是想排序，更建议使用vector，虽然我想这么说，但事实并非如此，请看以下代码
srand(time(0)); const int N = 1000000; list lt1; vector v; list lt2; for (int i = 0; i < N; ++i) { auto e = rand() + i; lt1.push_back(e); lt2.push_back(e); } int begin1 = clock(); for (auto& e : lt2) { v.push_back(e); } lt2.clear(); sort(v.begin(), v.end()); for (auto& e : v) { lt2.push_back(e); } int end1 = clock(); int begin2 = clock(); lt1.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2);
首先我们要知道用户拿到的代码调试版本是Release版本，release版本移除了调试信息，以及对栈帧的压缩快排递归建立栈帧相对较多，同时调试信息也比较多，在debug版本中这种赋值，排序，再赋值回来的代码，效率不如直接使用list的sort接口但是在Release版本中，编译器会将符合条件的尾递归转换为循环，避免栈帧累积。这样就使得快排建立栈帧的劣势变为优势，而且快排本身就比归并快。总结： list 自带的排序接口基本用不上。
3.list原理解析及模拟实现3.1list的节点 list 类本身和 list 节点是不同的结构
list 类本身是对 list 这种数据结构的使用方法（增删查改等）的封装，list类的成员为list节点类。节点则是单独一个类，而且在list类中，需要经常访问list的节点中的数据（数据，上一个节点指针，下一个节点指针），所以list节点类为struct，访问限定默认为共有。
struct List_node{ T _data; List_node* _prev; List_node* _next; List_node(const T& data=T()) :_data(data),_prev(nullptr),_next(nullptr){ } };
该代码为模拟实现。
3.2list的迭代器 list的迭代器不能像vector那样简单的把模板类型(T)指针typedef为iterator，因为list节点在内存中不连续存在。
链表对迭代器的要求：
迭代器指向list的节点迭代器递增时指向下一个节点，递减时指向前一个节点。解引用时取到的是节点的数据值，成员取用时必须是节点的成员 由于STLlist是一个双向链表（double linked-list)，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterators。
list 的插入（insert）和结合（splice）操作都不会造成原有 list 迭代器失效，因为list每插入一个节点都是从内存中新申请的，在该节点与其他节点连接时不会导致其他节点的地址发生变化。甚至list的删除操作也只有，指向被删除的元素的迭代器失效，其他迭代器不受影响。
list迭代器重载->的二重解引用性质 在 C++ 中，重载的->操作符具有独特的二重解引用性质，这使得它与其他操作符的重载行为不同。这种特性源于 C++ 标准对->操作符的特殊规定：当->被重载时，其返回值必须是一个指针或另一个重载了->的对象，并且该过程会递归进行，直到最终返回一个原始指针。
->的二重解引用原理
当对象obj重载了->操作符时，表达式obj->member的执行分为两个步骤：
第一次解引用：调用obj.operator->()，返回一个中间对象intermediate。递归应用->：对intermediate继续应用->操作符，直到返回一个原始指针raw_ptr，最终通过raw_ptr->member访问成员。关键点：
重载的->必须返回一个指针或另一个可解引用的对象。递归解引用由编译器自动完成，无需手动编写嵌套调用。
struct Data { int value;}; class Wrapper {private: Data* data;public: Wrapper(Data* d) : data(d) {} Data* operator->() const { return data; } Data& operator*() const { return *data; }}; int main() { Data d{42}; Wrapper w(&d); w->value; // 等价于 (w.operator->())->value (*w).value; // 等价于 w.operator*().value}
3.3list的模拟实现
#pragma#include#include using namespace std; namespace wxList{ template struct List_node { T _data; List_node* _prev; List_node* _next; List_node(const T& data=T()) :_data(data),_prev(nullptr),_next(nullptr){ } }; template struct __list_iterator { typedef List_node Node; typedef __list_iterator self; Node* _node; __list_iterator(Node* node) :_node(node){ } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tem(*this); _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tem(*this); _node = _node->_prev; return *this; } Ptr operator->() { return &(_node->_data); } Ref operator*() { return _node->_data; } bool operator!=(const self& it) const { return (_node != it._node); } bool operator==(const self& it) const { return (_node == it._node); } }; template class list { typedef List_node Node; public: typedef __list_iterator iterator; typedef __list_iterator const_iterator; list() { empty(); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } list(const list& li) { empty(); for (const auto& e: li) { push_back(e); } _size = li.size(); } list(initializer_list il) { empty(); for (const auto& e : il) { push_back(e); } _size = il.size(); } void swap(list& li) { std::swap(_head, li._head); std::swap(_size, li._size); } list& operator=(list li) { swap(li); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& x ) { Node* tem = pos._node->_prev; Node* temnext = pos._node; Node* newnode = new Node(x); tem->_next = newnode; newnode->_prev = tem; temnext->_prev = newnode; newnode->_next = temnext; _size++; return iterator(newnode); } iterator erase(iterator pos) { Node* tem1 = pos._node->_prev; Node* tem2 = pos._node->_next; tem1->_next = tem2; tem2->_prev = tem1; _size--; delete pos._node; return iterator(tem2); } size_t size() const { return _size; } void empty() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } private: Node* _head; size_t _size; };}