C++ std::list
std::list 是 C++ STL 中基于双向链表实现的序列容器，其设计目标是提供高效的任意位置插入 / 删除操作。1、底层结构与核心原理
1.1 节点与链表结构
节点组成：每个元素存储在独立的节点中，节点包含三部分
template <typename T>
struct ListNode {
T data; // 元素值
ListNode* prev;// 指向前驱节点
ListNode* next;// 指向后继节点
};容器内部指针：std::list 维护两个关键指针：
[*]head：指向第一个节点（首节点）。
[*]tail：指向最后一个节点（尾节点）。
1.2 核心特性
[*]非连续存储
[*]元素分散在内存的各个地方，不像vector或array是连续块。
[*]高效的插入与删除 (O(1))
[*]在任何已知位置（通过迭代器指定）的插入和删除操作都是常数时间复杂度。
[*]操作仅涉及指针的重新赋值，不需要移动任何其他元素。
[*]插入：新分配一个节点，然后调整相邻节点的指针指向这个新节点。
[*]删除：调整目标节点前后节点的指针，让它们彼此指向对方，然后释放目标节点的内存。
[*]迭代器稳定性
[*]这是list最强大的特性之一。插入操作不会使任何现有的迭代器、指针或引用失效。
[*]删除操作只会使指向被删除元素的迭代器、指针或引用失效，其他元素的迭代器仍然完全有效。
[*]这与vector和deque形成鲜明对比，后者在插入/删除时极易导致迭代器大面积失效。
[*]不支持随机访问 (O(n))
[*]无法使用[]运算符或at()方法直接访问第n个元素。
[*]访问某个特定位置的元素需要从begin()或end()开始逐步递增或递减迭代器，时间复杂度为线性O(n)。
2、常用操作与示例代码
2.1 初始化
#include <list>
#include <iostream>
// 1. 空list
std::list<int> list1;
// 2. 包含 n 个元素，每个元素使用默认值初始化 (int 为 0)
std::list<int> list2(5); // {0, 0, 0, 0, 0}
// 3. 包含 n 个元素，每个元素都是 value
std::list<int> list3(5, 100); // {100, 100, 100, 100, 100}
// 4. 通过初始化列表 (C++11)
std::list<int> list4 = {1, 2, 3, 4, 5};
// 5. 通过迭代器范围（另一个容器的）
std::vector<int> vec = {6, 7, 8};
std::list<int> list5(vec.begin(), vec.end()); // {6, 7, 8}
// 6. 拷贝构造函数
std::list<int> list6(list4); // {1, 2, 3, 4, 5}2.2 元素访问
std::list<int> l = {10, 20, 30};
// 访问第一个和最后一个元素
std::cout << l.front(); // 10
std::cout << l.back();// 30
// 错误！list不支持随机访问
// int a = l;
// int b = l.at(1);
// 正确但低效的方法：使用迭代器步进
auto it = l.begin();
std::advance(it, 1); // 将迭代器 it 前进 1 步，现在指向 20
std::cout << *it; // 20
// 注意：advance(it, n) 对于list是O(n)操作2.6 splice：转移元素的神器
std::list<int> l = {1, 2, 3};
// 在尾部添加
l.push_back(4); // {1, 2, 3, 4} - 拷贝或移动
l.emplace_back(5); // {1, 2, 3, 4, 5} - 原地构造，更高效
// 在头部添加
l.push_front(0); // {0, 1, 2, 3, 4, 5}
l.emplace_front(-1); // {-1, 0, 1, 2, 3, 4, 5}
// 在指定位置插入
auto it = l.begin();
std::advance(it, 3); // it 现在指向 2
l.insert(it, 99); // 在 2 之前插入 99 -> {-1, 0, 1, 99, 2, 3, 4, 5}
l.emplace(it, 88); // 同理，但原地构造 -> {-1, 0, 1, 99, 88, 2, 3, 4, 5}
// 插入多个值或一个区间
l.insert(it, 3, 77); // 在 it 前插入 3 个 77
std::vector<int> v = {55, 66};
l.insert(it, v.begin(), v.end()); // 插入一个区间2.7 sort：成员函数排序
std::list<int> l = {-1, 0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5};
// 删除头部元素
l.pop_front(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5}
// 删除尾部元素
l.pop_back(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4}
// 删除指定位置的元素
auto it = l.begin();
std::advance(it, 3);
it = l.erase(it); // 删除第三个元素（第一个77），erase返回被删除元素的下一个元素的迭代器
// l: {0, 1, 77, 77, 55, 66, 88, 2, 3, 4}
// 删除一个区间的元素 [first, last)
auto first = l.begin();
auto last = l.begin();
std::advance(first, 1);
std::advance(last, 4);
l.erase(first, last); // 删除 [第二个元素1, 第五个元素55) 之间的元素（左闭右开）
// l: {0, 55, 66, 88, 2, 3, 4}
// 删除所有值等于特定值的元素
l.remove(88); // l: {0, 55, 66, 2, 3, 4}
// 删除满足条件的所有元素（例如，删除所有偶数）
l.remove_if([](int n) { return n % 2 == 0; }); // 使用Lambda表达式
// l: {55, 3}
// 删除所有元素
l.clear();2.8 merge：合并两个已排序的list
std::list<int> l = {1, 2, 3};
std::cout << l.size(); // 3
std::cout << l.empty(); // false (0)
l.resize(5); // 将大小增大到5，新增的元素默认初始化为0 -> {1, 2, 3, 0, 0}
l.resize(2); // 将大小减小到2，尾部的元素被丢弃 -> {1, 2}
l.resize(4, 99); // 将大小增大到4，新增的元素初始化为99 -> {1, 2, 99, 99}
// list 没有 capacity() 和 reserve() 概念，因为内存是动态按需分配的。2.9 unique：去除连续的重复元素
// 将另一个list的元素转移到本list中，不涉及元素的拷贝或移动，只改变指针。
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};
auto it = list1.begin();
std::advance(it, 1); // it 指向 2
// 1. 转移整个list2到list1的it位置之前
list1.splice(it, list2);
// list1: {1, 4, 5, 6, 2, 3}
// list2: (空)
// 2. 转移另一个list中的单个元素
std::list<int> list3 = {7, 8, 9};
auto it3 = list3.begin(); // it3 指向 7
list1.splice(list1.begin(), list3, it3); // 将list3的it3元素转移到list1开头
// list1: {7, 1, 4, 5, 6, 2, 3}
// list3: {8, 9}
// 3. 转移另一个list中的一个元素范围
std::list<int> list4 = {10, 11, 12, 13};
auto first4 = list4.begin(); // 10
auto last4 = first4;
std::advance(last4, 2); // 12
list1.splice(list1.end(), list4, first4, last4); // 转移[10, 11)（左闭右开）
// list1: {7, 1, 4, 5, 6, 2, 3, 10, 11}
// list4: {12, 13}2.10 循环
2.10.1 范围-based for 循环 (C++11+)
#include #include int main() { std::list numbers = {1, 2, 3, 4, 5}; // 只读访问 for (int num : numbers) { std::cout
页:
[1]