C++ STL 容器详解：双向链表 list 核心用法与注意事项

特殊成员函数

• 析构函数：对象销毁时自动调用，释放所有节点占用的内存。
• 赋值运算符重载：执行深拷贝，确保新容器内部元素被正确复制。

迭代器的使用

获取迭代器通常使用 iterator 类型，它是 std::list 的内部定义类型。

• 正向遍历：使用 begin() 和 end()。注意区间是左闭右开。
• 反向遍历：使用 rbegin() 和 rend()。

虽然范围 for 循环语法简洁，但仅支持正向遍历。若需逆向操作，必须使用反向迭代器。

代码示例：

// 正向遍历
int arr[] = {5, 2, 0, 1, 3, 1, 4};
list<int> l1(arr, arr + 7);
list<int>::iterator it = l1.begin();
while (it != l1.end()) {
    cout << *it << ' ';
    it++;
}
cout << endl;

// 反向遍历
list<int>::reverse_iterator rit = l1.rbegin();
while (rit != l1.rend()) {
    cout << *rit << ' ';
    rit++;
}
cout << endl;

容器相关函数

size 和 empty

• size()：返回当前有效数据个数。
• empty()：判断容器是否为空。

list<int> l1;
list<int> l2(6, 6);
cout << "l1 size: " << l1.size() << endl;
cout << "l2 size: " << l2.size() << endl;
cout << "l1 empty: " << l1.empty() << endl;
cout << "l2 empty: " << l2.empty() << endl;

修改容器内容相关函数

push_front / emplace_front

• push_front()：在头部添加元素，涉及拷贝或移动。
• emplace_front()：在头部原地构造元素，避免拷贝，效率更高。

int arr[] = {5, 2, 0, 1, 3, 1, 4};
int arr1[] = {1, 3, 1, 4, 5, 2, 0};
list<int> l1(arr, arr + 7);
list<int> l2(arr1, arr1 + 7);
l1.emplace_front(6); // 原地构造
l2.push_front(100);  // 拷贝构造

emplace_back / push_back

逻辑同上，只是操作位置在尾部。

l1.emplace_back(6);
l2.push_back(100);

insert / emplace

• 迭代器不失效：insert 不会导致现有迭代器失效，仅修改链接关系。
• 功能：支持插入单个元素、多个相同元素、或迭代器区间。
• emplace：同 insert，但在指定位置直接构造元素。

int arr[] = {5, 2, 0, 1, 3, 1, 4};
list<int> l3(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int>::iterator pos = l3.begin();
pos++; // 移动到第二个元素

// 在 pos 之前插入单个元素
l3.insert(pos, 0);

// 插入 5 个 6
l3.insert(pos, 5, 6);

// 插入区间
list<int> lt4(6, 5);
l3.insert(pos, lt4.begin(), lt4.end());

for (auto e : l3) {
    cout << e << ' ';
}
cout << endl;

pop_front / pop_back

• pop_front()：删除头部元素。
• pop_back()：删除尾部元素。

list<int> l1;
l1.push_back(0);
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);

for (auto e : l1) cout << e << ' ';
cout << endl; // 0 1 2 3

l1.pop_back();
l1.pop_back();

for (auto e : l1) cout << e << ' ';
cout << endl; // 0 1

erase / clear

• erase：删除指定迭代器指向的节点。关键点：被删除节点的迭代器会失效，但 erase 会返回下一个有效迭代器。务必使用返回值继续遍历。
• clear：清空所有元素。

int arr[] = {5, 2, 0, 1, 3, 1, 4};
list<int> l1(arr, arr + sizeof(arr) / sizeof(arr[0]));

// 删除最后一个元素
l1.erase(--l1.end());

// 清空容器
l1.clear();

resize

调整容器大小。若缩小则截断多余部分；若扩大则尾插默认值或指定值。

list<int> l1(5, 3);
for (auto e : l1) cout << e << ' ';
cout << endl; // 3 3 3 3 3

l1.resize(7, 6); // 扩大并填充 6
for (auto e : l1) cout << e << ' ';
cout << endl; // 3 3 3 3 3 6 6

l1.resize(2); // 缩小
for (auto e : l1) cout << e << ' ';
cout << endl; // 3 3

assign

替换容器内容。会先清空原数据，再根据传入参数（迭代器区间或值+数量）重新填充。

int arr[] = {5, 2, 0, 1, 3, 1, 4};
list<int> l1(arr, arr + 7);
list<int> l2;
l2.assign(l1.begin(), l1.end());

for (auto e : l2) cout << e << ' ';
cout << endl;

swap

交换两个容器的内容，这是一个高效操作，仅交换内部指针，不涉及元素拷贝。

list<int> l1(4, 2);
list<int> l2(4, 6);
l1.swap(l2);

for (auto e : l1) cout << e << ' ';
cout << endl; // 6 6 6 6
for (auto e : l2) cout << e << ' ';
cout << endl; // 2 2 2 2

list 的相关操作函数

sort

对 list 进行排序。由于是双向链表，它使用内部归并排序，时间复杂度 O(n log n)。

list<int> lt;
lt.push_back(4); lt.push_back(7); lt.push_back(5);
lt.push_back(9); lt.push_back(6); lt.push_back(0); lt.push_back(3);

lt.sort(); // 默认排序升序

for (auto e : lt) cout << e << ' ';
cout << endl; // 0 3 4 5 6 7 9

remove

移除所有等于指定值的元素。注意这是原地修改，匹配的是值而非迭代器。

list<int> lt;
lt.push_back(1); lt.push_back(4); lt.push_back(3);
lt.push_back(3); lt.push_back(2); lt.push_back(2); lt.push_back(3);

lt.remove(3); // 删除所有值为 3 的元素

for (auto e : lt) cout << e << ' ';
cout << endl; // 1 4 2 2

unique

删除连续的重复元素。因此通常需要先排序，否则非相邻的重复元素不会被删除。

lt.sort();
lt.unique();

for (auto e : lt) cout << e << ' ';
cout << endl; // 1 2 3 4

merge

将两个已排序的 list 合并为一个。合并后源列表变为空，所有元素移至目标列表。要求两个列表均有序。

list<int> lt1;
lt1.push_back(3); lt1.push_back(8); lt1.push_back(1);
list<int> lt2;
lt2.push_back(6); lt2.push_back(2); lt2.push_back(9); lt2.push_back(5);

lt1.sort();
lt2.sort();
lt1.merge(lt2);

for (auto e : lt1) cout << e << ' ';
cout << endl; // 1 2 3 5 6 8 9

reserve

注意：std::list 不支持 reserve() 方法。因为链表内存是动态分散分配的，不存在连续内存块预分配的概念。该方法仅适用于 vector 等连续内存容器。

在实际开发中，选择 list 还是 vector 取决于具体场景。如果频繁在中间插入删除且不需要随机访问，list 是更好的选择；反之，若追求缓存友好性和顺序访问性能，vector 更优。理解这些底层差异，才能写出更健壮的 C++ 代码。