std::list是 C++
标准库中的双向链表容器，支持高效的元素插入和删除操作。以下是
std::list的完整 API 参考。
1. 构造函数
| 方法 |
描述 |
时间复杂度 |
list<T> l |
创建空 list |
O(1) |
list<T> l(count) |
创建包含 count 个默认构造元素的
list |
O(n) |
list<T> l(count, value) |
创建包含 count 个 value 的 list |
O(n) |
list<T> l(begin, end) |
用迭代器范围初始化 |
O(n) |
list<T> l(initializer_list) |
用初始化列表初始化 |
O(n) |
list<T> l(other_list) |
拷贝构造函数 |
O(n) |
list<T> l(move(other_list)) |
移动构造函数 |
O(1) |
2. 元素访问
| 方法 |
描述 |
时间复杂度 |
l.front() |
访问第一个元素 |
O(1) |
l.back() |
访问最后一个元素 |
O(1) |
l.begin() |
返回指向第一个元素的迭代器 |
O(1) |
l.end() |
返回指向末尾的迭代器 |
O(1) |
l.rbegin() |
返回反向迭代器（指向最后一个元素） |
O(1) |
l.rend() |
返回反向迭代器（指向第一个元素前） |
O(1) |
3. 容量操作
| 方法 |
描述 |
时间复杂度 |
l.empty() |
判断是否为空 |
O(1) |
l.size() |
返回元素数量 |
O(1) |
l.max_size() |
返回可容纳的最大元素数量 |
O(1) |
4. 修改操作
4.1 插入元素
| 方法 |
描述 |
时间复杂度 |
l.push_front(value) |
在头部插入元素 |
O(1) |
l.emplace_front(args...) |
在头部就地构造元素 |
O(1) |
l.push_back(value) |
在尾部插入元素 |
O(1) |
l.emplace_back(args...) |
在尾部就地构造元素 |
O(1) |
l.insert(pos, value) |
在 pos 前插入元素 |
O(1) |
l.insert(pos, count, value) |
在 pos 前插入 count 个 value |
O(n) |
l.insert(pos, begin, end) |
在 pos 前插入迭代器范围的元素 |
O(n) |
l.insert(pos, initializer_list) |
在 pos 前插入初始化列表的元素 |
O(n) |
4.2 删除元素
| 方法 |
描述 |
时间复杂度 |
l.pop_front() |
删除头部元素 |
O(1) |
l.pop_back() |
删除尾部元素 |
O(1) |
l.erase(pos) |
删除 pos 指向的元素 |
O(1) |
l.erase(begin, end) |
删除 [begin,end) 范围的元素 |
O(n) |
l.clear() |
清空所有元素 |
O(n) |
4.3 其他操作
| 方法 |
描述 |
时间复杂度 |
l.swap(other_list) |
交换两个 list 的内容 |
O(1) |
l.resize(count) |
调整大小 |
O(n) |
l.resize(count, value) |
调整大小并用 value 填充新元素 |
O(n) |
l.splice(pos, other_list) |
将 other_list 的所有元素移动到 pos
前 |
O(1) |
l.splice(pos, other_list, it) |
将 other_list 中 it 指向的元素移动到 pos
前 |
O(1) |
l.splice(pos, other_list, begin, end) |
将 other_list 中 [begin,end)
范围的元素移动到 pos 前 |
O(1) |
l.remove(value) |
删除所有等于 value 的元素 |
O(n) |
l.remove_if(pred) |
删除所有满足 pred 的元素 |
O(n) |
l.unique() |
删除连续重复元素 |
O(n) |
l.unique(pred) |
删除连续满足 pred 的重复元素 |
O(n) |
l.sort() |
排序（升序） |
O(n log n) |
l.sort(comp) |
使用 comp 排序 |
O(n log n) |
l.merge(other_list) |
合并两个已排序的 list |
O(n) |
l.merge(other_list, comp) |
使用 comp 合并两个已排序的 list |
O(n) |
l.reverse() |
反转 list |
O(n) |
5. 特殊操作详解
5.1 splice操作
splice是 list
特有的高效操作，可以在常数时间内将元素从一个 list 移动到另一个
list：
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};
list1.splice(list1.end(), list2);
|
5.2 sort和 merge
list 提供了自己的 sort和
merge实现，比通用算法更适合 list 的特性：
std::list<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6};
numbers.sort();
std::list<int> more_numbers = {7, 8, 0};
more_numbers.sort();
numbers.merge(more_numbers);
|
6. 性能提示
- 插入和删除操作在任何位置都是 O(1) 时间复杂度
- 随机访问效率低（O(n)），不适合频繁随机访问的场景
sort()成员函数比 std::sort()更适合
list，因为后者需要随机访问迭代器splice操作是 list 特有的高效操作- 相比 vector，list
的内存开销更大（每个元素需要额外存储前后指针）
7. 完整示例
#include <iostream>
#include <list>
#include <algorithm>
int main() {
std::list<int> nums = {2, 4, 6, 8};
nums.push_front(1);
nums.push_back(10);
nums.insert(std::next(nums.begin(), 2), 3);
nums.remove(4);
nums.erase(std::next(nums.begin(), 3));
for (int n : nums) {
std::cout << n << " ";
}
std::cout << "\n";
std::list<int> other = {5, 7, 9};
nums.splice(std::next(nums.begin(), 4), other);
nums.sort();
nums.unique();
nums.reverse();
auto it = std::find(nums.begin(), nums.end(), 7);
if (it != nums.end()) {
std::cout << "Found 7 at position "
<< std::distance(nums.begin(), it) << "\n";
}
return 0;
}
|
8. 与其他容器比较
| 特性 |
std::list |
std::vector |
std::forward_list |
| 底层实现 |
双向链表 |
动态数组 |
单向链表 |
| 随机访问 |
不支持（O(n)） |
支持（O(1)） |
不支持（O(n)） |
| 插入/删除 |
任意位置 O(1) |
末尾 O(1)，中间/开头 O(n) |
任意位置 O(1) |
| 内存开销 |
较高（每个元素两个指针） |
低（仅元素本身） |
中等（每个元素一个指针） |
| 迭代器类型 |
双向迭代器 |
随机访问迭代器 |
前向迭代器 |
| 适用场景 |
频繁任意位置插入删除 |
频繁随机访问 |
内存敏感的单向链表需求 |
std::list是需要在任意位置频繁插入删除元素的理想选择，如果需要随机访问或内存效率更高，可以考虑
std::vector。
