[数据结构·C++语法] 常见序列容器对比

简介

在 C++ STL (标准模板库) 中，序列容器（Sequence Containers）是这样一类容器，它们中的元素都按严格的线性顺序排列。每个元素都有其固定的位置，你可以访问“第一个”元素、“最后一个”元素或“第n个”元素。

最常见的序列容器包括：

std::vector
std::deque
std::list
std::array (C++11)
std::forward_list (C++11)
std::string (专门的字符序列容器)

下面我们将详细介绍前五个通用容器，并简要对比 std::string。

1. std::vector

头文件: <vector>
底层实现: 动态数组（连续内存）。

vector 是 C++ 中最常用、最灵活的序列容器。它将元素存储在一段连续的内存中，这使得它具有极高的随机访问（通过索引 []）性能。

核心特点:

优点: 随机访问速度最快 (O(1))。尾部插入/删除速度快（均摊 O(1)）。
缺点: 在中间或头部插入/删除元素非常慢 (O(n))，因为它需要移动之后的所有元素。
内存: 插入时若空间不足，会触发扩容（重新分配更大的内存块并拷贝所有元素），这可能导致所有迭代器、指针和引用失效。

常用方法

构造函数

vector(): 创建一个空 vector。
vector(size_type n, const T& val): 创建包含 n 个 val 副本的 vector。
vector(InputIt first, InputIt last): 用迭代器范围 [first, last) 构造。

迭代器 (Iterators)

begin() / cbegin(): 返回指向第一个元素的迭代器。
end() / cend(): 返回指向末尾（最后一个元素的下一个位置）的迭代器。
rbegin() / crbegin(): 返回指向反向序列的第一个元素（即正向的最后一个元素）。
rend() / crend(): 返回指向反向序列末尾的迭代器。

容量 (Capacity)

empty(): 检查是否为空 (O(1))。
size(): 返回元素数量 (O(1))。
max_size(): 返回可容纳的最大元素数。
capacity(): 返回当前已分配内存可容纳的元素总数（capacity() >= size()）。
reserve(n): 请求将 capacity() 更改为至少 n。如果 n > capacity()，会触发内存重分配。
shrink_to_fit(): (C++11) 请求释放未使用的内存，使 capacity() 约等于 size()。

元素访问 (Element access)

operator[n]: 访问第 n 个元素（不进行边界检查）。
at(n): 访问第 n 个元素（进行边界检查，越界会抛出 std::out_of_range 异常）。
front(): 访问第一个元素。
back(): 访问最后一个元素。
data(): (C++11) 返回指向底层连续内存数组的指针。

修改器 (Modifiers)

assign(): 赋新值（替换所有内容）。
push_back(const T& val): 在尾部添加一个元素。
pop_back(): 移除尾部的最后一个元素。
insert(iterator pos, ...): 在迭代器 pos 之前插入一个或多个元素。
erase(iterator pos): 移除 pos 处的元素。
erase(iterator first, iterator last): 移除 [first, last) 范围内的元素。
emplace_back(Args&&... args): (C++11) 在尾部就地构造一个元素，免去拷贝/移动。
emplace(iterator pos, Args&&... args): (C++11) 在 pos 之前就地构造一个元素。
clear(): 清空所有元素（size() 变为 0，capacity() 不一定变）。
swap(vector& other): 交换两个 vector 的内容。

2. std::deque

头文件: <deque> (发音 "deck"，double-ended queue)
底层实现: 双端队列（通常是分块的连续内存，即一个指向多个小内存块的索引）。

deque 提供了 vector 的大部分功能，但额外支持高效的头部插入和删除。它不是完全连续的内存。

核心特点:

优点: 随机访问较快 (O(1)，但常数比 vector 略大)。头部和尾部的插入/删除都是 O(1)。
缺点: 内存不连续。中间插入/删除仍然很慢 (O(n))。
迭代器: 迭代器比 vector 的复杂。在头部或尾部插入/删除不会使所有迭代器失效（但 vector 扩容会）。

常用方法

deque 拥有 vector 的绝大多数方法，包括：

迭代器: begin, end, rbegin, rend...
容量: empty, size, max_size, shrink_to_fit (注意：没有 capacity() 和 reserve()，因为它不是单块连续内存)。
元素访问: operator[], at, front, back。
修改器: assign, push_back, pop_back, insert, erase, emplace_back, emplace, clear, swap。

deque 特有的方法:

push_front(const T& val): 在头部添加一个元素。
pop_front(): 移除头部的第一个元素。
emplace_front(Args&&... args): (C++11) 在头部就地构造一个元素。

3. std::list

头文件: <list>
底层实现: 双向链表（每个节点存储元素，并有指向前一个和后一个节点的指针）。

list 擅长在序列的任意位置进行快速的插入和删除操作。

核心特点:

优点: 在任意位置（头部、尾部、中间）插入和删除元素都极快 (O(1))，只要你拥有指向该位置的迭代器。
缺点: 不支持随机访问（[] 或 at()）。要访问第 n 个元素，必须从头/尾遍历 n 次 (O(n))。
内存: 每个元素都有额外的指针开销。
迭代器: 插入操作不会使任何迭代器失效。删除操作只会使指向被删除元素的迭代器失效。

常用方法

迭代器 (Iterators)

begin, end, rbegin, rend... (与 vector 相同)

容量 (Capacity)

empty(), size(), max_size() (与 deque 相同，没有 capacity)

元素访问 (Element access)

front(): 访问第一个元素。
back(): 访问最后一个元素。
(注意: 没有 [], at(), data())

修改器 (Modifiers)

push_back(), pop_back()
push_front(), pop_front()
emplace_back(), emplace_front()
insert(iterator pos, ...)
emplace(iterator pos, ...)
erase(iterator pos)
clear(), swap(), assign()

`list` 特有的修改器（利用链表特性）

splice(iterator pos, list& other, ...): 移动（"拼接"）other 列表中的一个或多个元素到 pos 之前。这是 O(1) 操作，不会拷贝元素。
remove(const T& val): 移除所有等于 val 的元素。
remove_if(Predicate pred): 移除所有使 pred 为 true 的元素。
unique(): 移除连续的重复元素。
merge(list& other): 合并两个已排序的 list。
sort(): 对 list 进行原地排序（使用 <）。
reverse(): 反转 list 中元素的顺序。

4. std::array

头文件: <array> (C++11)
底层实现: 固定大小的数组（在栈上或静态数据区，行为类似 C 语言的 T arr[N]）。

array 是对 C 语言原始数组的封装，提供了 STL 容器的接口（如迭代器），但大小在编译时就已固定，不能改变。

核心特点:

优点: 性能与 C 数组完全相同。零开销抽象。支持 STL 算法。
缺点: 大小固定，无法动态增减。
模板参数: std::array<T, N> (T 是类型, N 是大小)。

常用方法

迭代器: begin, end, rbegin, rend...
容量: empty(), size(), max_size() (这三者都返回编译时的大小 N 或 0)。
元素访问: operator[], at, front, back, data()。
修改器: fill(const T& val) (用 val 填充整个数组), swap()。
(注意: 没有 push/pop_back/front, insert, erase, clear, reserve, capacity 等改变大小的操作)

5. std::forward_list

头文件: <forward_list> (C++11)
底层实现: 单向链表（每个节点只指向下一个节点）。

forward_list 是 C++ STL 中最轻量级的容器，它只支持 O(1) 的头部插入。它的设计目标是极致的内存效率（牺牲了 size() 和反向迭代）。

核心特点:

优点: 内存占用最低（每个元素只有一个指针开销）。
缺点: 只能单向遍历。没有 size() 方法 (获取大小需要 O(n) 遍历)。不支持 push_back, pop_back, back。
操作: 它的所有操作都是在某个元素之后 (after) 进行的，因为它没有前向指针。

常用方法

迭代器: before_begin(), begin(), end() (没有 rbegin/rend)。
容量: empty(), max_size() (注意：没有 size() 方法)。
元素访问: front() (没有 back, [], at)。
修改器:
- push_front(), pop_front(), emplace_front()。
- insert_after(iterator pos, ...): 在 pos 之后插入。
- emplace_after(iterator pos, ...): 在 pos 之后就地构造。
- erase_after(iterator pos): 移除 pos 之后的元素。
- clear(), swap(), assign()。
特有操作: splice_after(), remove(), remove_if(), unique(), merge(), sort(), reverse() (与 list 类似，但都是 _after 版本或基于前向迭代)。

总结：功能与复杂度对比

功能 / 操作	`vector`	`deque`	`list`	`array<T, N>`	`forward_list`
头文件	`<vector>`	`<deque>`	`<list>`	`<array>`	`<forward_list>`
底层	连续数组	分块数组	双向链表	C 数组	单向链表
随机访问 `[]` / `at()`	O(1)	O(1) (略慢)	O(n)	O(1)	O(n)
访问 `front()`	O(1)	O(1)	O(1)	O(1)	O(1)
访问 `back()`	O(1)	O(1)	O(1)	O(1)	O(n)
获取 `size()`	O(1)	O(1)	O(1)	O(1)	O(n) (无此方法)
头部插入 `push_front()`	O(n)	O(1)	O(1)	O(n) (无此方法)	O(1)
头部删除 `pop_front()`	O(n)	O(1)	O(1)	O(n) (无此方法)	O(1)
尾部插入 `push_back()`	均摊 O(1)	O(1)	O(1)	O(n) (无此方法)	O(n) (无此方法)
尾部删除 `pop_back()`	O(1)	O(1)	O(1)	O(n) (无此方法)	O(n) (无此方法)
中部插入 `insert()`	O(n)	O(n)	O(1)	O(n) (无此方法)	O(1) (需 `_after`)
中部删除 `erase()`	O(n)	O(n)	O(1)	O(n) (无此方法)	O(1) (需 `_after`)
迭代器失效性 (插入/删除时)	可能全部失效	可能全部失效	仅失效被删除的	N/A (大小固定)	仅失效被删除的

如何选择？ (经验法则)

默认首选: std::vector。
- 除非你有非常明确的理由，否则 vector 永远是你的第一选择。它的内存连续性带来的缓存友好性（Cache-friendly）使它在遍历和访问时表现最佳。
需要频繁在头部和尾部操作: std::deque。
- 当你需要一个“队列”或“双端队列”，并且同时还需要较快的随机访问（[]）时。
需要频繁在任意位置插入/删除: std::list。
- 当你的主要操作是在序列中部进行 insert, erase 或 splice，并且你不需要随机访问时。
大小固定且已知: std::array。
- 当你需要一个 C 数组，但又想获得 STL 容器的便利（如迭代器、size()）时。
内存受限且只需单向遍历: std::forward_list。
- 在性能和内存要求极其苛刻的场景下使用，这是最轻量的链表。

简介

1. std::vector

常用方法

构造函数

迭代器 (Iterators)

容量 (Capacity)

元素访问 (Element access)

修改器 (Modifiers)

2. std::deque

常用方法

3. std::list

常用方法

迭代器 (Iterators)

容量 (Capacity)

元素访问 (Element access)

修改器 (Modifiers)

list 特有的修改器（利用链表特性）

4. std::array

常用方法

5. std::forward_list

常用方法

总结：功能与复杂度对比

如何选择？ (经验法则)

`list` 特有的修改器（利用链表特性）