C++list
C++ STL list容器详解[编辑 | 编辑源代码]
std::list是C++标准模板库(STL)中提供的双向链表容器，在<list>头文件中定义。与vector和array不同，list不支持随机访问，但可以在任意位置高效插入和删除元素。
基本特性[编辑 | 编辑源代码]
- 双向链表结构：每个元素包含指向前驱和后继的指针
- 时间复杂度：
- 插入/删除：O(1)（已知位置时）
- 查找：O(n)
- 内存布局：非连续内存存储
- 迭代器类型：双向迭代器
声明与初始化[编辑 | 编辑源代码]
list提供多种初始化方式：
#include <list>
#include <iostream>
int main() {
// 1. 空list
std::list<int> list1;
// 2. 包含5个元素，每个值为10
std::list<int> list2(5, 10);
// 3. 通过初始化列表
std::list<int> list3 = {1, 2, 3, 4, 5};
// 4. 通过迭代器范围
int arr[] = {6, 7, 8};
std::list<int> list4(arr, arr + sizeof(arr)/sizeof(arr[0]));
// 输出验证
for(int n : list4)
std::cout << n << " ";
// 输出: 6 7 8
return 0;
}
常用成员函数[编辑 | 编辑源代码]
容量相关[编辑 | 编辑源代码]
- empty()：检查是否为空
- size()：返回元素数量
- max_size()：返回可容纳的最大元素数
元素访问[编辑 | 编辑源代码]
- front()：访问第一个元素
- back()：访问最后一个元素
修改操作[编辑 | 编辑源代码]
- push_front()/pop_front()：在头部插入/删除
- push_back()/pop_back()：在尾部插入/删除
- insert()：在指定位置插入
- erase()：删除指定位置元素
- clear()：清空容器
特殊操作[编辑 | 编辑源代码]
- splice()：转移元素到另一个list
- remove()/remove_if()：删除特定元素
- unique()：删除连续重复元素
- merge()：合并两个已排序list
- sort()：排序
- reverse()：反转元素顺序
详细示例[编辑 | 编辑源代码]
基本操作[编辑 | 编辑源代码]
#include <list>
#include <iostream>
int main() {
std::list<std::string> names;
// 添加元素
names.push_back("Alice");
names.push_front("Bob");
names.insert(++names.begin(), "Charlie"); // 在第二个位置插入
// 遍历输出
for(const auto& name : names)
std::cout << name << " ";
// 输出: Bob Charlie Alice
// 删除元素
names.remove("Bob"); // 删除值为"Bob"的元素
names.pop_back(); // 删除最后一个元素
std::cout << "\nSize after deletion: " << names.size();
// 输出: Size after deletion: 1
return 0;
}
高级操作示例[编辑 | 编辑源代码]
#include <list>
#include <algorithm>
#include <iostream>
int main() {
std::list<int> nums = {5, 3, 7, 1, 9, 2};
// 排序
nums.sort(); // list特有的排序方法
// 删除所有奇数
nums.remove_if([](int n) { return n % 2 != 0; });
// 合并两个list
std::list<int> other = {4, 8};
nums.merge(other);
// 输出结果
for(int n : nums)
std::cout << n << " ";
// 输出: 2 4 8
return 0;
}
性能分析[编辑 | 编辑源代码]
list与其它序列容器的比较：
| 操作 | list | vector | deque |
|---|---|---|---|
| 头部插入/删除 | O(1) | O(n) | O(1) |
| 尾部插入/删除 | O(1) | O(1) | O(1) |
| 中间插入/删除 | O(1) | O(n) | O(n) |
| 随机访问 | O(n) | O(1) | O(1) |
实际应用案例[编辑 | 编辑源代码]
场景1：高频插入删除[编辑 | 编辑源代码]
在游戏开发中，管理动态变化的实体列表：
class GameEntity {
// 实体类定义...
};
std::list<GameEntity> entities;
// 每帧更新
void updateGame() {
for(auto it = entities.begin(); it != entities.end(); ) {
if(it->shouldBeRemoved()) {
it = entities.erase(it); // 高效删除
} else {
it->update();
++it;
}
}
// 添加新实体
if(shouldSpawnNewEntity()) {
entities.emplace_back(createEntity());
}
}
场景2：LRU缓存实现[编辑 | 编辑源代码]
利用list的快速插入删除和顺序保持特性：
template<typename K, typename V>
class LRUCache {
std::list<std::pair<K, V>> items;
std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> keyToItem;
size_t capacity;
public:
LRUCache(size_t cap) : capacity(cap) {}
void put(const K& key, const V& value) {
auto it = keyToItem.find(key);
if(it != keyToItem.end()) {
items.erase(it->second);
keyToItem.erase(it);
}
items.push_front({key, value});
keyToItem[key] = items.begin();
if(items.size() > capacity) {
keyToItem.erase(items.back().first);
items.pop_back();
}
}
bool get(const K& key, V& value) {
auto it = keyToItem.find(key);
if(it == keyToItem.end()) return false;
items.splice(items.begin(), items, it->second); // 关键操作
value = it->second->second;
return true;
}
};
最佳实践与注意事项[编辑 | 编辑源代码]
1. 迭代器失效：只有被删除元素的迭代器会失效，其它迭代器保持有效 2. 内存使用：每个元素需要额外存储两个指针，内存开销较大 3. 缓存不友好：非连续存储可能导致缓存命中率低 4. 何时使用：
* 需要频繁在中间位置插入删除 * 不需要随机访问 * 需要稳定的迭代器和引用（元素地址不变）
数学特性[编辑 | 编辑源代码]
对于包含N个元素的list：
- 空间复杂度：O(N)
- 指针操作次数：插入/删除操作需要常数时间指针重定向（）
- 排序时间复杂度：（使用归并排序实现）