关于顺序容器的个人在学习与理解
文章详细介绍了五种常用的序列式容器：array、vector、deque、forward_list和list。每种容器的核心特点、复杂度分析以及代码示例均清晰明了。
前言
学过数据结构的同学们应该知道动态数组，双向链表，模拟栈，队列等基础数据结构的原理。比如我们在学习时，老师就要求我们使用数组，结构体等，实现模拟的循环队列双向链表等复杂的数据结构。 对于这种可能需要重复劳动的“体力活”，C++标准模板库（STL）对这些进行了封装，提供了一系列强大且灵活的容器，可大概分类为 这三类：
- 序列式容器
- 关联式容器
- 无序（关联式）容器
从名字可以看出：前者存在一个顺序，就像数组链表一样。后两者侧重于对应，类似哈希表。 本文将介绍序列式容器，也可说顺序型容器；
本文章侧重于容器的理解与核心，不涉及具体使用，如需具体使用方法，请访问:
- 具体用法Vector、List 更多请访问官网
核心
总览
序列式容器常用的共有5种：
- 数组(array)：定长的顺序表，C 风格数组的简单包装。
- 向量(vector)：后端可高效增加元素的顺序表。
- 双端队列(deque)：双端都可高效增加元素的顺序表。
- 单向列表(forward_list)：只能沿一个方向遍历的链表。
- 列表(list)：可以沿双向遍历的链表。
学过数据结构的应该清楚，前三者都是本质数组，后两者为链表。 没学过也不用担心，只要你知道什么是数组，什么是链表就够了，我们一个一个来介绍：
数组(array)
array本质就是一个数组，没什么可以说的：
特点：
- 固定大小
- 支持随机访问
- 不支持动态大小调整
复杂度分析：
- 访问：常数时间复杂度O(1)
- 尾部插入和删除：如允许，线性时间复杂度O(n)
- 中间插入和删除：如允许，线性时间复杂度O(n)
代码示例：
int main() {
std::array<int, 5> arr = {1, 2, 3, 4, 5};
arr[2] = 10; // 随机访问
for (const auto& elem : arr)
{
std::cout << elem << " ";
}
return 0;
}
向量(vector)
vector是动态数组，能够自动调整其大小。它的本质依然是数组。
数组(array)的不足在于，我定义了一个10个元素的数组，那么我想插入第11个元素，很显然不允许。那我应该怎么做，答案很粗暴简单，我开一个11元素的数组，把原来数组拷贝过来，插入第11个元素，把数组的头指针移过来，不就搞定了？ 对的，这就是动态数组的扩容机制，当然，大家也应该看到了，扩容操作是一个并不高效的操作，在实际运行时，往往都是倍增起步，即10个元素满了，有新的插入需求时直接倍增，扩充为20或更大的数组。
特点：
- 动态大小调整
- 支持随机访问
- 允许插入和删除操作，在末尾时时间复杂度为O(1)
复杂度分析：
访问：常数时间复杂度O(1) 尾部插入和删除：均摊常数时间复杂度O(1) 其他插入和删除：线性时间复杂度O(n)
代码示例：
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6); // 在末尾插入元素
vec[2] = 10; // 随机访问
for (const auto& elem : vec)
{
std::cout << elem << " ";
}
return 0;
}
可以看出，vector相比array，最大的改善就是允许直接插入删除，不在需要担心容量问题，是一个相当优秀的上位替代。
注意，Vector是常用的库,为重点，详细用法请参 考:具体用法Vector、List
双端队列(deque)
vector解决了一个问题，即直接从尾部插入删除元素，但是如果需要频繁更改头部元素呢？ 和数组一样，如果需要在头部增删一个数据，那么需要将后面所有元素都进行移动，如果频繁的插入删除，效率会很低。 回顾一下vector，vector之所以可以在尾部快速增删，本质是因为尾部并没有满，所谓的增删本质上是将尾部的空数据替换成要变更的数据。这个尾部实际上存在，只是被我们屏蔽了。 既然尾部可以这样操作，那首部可不可以呢？ 当然可以，定义10个元素的数组，然后在前面额外分配10个空间，后面额外分配10个空间，然后封装起来，当我们访问a[0]的时候，本质上是*a(10+0)。对的，这就是双端队列的核心思想。 当然，实际上的双端队列是分段存储的，实现要比vector复杂的多，但是正如前面这个例子，核心并不难。
特点：
- 双端高效插入和删除
- 支持随机访问
- 动态大小调整
复杂度分析：
- 访问：常数时间复杂度O(1)
- 两端插入和删除：常数时间复杂度O(1)
- 中间插入和删除：线性时间复杂度O(n)
代码示例：
int main() {
std::deque<int> deq = {1, 2, 3, 4, 5};
deq.push_front(0); // 在前端插入元素
deq.push_back(6); // 在末尾插入元素
for (const auto& elem : deq) {
std::cout << elem << " ";
}
return 0;
}
实际使用中，需要根据实际需要进行选择，并无明显的 优劣之分。
单向列表(forward_list)
单向列表就是一个普通的单向链表，每一个元素保存当前元素的内容和下一个元素的地址。
特点：
- 只能沿一个方向遍历
- 高效的头部插入和删除
复杂度分析：
- 访问：线性时间复杂度O(n)
- 头部插入和删除：常数时间复杂度O(1)
- 其他插入和删除：线性时间复杂度O(n)
关于增删复杂度，这里认为没有相关引用，即首先查询，然后增删。 关于其他情况，假如向单向列表ABC中，在B后插入元素D； 如果已经有要插入位置上一个元素B的引用，则为O(1)。 如果已经有要插入位置下一个元素C的引用，我们无法得到B的位置，则依然需要先查询到B，才可以进行插入。 总之，具体情况需要进行分析。
代码示例：
int main() {
std::forward_list<int> flist = {1, 2, 3, 4, 5};
flist.push_front(0); // 在头部插入元素
for (const auto& elem : flist) {
std::cout << elem << " ";
}
return 0;
}
列表(list)
list是双向链表，可以沿双向遍历。每个元素保存当前元素的内容，上一个和下一个元素的地址。
特点：
- 高效的插入和删除操作
- 支持双向遍历
- 动态大小调整
复杂度分析：
访问：线性时间复杂度O(n) 首部和尾部插入和删除：常数时间复杂度O(n) 其他位置插入和删除：常数时间复杂度O(n)
同前面单向列表，这里假设不知道插入位置相关的引用，故需要先遍历链表查询位置。
代码示例：
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
lst.push_back(6); // 在末尾插入元素
lst.push_front(0); // 在前端插入元素
for (const auto& elem : lst) {
std::cout << elem << " ";
}
return 0;
}
总结与理解
简单总结一下各个顺序容器：
- array：适用于大小固定且需要随机访问的场景，但不支持动态调整大小。
- vector：适用于需要动态调整大小且尾部插入和删除操作频繁的场景，是大多数情况下的首选容器。
- deque：适用于需要双端高效插入和删除操作的场景，结合了数组和链表的优点。
- forward_list：适用于需要高效头部插入和删除且不需要双向遍历的场景，内存占用较低。
- list：适用于需要双向遍历和高效插入删除操作的场景，提供了最大的灵活性。
顺序容器是C++ STL中最常用的容器之一，也是算法比赛，项目开发中常用的数据结构，熟练使用可以大大提升编程的灵活性。尽管有些地方认为STL是模版编程，将它归为高级特性，但事实就是，灵活使用STL是一个重要的基本功。