C++ std::list
概念详解
std::list
是 C++ 标准模板库(STL)中的一个双向链表容器。与 vector
和 array
不同,它不保证元素在内存中连续存储,而是通过指针将各个元素连接起来。
核心特性
- 双向链表结构:
- 每个元素包含指向前驱和后继的指针
- 支持双向遍历(前向和后向)
- 时间复杂度:
- 任意位置插入/删除:O(1)
- 随机访问:O(n)(效率低)
- 排序:O(n log n)(使用成员函数
sort()
)
- 内存特性:
- 非连续内存分配
- 每个元素有额外指针开销(前驱 + 后继)
- 不会导致迭代器失效(除被删除元素)
- 迭代器类型:
- 双向迭代器(支持
++
和--
) - 不支持随机访问(不能
+ n
)
- 双向迭代器(支持
常用成员函数
操作 | 函数 | 示例 |
---|---|---|
插入元素 | push_back() |
list.push_back(10); |
push_front() |
list.push_front(5); |
|
insert() |
list.insert(it, 7); |
|
删除元素 | pop_back() |
list.pop_back(); |
pop_front() |
list.pop_front(); |
|
erase() |
list.erase(it); |
|
访问元素 | front() |
int first = list.front() |
back() |
int last = list.back() |
|
容量操作 | size() |
int len = list.size() |
empty() |
if (list.empty()) ... |
|
特殊操作 | splice() |
list1.splice(pos, list2) |
sort() |
list.sort(); |
|
merge() |
list1.merge(list2); |
|
reverse() |
list.reverse(); |
使用案例:订单管理系统
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
// 订单结构
struct Order {
int id;
std::string customer;
double amount;
Order(int i, std::string c, double a)
: id(i), customer(c), amount(a) {}
};
int main() {
// 创建订单链表
std::list<Order> orders;
// 添加订单(三种方式)
orders.push_back(Order(101, "Alice", 150.0)); // 尾部添加
orders.emplace_back(102, "Bob", 99.99); // 直接构造(C++11)
orders.push_front(Order(100, "VIP", 500.0)); // 头部添加
// 在特定位置插入
auto it = orders.begin();
std::advance(it, 2); // 移动到第三个位置
orders.insert(it, Order(103, "Charlie", 75.5));
// 遍历并打印订单(C++11范围循环)
std::cout << "All Orders:\n";
for (const auto& order : orders) {
std::cout << "ID: " << order.id
<< ", Customer: " << order.customer
<< ", Amount: $" << order.amount << "\n";
}
// 删除特定订单(金额<100)
orders.remove_if([](const Order& o) {
return o.amount < 100.0;
});
// 按金额升序排序
orders.sort([](const Order& a, const Order& b) {
return a.amount < b.amount;
});
// 新订单批次
std::list<Order> newOrders = {
{201, "David", 200.0},
{202, "Eva", 350.0}
};
// 合并订单(到链表尾部)
orders.splice(orders.end(), newOrders);
// 遍历打印最终订单
std::cout << "\nFinal Orders (Sorted & Merged):\n";
for (const auto& order : orders) {
std::cout << "ID: " << order.id
<< ", Customer: " << order.customer
<< ", Amount: $" << order.amount << "\n";
}
// 查找特定订单
auto findIt = std::find_if(orders.begin(), orders.end(),
[](const Order& o) { return o.customer == "Eva"; });
if (findIt != orders.end()) {
std::cout << "\nFound Eva's order: $" << findIt->amount << "\n";
}
return 0;
}
输出示例:
All Orders:
ID: 100, Customer: VIP, Amount: $500
ID: 101, Customer: Alice, Amount: $150
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99
Final Orders (Sorted & Merged):
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99
ID: 101, Customer: Alice, Amount: $150
ID: 201, Customer: David, Amount: $200
ID: 202, Customer: Eva, Amount: $350
ID: 100, Customer: VIP, Amount: $500
Found Eva's order: $350
关键操作详解
高效插入/删除:
// 在任意位置插入(O(1)) auto it = orders.begin(); std::advance(it, 3); orders.insert(it, Order(105, "Frank", 120.0)); // 删除指定位置元素(O(1)) orders.erase(it);
链表拼接:
// 将list2的所有元素移动到list1的指定位置 list1.splice(position, list2); // 移动list2中的单个元素 list1.splice(pos, list2, elementIt); // 移动list2中的元素范围 list1.splice(pos, list2, startIt, endIt);
专用排序算法:
// 成员函数sort(比std::sort更高效) orders.sort(); // 默认使用operator< // 自定义排序 orders.sort([](const Order& a, const Order& b) { return a.amount > b.amount; // 按金额降序 });
链表合并:
// 合并两个有序链表 list1.merge(list2); // 注意:合并后list2为空
性能对比(vs vector)
操作 | std::list |
std::vector |
---|---|---|
随机访问 | O(n) | O(1) |
头部插入/删除 | O(1) | O(n) |
尾部插入/删除 | O(1) | O(1) 摊销 |
中间插入 | O(1) | O(n) |
内存连续性 | 否 | 是 |
内存开销 | 高(指针) | 低 |
最佳实践
适用场景:
- 需要频繁在任意位置插入/删除
- 不需要随机访问
- 需要稳定迭代器(不失效)
- 需要高效合并/拆分操作
不适用场景:
- 需要随机访问元素
- 内存受限环境
- 需要缓存友好的操作
现代C++技巧:
// 结构化绑定(C++17) for (const auto& [id, customer, amount] : orders) { std::cout << customer << ": $" << amount << "\n"; } // 自定义内存分配器 std::list<int, MyAllocator> customList;
经典应用场景
- LRU缓存实现:使用链表+哈希表
- 撤销/重做功能:维护操作历史
- 消息队列系统:高效插入/删除
- 图算法:邻接表表示
- 多线程任务池:任务调度