1.list概述

    List 并非 vector 与 string 那样连续的内存空间，list 每次插入或删除一个元素，都会新配置或释放一个元素的空间，所以list对于空间的使用很充分，一点也没有浪费，对于任意位置的插入或删除元素，时间复杂度都为O(1)，这是 list 相较于 vector 与 string 的优点。

    list 与 vector 是我们常用的容器，选择使用哪个容器，要考虑元素的数量，元素是否需要多次访问，元素（构造/赋值）的复杂程度，对容器任意位置的插入或删除有需求。

2.list使用

使用部分只有常用的接口才会详细解释，并且使用方法与vector，string重复的只通过语言描述

构造函数

1）默认构造：

    第一种形式创建一个空的 list ，可指定分配器（默认使用系统分配器）

2）填充构造函数（fill (2)）

1. 创建一个包含 n 个默认初始化元素的 list 。
2. 创建一个包含 n 个值为 val 元素的 list ，也可指定分配器。

3） 范围构造函数（range (3)）：

       使用迭代器范围 [first, last) 内的元素来初始化 list ，即将这些元素复制到新的 list 中，可指定分配器。

4）复制构造函数（copy (4)）：

1. 第一种形式通过复制另一个 list x 来创建新的 list；
2. 第二种形式在指定分配器的情况下复制另一个 list x 。

5）移动构造函数（move (5)）：

1. 第一种形式通过移动另一个 list x 来创建新的 list，将 x 的资源转移到新 list ，x 变为有效但未指定状态；
2. 第二种形式在指定分配器的情况下进行移动构造。

6）初始化列表构造函数（initializer list (6)）

    使用初始化列表 il 中的元素来初始化 list ，可指定分配器。

赋值重载

1）复制赋值（copy (1)）

    将 list 对象 x 的内容复制到当前 list 中。它会先释放当前 list 已有的内存空间（如果有），然后分配新的内存，再把 x 中的元素逐个复制过来。这是深拷贝操作，两个 list 对象有各自独立的内存存储元素。

2）移动赋值（move (2)）

    将 list 对象 x 的资源（如内部节点指针等）移动到当前 list 中。x 会变为有效但未指定状态（通常其内部数据结构被置空等）。此操作是浅拷贝，不进行元素逐个复制，而是直接转移资源所有权，效率较高，适用于 x 不再需要的场景。

#include <list>
#include <iostream>int main() {std::list<int> l1 = {1, 2, 3};std::list<int> 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 中。

迭代器

begin	Return iterator to beginning (public member function )
end	Return iterator to end (public member function )
rbegin	Return reverse iterator to reverse beginning (public member function )
rend	Return reverse iterator to reverse end (public member function )
cbegin	Return const_iterator to beginning (public member function )
cend	Return const_iterator to end (public member function )
crbegin	Return const_reverse_iterator to reverse beginning (public member function )
crend	Return const_reverse_iterator to reverse end (public member function )

    list 迭代器在使用方法与接口拼写等方面与 vector string 相同不在重复解释

容量

empty	判断链表是否为空
size	返回链表元素个数
max_size	链表能够向内存申请多少个节点大小的空间，基本用不上

元素访问

front	返回第一个元素
back	返回最后一个元素

链表修改接口

assign

template <class InputIterator>   void assign (InputIterator first, InputIterator last);	使用迭代器范围 [first, last) 内的元素替换当前 list 的所有元素。list 会自动管理内存，根据新元素的数量调整大小。
void assign (size_type n, const value_type& val);	将当前 list 的所有元素替换为 n 个值为 val 的元素。list 会根据 n 的大小调整自身容量。
void assign (initializer_list<value_type> il);	使用初始化列表 il 中的元素替换当前 list 的所有元素。list 会根据初始化列表的元素数量和内容进行调整。

emplace_front与emplace_back

  emplace_front 用于在 std::list 的头部直接构造并插入一个新元素。与 push_front 不同，push_front 是先创建一个临时对象，然后将其插入到列表头部（涉及对象拷贝或移动）；而 emplace_front 利用可变参数模板 Args&&... args ，直接在列表头部的内存位置，使用传入参数原位构造元素。这样避免了不必要的对象构造、拷贝或移动开销，在元素类型构造开销较大时能显著提高效率。

#include <list>
#include <string>class MyClass {
public:MyClass(int num, std::string str) : num_(num), str_(str) {}
private:int num_;std::string str_;
};int main() {std::list<MyClass> myList;// 在list头部直接构造MyClass对象myList.emplace_front(10, "hello"); return 0;
}

    与emplace_front类似，emplace_back是在尾部添加

#include <list>
#include <string>class Person {
public:Person(std::string name, int age) : name_(name), age_(age) {}
private:std::string name_;int age_;
};int main() {std::list<Person> 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 <list>
#include <iostream>
int main() {std::list<int> l = {1, 2, 3};auto it = l.begin();++it; // 指向第二个元素it = l.insert(it, 10); // 在第二个元素前插入10for (int i : l) {std::cout << i << " ";}return 0;
}

2） 插入多个相同元素（fill (2)）

    在迭代器 position 所指向的元素之前插入 n 个值为 val 的元素。通过多次调整指针完成插入，返回指向第一个新插入元素的迭代器。

#include <list>
#include <iostream>
int main() {std::list<int> l = {1, 2, 3};auto it = l.begin();it = l.insert(it, 2, 10); // 在开头插入2个10for (int i : l) {std::cout << i << " ";}return 0;
}

3）插入迭代器范围内元素（range (3)）：

    将迭代器范围 [first, last) 内的元素插入到 position 所指向的元素之前。依次调整指针将范围内元素插入链表，返回指向第一个新插入元素的迭代器。

#include <list>
#include <vector>
#include <iostream>
int main() {std::list<int> l1 = {1, 2, 3};std::vector<int> 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 <list>
#include <iostream>
int main() {std::list<int> l = {1, 2, 3};int x = 10;auto it = l.begin();++it; // 指向第二个元素it = l.insert(it, std::move(x)); // 在第二个元素前移动插入xfor (int i : l) {std::cout << i << " ";}return 0;
}

5）插入初始化列表元素（initializer list (5)）：

    将初始化列表 il 中的元素插入到 position 所指向的元素之前。按顺序调整指针插入元素，返回指向第一个新插入元素的迭代器。

#include <list>
#include <iostream>
int main() {std::list<int> 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;
}

erase

iterator erase (const_iterator position);	删除迭代器位置的元素
iterator erase (const_iterator first, const_iterator last);	删除一段迭代器区间

resize

void 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 <list>
#include <iostream>int main() {std::list<int> l1 = {1, 2, 3};std::list<int> 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大小为0return 0;
}

2）移动单个元素：将列表 x 中由迭代器 i 指向的单个元素移动到当前列表中 position 所指向的元素之前。移动后，该元素从列表 x 中移除。同样是通过调整指针来完成操作，不会涉及元素的拷贝构造。

#include <list>
#include <iostream>int main() {std::list<int> l1 = {1, 2, 3};std::list<int> 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 <list>
#include <iostream>int main() {std::list<int> l1 = {1, 2, 3};std::list<int> 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 <list>
#include <iostream>int main() {std::list<int> 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 <list>
#include <iostream>bool is_even(int num) {return num % 2 == 0;
}int main() {std::list<int> 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 <list>
#include <iostream>int main() {std::list<int> 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 <list>
#include <iostream>int main() {std::list<int> 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 <list>
#include <iostream>int main() {std::list<int> l1 = {1, 3, 5};std::list<int> l2 = {2, 4, 6};l1.merge(l2);for (int i : l1) {std::cout << i << " ";}std::cout << "\nl2 size: " << l2.size() << std::endl; // l2大小为0return 0;
}

2）按照用户自定义的比较规则 comp ，将列表 x 合并到当前列表中。Compare 是一个可调用对象（如函数指针、函数对象、lambda 表达式等），它接受两个元素类型的参数，并返回 bool 类型的值，用于判断两个元素的顺序关系。同样，合并前两个列表都应是有序的（按 comp 规则），合并后 x 列表为空，当前列表包含两个列表的所有元素且有序。

#include <list>
#include <iostream>int main() {std::list<int> l1 = {3, 2, 1};std::list<int> 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大小为0return 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<int> lt1;vector<int> 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:256printf("list sort:%d\n", end2 - begin2);//list sort:28//100w数据时list sort:386
}

针对这个代码：

• 电脑配置不同，每次代码的运行都可能使这个运行时间有所误差，但数量级都是一样的
• 算法库中的sort排序效率更快

所以如果只是想排序，更建议使用vector，虽然我想这么说，但事实并非如此，请看以下代码

	srand(time(0));const int N = 1000000;list<int> lt1;vector<int> v;list<int> 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<T>* _prev;List_node<T>* _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的执行分为两个步骤：

1. 第一次解引用：调用obj.operator->()，返回一个中间对象intermediate。
2. 递归应用->：对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<initializer_list>
#include<algorithm>using namespace std;namespace wxList
{template<class T>struct List_node{T _data;List_node<T>* _prev;List_node<T>* _next;List_node(const T& data=T()):_data(data),_prev(nullptr),_next(nullptr){ }};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):_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 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;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<T>& li){empty();for (const auto& e: li){push_back(e);}_size = li.size();}list(initializer_list<T> il){empty();for (const auto& e : il){push_back(e);}_size = il.size();}void swap(list<T>& li){std::swap(_head, li._head);std::swap(_size, li._size);}list<T>& operator=(list<T> 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(){return _size;}void empty(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void push_back(const T& x){Node* tem = new Node(x);Node* tail = _head->_prev;tail->_next = tem;tem->_prev = tail;tem->_next = _head;_head->_prev = tem;}private:Node* _head;size_t _size;};
}