导入
简介
我们将研究的第一类容器是顺序容器。以下是各种顺序容器的主要特性列表。
顺序容器 有很多共同点，但每种容器都有其特定的应用场景。在深入细节之前，我们先对 std 命名空间中的五种顺序容器做一个总体概览。
| 特性 | Array | Vector | Deque | List | Forward List |
|---|---|---|---|---|---|
| 大小 | 静态 | 动态 | 动态 | 动态 | 动态 |
| 实现方式 | 静态数组 | 动态数组 | 数组序列 | 双向链表 | 单向链表 |
| 访问方式 | 随机访问 | 随机访问 | 随机访问 | 前向和后向访问 | 仅前向访问 |
| 插入和删除优化的位置 | --- | 尾部：O(1) | 头部和尾部：O(1) | 头部和尾部：O(1)；任意位置：O(1) | 头部：O(1)；任意位置：O(1) |
| 内存预分配 | --- | 是 | 否 | 否 | 否 |
| 内存释放 | --- | shrink_to_fit | shrink_to_fit | 始终 | 始终 |
| 优势 | 无需动态内存分配；内存需求最小 | 95% 场景下的理想选择 | 在头部和尾部进行插入与删除 | 在任意位置进行插入与删除 | 插入与删除速度快；内存需求最小 |
| 劣势 | 无法动态分配内存；内存管理受限 | 在任意位置插入与删除：O(n) | 在任意位置插入与删除：O(n) | 不支持随机访问 | 不支持随机访问 |
顺序容器
补充几点说明：
O(1) 表示操作的时间复杂度。O(1) 意味着操作的运行时间是常数，与容器大小无关。相反，O(n) 表示运行时间与容器中元素数量成线性关系。这对 std::vector 意味着什么？访问某个元素的时间与 std::vector 的大小无关，但若要插入或删除一个任意位置的元素，当元素数量增加 k 倍时，操作耗时也会大约增加 k 倍。
尽管 std::vector 和 std::deque 的元素随机访问都具有相同的复杂度 O(1)，但这并不意味着两者的访问速度相同。
对于双向链表（std::list）或单向链表（std::forward_list），插入或删除操作保证 O(1) 的复杂度，前提是迭代器指向正确的元素。
ℹ️ std::string 类似于 std::vector
虽然std::string不是标准模板库中的容器，但从行为上看，它类似于一个顺序容器，具体来说就是std::vector<char>。因此，我们将std::string视为std::vector<char>来处理。
在下一课中，我们将详细学习 std::array。