1. list的介绍和使用
1.1 list的介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- 与其他序列式容器相比，list通常在任意位置插入、移除元素的效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。比如：要访问list的第6个元素，必须从已知的位置（头和尾）一步步走到该位置；list还需要一些额外空间，以保存每个节点的相关联信息。
1.2 list的使用
1.2.1 list的构造
#include <list>// 默认构造函数
std::list<int> defaultList;// 通过值初始化列表
std::list<int> valueList = {1, 2, 3, 4, 5};// 通过大小和默认值初始化列表
std::list<int> sizeValueList(3, 1); // 包含三个元素，每个元素的值都是1// 通过范围初始化列表
int arr[] = {10, 20, 30, 40, 50};
std::list<int> rangeList(arr, arr + sizeof(arr) / sizeof(arr[0]));// 复制构造函数
std::list<int> copyList = valueList;// 移动构造函数（C++11及以后）
std::list<int> moveList = std::move(valueList);
1.2.2 list 访问元素
1. front()：返回对列表第一个元素的引用
std::list<int> myList = {1, 2, 3, 4, 5};
int firstElement = myList.front(); // firstElement is 1
2. back()：返回对列表最后一个元素的引用
int lastElement = myList.back(); // lastElement is 5
3. operator[]：通过索引访问元素，但请注意，std::list 不像 std::vector 或 std::array 那样提供随机访问。这个操作实际上会从 begin() 开始遍历列表直到到达指定位置，因此效率较低。
int elementAtTwo = myList[2]; // elementAtTwo is 3
1.2.3 list增删查改
push_front(const T& value) ：在列表的开头添加一个新元素。
push_back(const T& value) ：在列表的末尾添加一个新元素。
pop_front() ：移除列表的第一个元素。
pop_back() ：移除列表的最后一个元素。
insert(iterator pos, const T& value) ：在指定位置插入一个新元素。
auto it = myList.begin();
advance(it, 2); // 移动到第三个元素的位置
myList.insert(it, 15); // 在第三个元素的位置插入 15
注意：头插头删，尾插尾删的效率都很高。string以后插入开始使用迭代器位置，string用的是下标。list如果想在第3个位置插入元素，不能写成：
myList.insert(myList.begin() + 3, 15);
因为空间不是连续的。
erase(iterator pos) ：移除指定位置的元素。
auto it = myList.begin();
advance(it, 2); // 移动到第三个元素的位置
myList.erase(it); // 移除第三个元素
1.2.4 其他
比如说size()，capacity()等。
- merge()
在C++标准库中，std::merge 是一个用于合并两个已排序范围的算法。它位于 <algorithm> 头文件中，并且可以用于各种容器（如 vector, list, deque 等）。std::merge 的主要作用是将两个已排序的序列合并成一个新的已排序序列。
输入必须是已排序的：std::merge 假设输入的两个范围已经按升序或降序排列。如果输入未排序，则结果将是未定义的。
- remove
std::remove 和 std::remove_if 是用于从序列中移除元素的算法。它们并不直接删除元素，而是将不需要的元素移动到序列的末尾，并返回一个指向新序列末尾（即最后一个未被移除的元素之后的位置）的迭代器。实际的删除操作通常需要结合容器的 erase 方法来完成。
#include <iostream>
#include <list>
#include <algorithm> // 包含 std::removeusing namespace std;void test_remove()
{int array[] = {1, 2, 3, 4, 5, 3, 6};list<int> l(array, array + 7);cout << "Original list: ";for (const auto& elem : l){cout << elem << " ";}cout << endl;// 使用 std::remove 将值为 3 的元素移到末尾l.erase(std::remove(l.begin(), l.end(), 3), l.end());cout << "List after removing 3: ";for (const auto& elem : l){cout << elem << " ";}cout << endl;
}int main()
{test2();test_remove();return 0;
}
使用 std::remove 将所有 3 移动到列表末尾，并返回新的末尾迭代器 new_end。
使用 erase 删除从 new_end 到列表末尾的所有元素，即删除所有 3。
这样，只需调用一次 erase 就能删除所有 3。
1.2.5 迭代器失效
因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在被删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
#include <iostream>
#include <list>void test()
{int array[] = {1, 2, 3, 4, 5};std::list<int> l(array, array + 5);auto it = l.begin();while (it != l.end()){std::cout << "Deleting element: " << *it << std::endl;auto next_it = l.erase(it); // erase 返回下一个有效的迭代器std::cout << "Iterator after erase: " << (next_it == l.end() ? "end" : std::to_string(*next_it)) << std::endl;it = next_it;}std::cout << "List after deletion: ";for (const auto& elem : l){std::cout << elem << " ";}std::cout << std::endl;
}int main()
{test();return 0;
}
Deleting element: 1
Iterator after erase: 2
Deleting element: 2
Iterator after erase: 3
Deleting element: 3
Iterator after erase: 4
Deleting element: 4
Iterator after erase: 5
Deleting element: 5
Iterator after erase: end
List after deletion:通过上述代码和控制流图，可以清晰地验证删除时失效的只是被删除节点的迭代器，其他迭代器不会受到影响。
void test()
{int array[] = {1, 2, 3, 4, 5};list<int> l(array, array + 5);auto it = l.begin();while (it != l.end()){l.erase(it); ++it；}
}erase函数执行后，it所指向的节点已经被删除，因此it无效，在下一次使用it时，必须先给其赋值。
void test()
{int array[] = {1, 2, 3, 4, 5};list<int> l(array, array + 5);auto it = l.begin();while (it != l.end()){it = l.erase(it); // erase 返回下一个有效的迭代器}
}1.3 迭代器的分类
迭代器按性质分类，由容器底层结构决定。
- 前向迭代器（Forward Iterator）
可以读取和写入数据，支持多次遍历，但只能单向前进。
支持的操作：输入迭代器和输出迭代器的所有操作，以及多次遍历。
- 双向迭代器（Bidirectional Iterator）
在前向迭代器的基础上增加了反向遍历的能力。
支持的操作：前向迭代器的所有操作，以及--（前缀和后缀）。
- 随机访问迭代器（Random Access Iterator）
支持任意位置的访问，可以进行算术运算（如+, -），并且可以比较大小。
支持的操作：双向迭代器的所有操作，以及[]，+, -，<, >, <=, >=。
按功能从弱到强排列如下：
- 输入迭代器（Input Iterator）
- 输出迭代器（Output Iterator）
- 前向迭代器（Forward Iterator）
- 双向迭代器（Bidirectional Iterator）
- 随机访问迭代器（Random Access Iterator）
比如说 sort 函数使用的就是随机迭代器，我们这节讲的 list 就不能调用它，因为list使用的是双向迭代器。
在C++标准库中，不同容器支持不同类型的迭代器：
- std::list：使用双向迭代器，支持前向和后向遍历。
- std::vector 和 std::deque、std::string：使用随机访问迭代器，支持任意位置的访问和高效的算术运算。
- std::forward_list：使用前向迭代器，仅支持单向遍历。
- std::set, std::map, std::multiset, std::multimap：使用双向迭代器。
- std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap：使用前向迭代器。
层级低的容器不能访问层级高的函数。层级高的容器可以访问层级低的函数。比如：vector和string就可以调用reverse（双向）。
具体的函数属于什么层级可以在文档中查找。
2. list的模拟实现
2.1 初步实现
namespace zzy
{template<class T>struct list_node//为什么这里写它？{list_node<T>* _next;list_node<T>* _prev;T _val;explicit list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};template<class T>class list{typedef list_node<T> Node;public:list(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}void push_back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;size_t _size;};
}- list_node，为什么这里写它？后面再 typedef 成 Node：
因为在zzy的命名空间下，别的容器的结点也要用 Node 这个名字，如果这里列表的结点写成了Node，别的容器使用时会有命名冲突。所以在后面的list类中再typedef成Node，便于区分的同时也更方便。
2.2 list迭代器
在namespace中还要加上list迭代器：
template<class T>struct _list_iterator{typedef list_node<T> Node;Node* _node;explicit _list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}_list_iterator<T>& operator++(){_node = _node->_next;return *this;}bool operator!=(const _list_iterator<T>& it) const{return _node != it._node;}};这段C++代码定义了一个模板类 _list_iterator，用于实现双向链表的迭代器。主要功能如下：
- 构造函数：初始化迭代器，指向给定的节点。
- 解引用操作符 operator*：返回当前节点存储的值。
- 前缀自增操作符 operator++：将迭代器移动到下一个节点，并返回自身。
- 不等比较操作符 operator!=：比较两个迭代器是否指向不同的节点。
- 为什么 const _list_iterator<T>& it 要写const
不加const会报错，因为end() 函数通常返回一个表示链表末尾的迭代器，这个迭代器是一个临时对象（具有常性）。如果你不使用 const 修饰符，编译器将不允许你将这个临时对象绑定到非 const 引用上。
与此同时，list类中public更新为：
public:typedef _list_iterator<T> iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}2.3 const迭代器
我们期望的是指向的内容不能修改，不是指针本身不能修改，指针本身还得++才能遍历列表。
T& operator*() const上面这种是允许修改返回值的，很少用。
const T& operator*()这个是以const T& 返回，返回值类型是 const T&，返回值不能修改。
如果我们只是复制一下普通迭代器的实现，只是修改成上面这种*重载，其余都不变，未免太过冗余，于是我们想到了可以在模板中增加参数，一种只用来控制返回类型不同的参数
public:typedef _list_iterator<T, T&> iterator;typedef _list_iterator<T, const T&> const_iterator; template<class T, class Ref>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref> self;Node* _node;explicit _list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}self& operator++()//前置{_node = _node->_next;return *this;}self operator++(int)//后置{self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(const self& it) const{return _node != it._node;}};Ref 是 _list_iterator 模板类的第二个模板参数。
Ref 的作用：
Ref 用于定义解引用操作符 operator*() 返回的类型。具体来说：
- 如果 Ref 是 T&（即 T 的引用），那么 operator*() 将返回当前节点存储的值的引用。
- 如果 Ref 是 T（即 T 的值），那么 operator*() 将返回当前节点存储的值的副本。
通过这种方式，_list_iterator 可以支持不同类型的迭代器，例如：
- 普通迭代器：返回引用 (T&)，允许修改元素。
- 常量迭代器：返回常量引用 (const T&)，不允许修改元素。
void test_list()
{list<A> lt;lt.push_back(A(1));lt.push_back(A(2));lt.push_back(A(3));list<A>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a << endl;cout << it->_val._a << endl;++it;}cout << endl;
}C语言中的scanf和printf可以针对内置类型，但是自定义类型打印仍需要流插入重载。
由于普通和const迭代器各需要一个不同的返回类型的-> 的重载：
template<class T, class Ref = T&, class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;...Ptr operator->() const{return &_node->_val;}};public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;2.4 其他成员函数
iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--size;return next;} void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}size_t size() const{return _size;}~list(){clear();delete _head;_head = nullptr;} list(const list<T>& lt){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;for(auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(const list<T>& lt){swap(lt);return *this;}3. list与vector的对比
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持，访问效率为O(1) | 不支持，访问某个效率为O(N) |
| 插入删除 | 任意位置插删效率低 | 效率高，不需要搬移元素，O(1) |
| 空间利用率 | 不易造成内存碎片，空间利用率高 | 小结点易造成内存碎片 |
| 迭代器 | 原生指针 | 对指针进行封装 |
| 迭代器失效 | 插入可能导致扩容，导致失效 删除时需重新赋值否则失效 | 插入时不会导致迭代器失效 删除时，只会导致当前迭代器失效 |
| 使用场景 | 需要高效存储，支持随机访问 不关心插入删除效率 | 大量删除和插入操作 不关心随机访问 |
3.1 容器与迭代器
如果我们想在3前面插入一个值，但是我们发现list和vector都没有提供find，该怎么考虑呢？
首先我们应该意识到：C++通过迭代器将容器与算法连接起来了。迭代器提供了统一的方法访问容器，却不需要关注容器的底层实现。
在vector中，begin指向第一个元素，end指向最后一个数据的下一个位置。在list中，由于list是带头双向循环链表，begin指向的是第一个数据（头节点的下一个节点），而end则指向头结点。在list中，不能用 it < c.end()，在遍历 std::list 时，应该使用 != 来比较迭代器是否到达容器的末尾，因为在list中地址大小关系是不一定的。
在 C++ 标准库中， std::list 和 std::vector 都没有直接提供 find 成员函数。原因在于：
- 通用算法与容器分离：C++ 标准库采用了一种设计哲学，将算法与容器分离。算法被设计为独立于容器的函数，这样可以提高算法的复用性。例如， std::find 是一个通用算法，可以应用于任何支持迭代器的容器，包括 std::list、std::vector、std::array 等。
- 避免重复：如果每个容器都提供自己的 find 方法，那么就会有很多重复的代码。通过将算法作为独立的函数，可以避免这种重复，同时保持代码的简洁性和一致性。
3.2 排序效率
在C++中，选择合适的容器对于程序的性能和效率至关重要。std::list 和 std::vector 是两种常用的容器，但它们在不同操作上的表现差异很大。以下是为什么在需要排序时，std::list 不如 std::vector 合适的原因：
1. 排序算法的实现
- std::vector：
std::vector 支持随机访问迭代器，这意味着可以高效地进行索引访问和算术运算。标准库中的排序算法（如 std::sort）依赖于随机访问迭代器来实现高效的排序算法（通常是快速排序或归并排序），这些算法的时间复杂度为 O(n log n)。
- std::list：
std::list 只支持双向迭代器，不支持随机访问迭代器。
因此，标准库中的 std::sort 不能直接用于 std::list。虽然 std::list 提供了 std::list::sort 成员函数，但它的时间复杂度通常较高（O(n log n)，但在某些情况下可能更差），并且由于 std::list 的链表结构，元素之间的比较和交换操作也较为低效。
2. 内存布局与缓存友好性
- std::vector：
std::vector 是连续内存分配的，这使得它在现代CPU上具有更好的缓存局部性，从而提高了访问速度。
连续内存布局也有助于减少页面错误和提高内存带宽利用率。
- std::list：
std::list 是由节点组成的链表，每个节点都可能分散在不同的内存位置。
这种非连续的内存布局导致较差的缓存局部性，增加了内存访问的延迟。
4. 实际应用场景
- std::vector：
如果你需要对大量数据进行排序，并且不需要频繁的插入和删除操作，std::vector 是更好的选择。
它提供了更好的性能和更高的代码可读性。
- std::list：
如果你需要频繁地在列表中间插入和删除元素，并且不需要高效的排序操作，std::list 可能更适合。
但在需要排序的情况下，std::list 的性能劣势明显。
