1 std::list 概述
std::list 是 C++ 标准库中的一个双向链表容器。它支持在容器的任何位置进行常数时间的插入和删除操作，但不支持快速随机访问。与 std::vector 或 std::deque 这样的连续存储容器相比，std::list 在插入和删除元素时不需要移动其他元素，因此这些操作通常更快。然而，由于链表的结构，访问单个元素（特别是位于容器中间的元素）通常比连续存储的容器慢。
std::list 的主要特点包括：
（1）双向链表结构： 每个元素在 std::list 中都有一个指针指向前一个元素，也有一个指针指向后一个元素。这种结构允许 std::list 在两个方向上进行迭代，即可以向前也可以向后遍历。
（2）插入和删除操作的高效性： std::list 在任何位置进行插入和删除操作的时间复杂度都是 O(1)，即常量时间。这是因为插入和删除操作不需要移动其他元素，只需要更新相关节点的指针即可。
（3）不支持随机访问： 由于 std::list 是基于链表实现的，因此它不支持像数组或向量那样的随机访问。访问特定位置的元素需要从头节点或尾节点开始遍历链表，直到到达所需的位置。
（4）空间效率较低： 由于每个节点都需要存储指向前后节点的指针，因此与连续存储的容器相比，std::list 在空间效率方面可能较低。每个节点除了存储实际的数据外，还需要额外的空间来存储指针。
（5）类型安全： 由于 std::list 是一个模板类，因此它是类型安全的。可以为 std::list 指定元素的类型，并确保只能存储该类型的元素。
1.1 std::list 的内部实现
std::list 的内部实现细节通常由 C++ 标准库的具体实现决定，根据 C++ 标准，它必须满足 std::list 所提供的功能和性能要求。在大多数实现中，std::list 的内部实现可以大致描述为以下结构：
节点结构
每个 std::list 的元素都被封装在一个节点中。每个节点至少包含两部分：
- 元素值：存储实际的数据值。
- 指针：至少包含两个指针，一个指向前一个节点（prev），另一个指向后一个节点（next）。
节点结构可以定义为如下：
struct list_node
{
T value; // 存储的数据值
list_node* prev; // 指向前一个节点的指针
list_node* next; // 指向后一个节点的指针
};
容器结构
std::list 容器本身通常包含指向链表第一个元素和最后一个元素的指针，以及可能的其他元数据，如大小（size）和容量（capacity）信息：
class list
{
public:
// 其他成员函数和类型定义
private:
list_node* head; // 指向链表第一个节点的指针
list_node* tail; // 指向链表最后一个节点的指针
size_t size; // 链表的大小
// 其他内部状态
};
迭代器
std::list 也提供了迭代器，用于遍历链表。迭代器内部通常包含一个指向当前节点的指针：
struct list_iterator
{
list_node* current; // 指向当前节点的指针
// 其他用于支持迭代器的状态
};
成员函数
std::list 提供了一系列成员函数，如 push_front、push_back、pop_front、pop_back、insert、erase 等，这些函数通常通过操作节点指针来实现其功能。
注意：由于 std::list 的内部实现细节通常由标准库的实现者决定，上述描述只是一种常见的实现方式。不同的编译器和库可能会有细微的差异，但它们都必须满足 C++ 标准对 std::list 的规定。但是在实际使用中，通常不需要关心这些内部细节，除非需要在进行底层优化或调试时需要深入了解它们。
1.2 std::list 的性能特点
std::list 的性能特点主要基于其双向链表的数据结构。以下是关于 std::list 性能的一些关键点：
（1）插入和删除操作的高效性：
在链表中的任何位置进行插入和删除操作的时间复杂度都是 O(1)，即常数时间。这是因为插入和删除操作只需要更新相邻节点的指针，而不需要移动其他元素。
这一特点使得 std::list 在需要频繁插入和删除元素的场景中表现出色。
（2）不支持快速随机访问：
访问链表中特定位置的元素需要从头节点或尾节点开始遍历链表，直到到达所需的位置。因此，随机访问 std::list 中元素的时间复杂度是 O(n)，其中 n 是元素的位置。
对于需要频繁进行随机访问的场景，std::list 可能不是最佳选择。
（3）空间效率较低：
由于 std::list 是基于链表实现的，每个节点除了存储实际的数据外，还需要额外的空间来存储指向前后节点的指针。因此，与连续存储的容器（如 std::vector）相比，std::list 在空间效率方面可能较低。
（4）迭代器的稳定性：
在 std::list 内或在数个 std::list 间添加、移除和移动元素不会非法化迭代器或引用。只有当对应元素被删除时，迭代器才会变得非法。
（5）内存使用：
std::list 使用非连续的内存空间进行存储。这意味着它不会像 std::vector 那样在添加元素时导致内存重新分配和复制。然而，由于每个节点都需要额外的空间来存储指针，所以总体内存使用可能会比连续存储的容器更高。
综上所述，std::list 的性能特点包括高效的插入和删除操作、不支持快速随机访问、较低的空间效率以及稳定的迭代器。这些特点使得 std::list 在需要频繁插入和删除元素的场景中表现出色，但在需要快速随机访问或高效空间利用的情况下可能不是最佳选择。
2 std::list 的基本使用
2.1 std::list 的声明与初始化
声明
首先，需要包含<list>头文件以使用 std::list：
#include <string>
// 声明一个整数类型的链表
std::list<int> vals;
// 声明一个字符串类型的链表
std::list<std::string> strs;
// 声明一个自定义类型的链表
struct MyStruct
{
int id;
std::string name;
};
std::list<MyStruct> myStructs;
初始化
可以使用多种方法来初始化std::list。
（1）默认初始化：
创建一个空的 std::list 容器。
std::list<int> vals; // 空的 list
（2）使用初始化列表：
在声明时直接使用初始化列表来添加元素。
std::list<int> vals = {1, 2, 3, 4, 5};
（3）使用迭代器或范围构造：
使用另一个容器的迭代器或范围来初始化 std::list。
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> vals(vec.begin(), vec.end());
（4）指定数量并填充默认值：
创建一个具有指定数量的元素，并使用默认构造函数生成这些元素。
std::list<int> vals(10); // 创建一个包含 10 个默认构造的 int 的 list
（5）指定数量和值填充：
创建一个具有指定数量的元素，并用给定的值填充它们。
std::list<int> vals(5, 1); // 创建一个包含 5 个值为 1 的 int 的 list
（6）拷贝构造：
使用另一个 std::list 来初始化一个新的 std::list。
std::list<int> firstVals = {1, 2, 3};
std::list<int> secondVals(firstVals); // 拷贝构造
（7）移动构造：
使用另一个 std::list 的移动语义来初始化一个新的 std::list。
std::list<int> firstVals = {1, 2, 3};
std::list<int> secondVals(std::move(firstVals)); // 移动构造
（8）运算符赋值：
使用 = 运算符将一个 std::list 的内容赋给另一个 std::list。
std::list<int> firstVals = {1, 2, 3};
std::list<int> secondVals = firstVals; // 运算符赋值
2.2 std::list 的大小与容量
std::list 中与大小与容量相关的方法有如下几种：
- empty(): 如果 list 为空则返回 true。
- size(): 返回 list 中的元素数量。
- max_size(): 返回 list 可以容纳的最大元素数量。
- resize(size_type n): 改变 list 的大小，增加或减少元素。
- resize(size_type n, const value_type& val): 改变 list 的大小，并用 val 填充新元素。
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
// 创建一个空的 std::list
std::list<int> myList;
// 检查 list 是否为空，并输出结果
if (myList.empty()) {
std::cout << "List is empty." << std::endl;
}
// 向 list 中添加元素
myList.push_back(10);
myList.push_back(20);
myList.push_back(30);
// 再次检查 list 是否为空，并输出结果
if (!myList.empty()) {
std::cout << "List is not empty." << std::endl;
}
// 获取 list 的大小，并输出结果
std::cout << "Size of the list: " << myList.size() << std::endl;
// 获取 list 可以容纳的最大元素数量，并输出结果
std::cout << "Max size of the list: " << myList.max_size() << std::endl;
// 改变 list 的大小，增加元素
myList.resize(5);
std::cout << "After resizing to 5 elements (no value specified), size of the list: " << myList.size() << std::endl;
// 再次改变 list 的大小，并用特定值填充新元素
myList.resize(8, 12);
std::cout << "After resizing to 8 elements with value 12, size of the list: " << myList.size() << std::endl;
// 遍历并输出 list 中的所有元素
for (const auto& element : myList) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
List is empty.
List is not empty.
Size of the list: 3
Max size of the list: 768614336404564650
After resizing to 5 elements (no value specified), size of the list: 5
After resizing to 8 elements with value 12, size of the list: 8
10 20 30 0 0 12 12 12
在上面代码中，首先创建了一个空的 std::list，并使用 empty() 方法来检查它是否为空。然后向 std::list 中添加了一些元素，并再次检查它是否为空。接着使用 size() 方法来获取 std::list 的大小，并使用 max_size() 方法来获取它可以容纳的最大元素数量。
之后使用 resize() 方法来改变 std::list 的大小。首先将它的大小增加到 5，没有指定新的元素值，所以 std::list 的尾部将添加一些默认构造的元素（对于 int 类型，这些元素的值是未定义的）。然后将 std::list 的大小增加到 8，并用值 12 来填充新增的元素。
最后遍历 std::list 并输出它的所有元素，以验证 resize() 方法的效果。
注意：std::list 的 max_size() 方法通常返回的是一个非常大的数字，代表理论上的最大大小限制，这通常比实际可用的内存要大得多。在实际使用中，由于内存限制，可能无法接近这个理论上的最大值。
2.3 std::list 的构造函数与析构函数
构造函数
std::list 有多个构造函数，允许以不同的方式创建 list 对象。下面是一些常用的构造函数：
- list(): 默认构造函数，创建一个空的 list。
- list(const list& other): 拷贝构造函数，创建一个与 other 相同内容的 list。
- list(list&& other) noexcept: 移动构造函数，移动 other 中的元素到新的 list（C++11 新加入）。
- list(const_iterator first, const_iterator last): 用迭代器范围构造 list。
- list(InitializerList init): 使用初始化列表构造 list（C++11 新加入）。
析构函数
- ~list(): 析构函数，释放 list 中的所有元素。
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
// 使用默认构造函数创建一个空的 list
std::list<int> emptyList;
std::cout << "Empty list size: " << emptyList.size() << std::endl;
// 向 emptyList 添加一些元素
for (int i = 0; i < 6; i++) {
emptyList.push_back(i);
}
// 使用拷贝构造函数创建一个与 emptyList 相同内容的 list
std::list<int> copiedList(emptyList);
std::cout << "Copied list size: " << copiedList.size() << std::endl;
// 使用移动构造函数移动 emptyList 中的元素到新的 list
std::list<int> movedList(std::move(emptyList));
std::cout << "Moved list size: " << movedList.size() << std::endl;
std::cout << "Original list (after move) size: " << emptyList.size() << std::endl;
// 使用迭代器范围构造 list
std::list<int>::const_iterator itBegin = copiedList.begin();
std::list<int>::const_iterator itEnd = copiedList.end();
std::list<int> rangedList(itBegin, itEnd);
std::cout << "Ranged list size: " << rangedList.size() << std::endl;
// 使用初始化列表构造 list (C++11)
std::initializer_list<int> initList = { 7, 8, 9, 10 };
std::list<int> initListList(initList);
std::cout << "Init list size: " << initListList.size() << std::endl;
// 打印所有 list 的内容
std::cout << "Copied list: ";
for (int num : copiedList) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Moved list: ";
for (int num : movedList) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Ranged list: ";
for (int num : rangedList) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Init list: ";
for (int num : initListList) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
Empty list size: 0
Copied list size: 6
Moved list size: 6
Original list (after move) size: 0
Ranged list size: 6
Init list size: 4
Copied list: 0 1 2 3 4 5
Moved list: 0 1 2 3 4 5
Ranged list: 0 1 2 3 4 5
Init list: 7 8 9 10
上面代码展示了如何使用 std::list 的不同构造函数来创建 list 对象。每种构造函数都用于创建一个具有不同特性的 list。另外，还展示了如何使用迭代器范围和初始化列表来构造 list。
注意：std::list 的析构函数是自动调用的，当 list 对象离开其作用域时，它会自动释放其分配的内存。上面代码没有显式调用析构函数，因为 C++ 的内存管理会自动处理这些事项。
3 std::list 的元素操作
3.1 std::list 元素的访问与修改
3.1.1 使用成员函数
std::list 中与元素的访问相关的方法有如下几种：
- front(): 返回对第一个元素的引用。
- back(): 返回对最后一个元素的引用。
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
// 创建一个std::list并添加一些元素
std::list<int> numbers = { 5, 10, 15, 20, 25 };
// 检查列表是否为空
if (numbers.empty())
{
std::cout << "The list is empty and cannot retrieve the first or last element." << std::endl;
}
else
{
// 使用front()获取并打印第一个元素
std::cout << "The first element: " << numbers.front() << std::endl;
// 使用back()获取并打印最后一个元素
std::cout << "Last element: " << numbers.back() << std::endl;
// 修改第一个和最后一个元素的值
numbers.front() = 1;
numbers.back() = 100;
// 打印修改后的列表
std::cout << "Modified list: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}
上面代码的输出为：
The first element: 5
Last element: 25
Modified list: 1 10 15 20 100
在上面代码中，首先创建了一个包含五个整数的 std::list。然后检查列表是否为空，如果不为空，则使用 front() 方法获取并打印第一个元素，并且使用 back() 方法获取并打印最后一个元素。接着修改了第一个和最后一个元素的值，并打印出修改后的整个列表。
注意：在实际使用中，应该始终在调用 front() 或 back() 之前检查列表是否为空，以避免在未定义的情况下访问元素。
3.1.2 使用迭代器
在 std::list 中，元素的访问和修改更常见的是通过迭代器来完成的。std::list 提供了几种不同的迭代器，包括正向迭代器（iterator）和常量迭代器（const_iterator）。正向迭代器允许你修改元素的值，而常量迭代器则只允许你读取元素的值。
访问元素
要访问 std::list 中的元素，可以使用正向迭代器或常量迭代器。以下是如何使用这些迭代器来访问元素的示例：
#include <iostream>
#include <list>
int main()
{
// 创建一个包含整数的 std::list
std::list<int> my_list = { 10, 20, 30, 40, 50 };
// 使用正向迭代器访问元素
for (std::list<int>::iterator it = my_list.begin(); it != my_list.end(); ++it) {
std::cout << *it << " "; // 输出: 10 20 30 40 50
}
std::cout << std::endl;
// 使用常量迭代器访问元素
for (const auto& num : my_list) {
std::cout << num << " "; // 输出: 10 20 30 40 50
}
std::cout << std::endl;
return 0;
}
在上面代码中，首先使用正向迭代器遍历列表并打印每个元素的值。然后使用基于范围的 for 循环和常量引用来遍历列表并打印每个元素的值。注意，常量引用不允许修改元素的值。
修改元素
要修改 std::list 中的元素，则必须使用正向迭代器。以下是如何使用正向迭代器来修改元素的示例：
#include <iostream>
#include <list>
int main()
{
// 创建一个包含整数的 std::list
std::list<int> my_list = { 10, 20, 30, 40, 50 };
// 假设我们要修改第一个元素的值
int new_value = 99;
// 使用 begin() 获取起始迭代器，并解引用它来修改元素的值
if (!my_list.empty()) {
auto it = my_list.begin();
*it = new_value;
std::advance(it, 2); // 移动到第三个位置
*it = new_value;
// 打印修改后的列表以验证结果
for (const auto& num : my_list) {
std::cout << num << " "; // 输出: 99 20 99 40 50
}
std::cout << std::endl;
}
else {
std::cout << "List is empty." << std::endl;
}
return 0;
}
在上面代码中，使用了 begin() 方法获取列表的第一个元素的迭代器，并通过解引用迭代器来修改其值。注意，在修改元素之前，检查了列表是否为空，以避免在空列表上进行操作。
3.2 std::list 元素的插入与删除
std::list 中与元素插入与删除相关的方法有如下几种：
- push_front(const value_type& val): 在 list 开头插入元素。
- push_back(const value_type& val): 在 list 末尾插入元素。
- pop_front(): 删除 list 开头的元素。
- pop_back(): 删除 list 末尾的元素。
- insert(const_iterator position, const value_type& val): 在指定位置插入元素。
- erase(const_iterator position): 删除指定位置的元素。
- erase(const_iterator first, const_iterator last): 删除指定范围内的元素。
- unique(): 删除 list 中的重复元素。
- unique(BinaryPredicate binary_pred): 使用自定义二元谓词删除指定元素。
- clear(): 删除 list 中的所有元素。
如下为样例代码：
#include <iostream>
#include <list>
#include <algorithm>
// 自定义二元谓词，用于判断两个元素的关系
struct MyPredicate {
bool operator()(const int& a, const int& b) const {
// 在这个例子中，我们定义相等为两个数模3后相等
return (a % 3) == (b % 3);
}
};
int main()
{
// 创建一个std::list
std::list<int> numbers;
// 使用push_front和push_back添加元素
numbers.push_front(10);
numbers.push_back(20);
numbers.push_front(5);
numbers.push_back(15);
// 打印原始列表
std::cout << "Original list: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 在指定位置插入元素
auto it = numbers.begin();
std::advance(it, 2); // 移动到第三个位置
numbers.insert(it, 12);
// 打印更新后的列表
std::cout << "List after insert: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 删除指定位置的元素
it = numbers.begin();
std::advance(it, 3); // 移动到第四个位置
numbers.erase(it);
// 打印更新后的列表
std::cout << "List after erase: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 删除重复元素（默认比较）
numbers.unique();
// 打印更新后的列表
std::cout << "List after unique (default comparison): ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用自定义二元谓词删除指定元素
numbers.unique(MyPredicate());
// 打印更新后的列表
std::cout << "List after unique (custom comparison): ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 删除列表中的所有元素
numbers.clear();
// 打印清空后的列表
std::cout << "List after clear: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 再次添加元素以展示pop_front和pop_back
numbers.push_back(3);
numbers.push_back(6);
numbers.push_back(9);
// 打印列表
std::cout << "List before popping: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 删除开头和末尾的元素
numbers.pop_front();
numbers.pop_back();
// 打印更新后的列表
std::cout << "List after popping: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
Original list: 5 10 20 15
List after insert: 5 10 12 20 15
List after erase: 5 10 12 15
List after unique (default comparison): 5 10 12 15
List after unique (custom comparison): 5 10 12
List after clear:
List before popping: 3 6 9
List after popping: 6
上面代码展示了如何使用 std::list 的基本方法，包括在列表的开头和末尾插入元素、删除元素、插入元素到指定位置、删除重复元素（包括使用自定义比较函数）以及清空整个列表。最后，它还展示了如何使用 pop_front 和 pop_back 方法删除列表的第一个和最后一个元素。
3.3 std::list 元素的移动
std::list 中与元素移动相关的方法有如下几种：
- splice(const_iterator position, list& other): 将 other 中的所有元素移动到 list 的指定位置。
- splice(const_iterator position, list&& other): 将 other 中的所有元素移动到 list 的指定位置（移动语义）。
- splice(const_iterator position, other, const_iterator i): 将 other 中从 i 开始的单个元素移动到 list 的指定位置。
- splice(const_iterator position, other, const_iterator first, const_iterator last): 将 other 中从 first 到 last 的元素移动到 list 的指定位置。
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
// 创建两个std::list并初始化
std::list<int> numbers1{ 1, 3, 5, 7, 9 };
std::list<int> numbers2{ 2, 4, 6, 8, 10 };
// 打印初始列表
std::cout << "List 1 (numbers1): ";
for (const auto& num : numbers1) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "List 2 (numbers2): ";
for (const auto& num : numbers2) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用splice移动numbers2的所有元素到numbers1的开头
numbers1.splice(numbers1.begin(), numbers2);
// 打印更新后的列表
std::cout << "List 1 after splicing all of numbers2: ";
for (const auto& num : numbers1) {
std::cout << num << " ";
}
std::cout << std::endl;
// numbers2现在是空的
std::cout << "List 2 after splicing: ";
for (const auto& num : numbers2) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用splice移动numbers1中的一个元素到另一个位置
auto it = numbers1.begin();
std::advance(it, 3); // 移动到第三个位置
numbers1.splice(numbers1.begin(), numbers1, it);
// 打印更新后的列表
std::cout << "List 1 after moving a single element: ";
for (const auto& num : numbers1) {
std::cout << num << " ";
}
std::cout << std::endl;
// 重置numbers2为初始状态
numbers2 = { 2, 4, 6, 8, 10 };
// 使用splice移动numbers1中的一个元素范围到另一个位置
it = numbers1.begin();
std::advance(it, 2); // 移动到第三个位置
auto it2 = std::next(it);
std::advance(it2, 3); // 移动到第六个位置（不包括）
numbers1.splice(numbers1.begin(), numbers1, it, it2);
// 打印更新后的列表
std::cout << "List 1 after moving a range of elements: ";
for (const auto& num : numbers1) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用移动语义的splice移动numbers2的所有元素到numbers1的开头
numbers2 = { 2, 4, 6, 8, 10 }; // 重置numbers2
numbers1.splice(numbers1.begin(), std::move(numbers2));
// 打印更新后的列表
std::cout << "List 1 after splicing all of numbers2 using move semantics: ";
for (const auto& num : numbers1) {
std::cout << num << " ";
}
std::cout << std::endl;
// numbers2现在是空的，因为使用了移动语义
std::cout << "List 2 after splicing with move semantics: ";
for (const auto& num : numbers2) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
List 1 (numbers1): 1 3 5 7 9
List 2 (numbers2): 2 4 6 8 10
List 1 after splicing all of numbers2: 2 4 6 8 10 1 3 5 7 9
List 2 after splicing:
List 1 after moving a single element: 8 2 4 6 10 1 3 5 7 9
List 1 after moving a range of elements: 4 6 10 1 8 2 3 5 7 9
List 1 after splicing all of numbers2 using move semantics: 2 4 6 8 10 4 6 10 1 8 2 3 5 7 9
List 2 after splicing with move semantics:
上面代码展示了如何使用 splice 方法的各个版本。首先创建了两个std::list对象并初始化。然后分步骤地展示了如何将一个列表的元素移动到另一个列表的不同位置，包括移动整个列表、单个元素和元素范围。最后展示了如何使用移动语义来移动一个列表的所有元素，这通常比复制更高效，因为它避免了不必要的拷贝操作。
3.4 std::list 的交换与合并
std::list 中与交换与合并的方法有如下几种：
- merge(list& other): 合并 other 到当前 list。
- merge(list& other, BinaryPredicate binary_pred): 使用自定义二元谓词合并 other 到当前 list。
- swap(list& other): 交换两个 list 的内容。
如下为样例代码：
#include <iostream>
#include <list>
#include <algorithm> // 用于std::less
// 自定义二元谓词，用于降序合并
struct DescendingPredicate {
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
int main()
{
// 创建两个std::list并初始化
std::list<int> list1{ 1, 3, 5, 7, 9 };
std::list<int> list2{ 2, 4, 6, 8, 10 };
// 打印初始列表
std::cout << "List 1 (before merge): ";
for (const auto& num : list1) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "List 2 (before merge): ";
for (const auto& num : list2) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用默认合并，按升序合并list2到list1
list1.merge(list2);
// 打印合并后的列表
std::cout << "List 1 (after merge, ascending order): ";
for (const auto& num : list1) {
std::cout << num << " ";
}
std::cout << std::endl;
// 要将两个 std::list 降序合并，需要确保两个列表在合并之前都是降序排列的
// 反转 list1 中元素的顺序，使其为降序排序
list1.reverse();
// 重置 list2 为初始状态
list2 = { 10, 8, 6, 4, 2 };
// 使用自定义二元谓词合并，按降序合并list2到list1
list1.merge(list2, DescendingPredicate());
// 打印合并后的列表
std::cout << "List 1 (after merge, descending order): ";
for (const auto& num : list1) {
std::cout << num << " ";
}
std::cout << std::endl;
// 打印list2，它现在应该是空的，因为元素被合并到了list1
std::cout << "List 2 (after merge): ";
for (const auto& num : list2) {
std::cout << num << " ";
}
std::cout << std::endl;
// 现在交换两个列表的内容
list1.swap(list2);
// 打印交换后的列表
std::cout << "List 1 (after swap): ";
for (const auto& num : list1) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "List 2 (after swap): ";
for (const auto& num : list2) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
List 1 (before merge): 1 3 5 7 9
List 2 (before merge): 2 4 6 8 10
List 1 (after merge, ascending order): 1 2 3 4 5 6 7 8 9 10
List 1 (after merge, descending order): 10 10 9 8 8 7 6 6 5 4 4 3 2 2 1
List 2 (after merge):
List 1 (after swap):
List 2 (after swap): 10 10 9 8 8 7 6 6 5 4 4 3 2 2 1
上面代码首先合并了 list2 到 list1，先是使用默认的升序合并，然后是使用自定义的降序合并。DescendingPredicate 结构用于定义降序合并的规则。最后使用了 swap 方法交换了 list1 和 list2 的内容。
注意：要将两个 std::list 降序合并，需要确保两个列表在合并之前都是降序排列的。反之，要将两个 std::list 升序合并，需要确保两个列表在合并之前都是升序排列的。
3.5 std::list 的正向遍历删除
在 std::list 中遍历并删除元素需要小心处理，因为直接删除元素会导致迭代器失效。一种常见的方法是使用 std::list 的 erase 方法结合 std::remove_if 算法来遍历并删除满足特定条件的元素。
如下为样例代码：
#include <iostream>
#include <list>
#include <algorithm>
int main()
{
std::list<int> my_list = { 1, 2, 3, 4, 5, 6 };
// 使用 std::remove_if 算法标记要删除的元素
auto it = std::remove_if(my_list.begin(), my_list.end(), [](int n) {
return n % 2 == 0; // 假设要删除所有偶数
});
// 使用 erase 方法删除标记过的元素
my_list.erase(it, my_list.end());
// 输出结果
for (const auto& elem : my_list) {
std::cout << elem << ' ';
}
return 0;
}
上面代码的输出为：
1 3 5
在上面代码中，std::remove_if 算法遍历 list 并将不满足条件（即不是偶数）的元素移动到容器的前面，并返回一个指向新逻辑结尾的迭代器。然后，erase 方法用于删除从该迭代器到 list 实际结尾的所有元素。
如果需要在遍历过程中逐个删除元素（效率更高），那么可以使用 std::list::erase 方法结合普通的循环，但每次删除元素后，都需要更新迭代器。以下是一个逐个删除特定元素的例子：
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
std::list<int> my_list = { 1, 2, 3, 4, 5, 6 };
auto it = my_list.begin();
while (it != my_list.end()) {
if ((*it) % 2 == 0) {
it = my_list.erase(it); // erase 返回下一个有效元素的迭代器
}
else {
++it; // 继续到下一个元素
}
}
// 输出结果
for (const auto& elem : my_list) {
std::cout << elem << ' ';
}
return 0;
}
上面代码的输出为：
1 3 5
在上面代码中，使用一个循环来遍历 list，并在每次迭代中检查当前元素是否满足删除条件。如果满足条件，则使用 erase 方法删除该元素，并更新迭代器。如果不满足条件，则简单地递增迭代器以继续遍历。
注意：在删除元素后，迭代器 it 会被 erase 方法更新为指向被删除元素之后的位置，因此在下一次循环迭代中，it 仍然有效。
3.6 std::list 的反向遍历删除
在 std::list 中反向遍历并删除元素，虽然可以使用 rbegin() 和 rend() 方法来获取反向迭代器，但是在循环过程中仍然要再将其转换为正向迭代器，使用起来并不方便，可以采用如下方法做反向遍历：
#include <iostream>
#include <list>
int main() {
std::list<int> my_list = { 1, 2, 3, 4, 5 };
if (my_list.size()>0)
{
auto it = my_list.end();
if (it != my_list.begin())
{
--it;
}
while (it != my_list.begin())
{
if ((*it) % 2 == 0) {
it = my_list.erase(it); // erase 返回下一个有效元素的迭代器
}
else
{
--it;
}
}
if (my_list.size() > 0)
{
it = my_list.begin();
if ((*it) % 2 == 0) {
my_list.erase(it);
}
}
}
// 打印列表以验证结果
for (const auto& num : my_list) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
1 3 5
上面代码的核心思路是使用 --it 来完成反向迭代的过程，要注意对 my_list.begin() 的单独校验处理。
4 std::list 的迭代器
4.1 std::list 迭代器的基本使用
std::list 中与迭代器相关的方法有如下几种：
- begin(): 返回一个指向容器中第一个元素的迭代器。
- end(): 返回一个指向容器中最后一个元素之后位置的迭代器。
- rbegin(): 返回一个指向容器中最后一个元素的反向迭代器。
- rend(): 返回一个指向容器中第一个元素之前位置的反向迭代器。
- cbegin(), cend(), crbegin(), crend(): 与上述类似，但返回的是常量迭代器或常量反向迭代器。
如下为样例代码：
#include <iostream>
#include <list>
int main()
{
// 创建一个包含整数的std::list
std::list<int> my_list = { 5, 10, 15, 20, 25 };
// 使用正向迭代器遍历列表
std::cout << "Iterating over the list using forward iterators:" << std::endl;
for (auto it = my_list.begin(); it != my_list.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用常量正向迭代器遍历列表
std::cout << "Iterating over the list using const forward iterators:" << std::endl;
for (auto cit = my_list.cbegin(); cit != my_list.cend(); ++cit) {
std::cout << *cit << " ";
}
std::cout << std::endl;
// 使用反向迭代器反向遍历列表
std::cout << "Iterating over the list in reverse using reverse iterators:" << std::endl;
for (auto rit = my_list.rbegin(); rit != my_list.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
// 使用常量反向迭代器反向遍历列表
std::cout << "Iterating over the list in reverse using const reverse iterators:" << std::endl;
for (auto crit = my_list.crbegin(); crit != my_list.crend(); ++crit) {
std::cout << *crit << " ";
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
Iterating over the list using forward iterators:
5 10 15 20 25
Iterating over the list using const forward iterators:
5 10 15 20 25
Iterating over the list in reverse using reverse iterators:
25 20 15 10 5
Iterating over the list in reverse using const reverse iterators:
25 20 15 10 5
在上面代码例中，首先创建了一个包含 5 个整数的 std::list。接着使用 begin() 和 end() 来获取正向迭代器，并使用它们来遍历列表。然后使用 cbegin() 和 cend() 来获取常量正向迭代器，并再次遍历列表。这样做是为了展示即使通过常量迭代器访问元素，列表的内容也不会被修改。
之后使用 rbegin() 和 rend() 来获取反向迭代器，并使用它们来反向遍历列表。最后使用 crbegin() 和 crend() 来获取常量反向迭代器，并反向遍历列表。
注意：cbegin(), cend(), crbegin()和 crend()返回的是常量迭代器，这意味着不能通过它们来修改列表中的元素。尝试这样做会导致编译错误。
4.2 std::list 迭代器使用的注意事项
在使用 std::list 的迭代器时，有一些重要的注意事项需要牢记，以确保代码的正确性和稳定性：
（1）迭代器失效：
当通过迭代器删除或插入元素时，所有指向被修改位置的迭代器、引用和指针都会失效。这意味着不能再使用它们来访问或修改列表中的元素。
在删除或插入元素后，任何指向被删除或插入元素之前的元素的迭代器仍然有效，但指向被删除或插入元素之后的元素的迭代器将失效。
（2）迭代器的范围和边界：
迭代器的范围是从 begin() 到 end()，但不包括 end() 所指向的位置。end() 是一个哨兵迭代器，用于指示列表的末尾，不应被解引用。
（3）线程安全性：
如果多个线程同时修改 std::list，则必须采取适当的同步措施来避免数据竞争和未定义行为。在这种情况下，迭代器的使用可能变得更加复杂和危险。
（4）注意性能：
虽然 std::list 的插入和删除操作在平均情况下是常数时间的，但频繁地在列表中间插入或删除元素可能会导致列表的重新分配和元素的复制，这可能会影响性能。