20. STL顺序容器：vector、deque、list、forward_list、array、容器适配器

聊到STL容器，我个人觉得这是C++里最实用的部分之一。你想想看，写程序天天跟数据打交道，怎么存、怎么取、怎么删，这些基础操作要是都得自己手写链表、动态数组，那得累死。STL帮我们把这些活儿都干了，而且干得还挺漂亮。

这一章咱们重点看顺序容器。说白了，就是元素按顺序排成一列，你插在哪儿它就在哪儿。跟关联容器那种按key找东西的思路不一样。

20.1 vector——最常用的动态数组

vector 是我用得最多的容器，没有之一。它本质上就是一个动态数组，内存连续，支持随机访问。你拿下标取元素，O(1) 时间，爽得很。

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    vec.push_back(6);           // 尾部插入
    vec.pop_back();             // 尾部删除
    
    std::cout << vec[2];        // 随机访问，O(1)
    std::cout << vec.at(2);    // 带边界检查的访问
    
    vec.insert(vec.begin() + 2, 99);  // 中间插入，会移动元素
    vec.erase(vec.begin() + 1);       // 中间删除
    
    return 0;
}

20.2 deque——双端队列

deque 的全称是 double-ended queue。它跟 vector 最大的区别是：头尾插入删除都是 O(1)。

deque 的内存不是一整块连续的，而是分成多个固定大小的块。所以它支持随机访问，但比 vector 稍微慢一点点。不过头尾操作快很多。

#include <deque>

std::deque<int> dq = {10, 20, 30};
dq.push_front(5);    // 头部插入，O(1)
dq.push_back(40);    // 尾部插入，O(1)
dq.pop_front();      // 头部删除，O(1)
dq.pop_back();       // 尾部删除，O(1)

// 随机访问依然支持
std::cout << dq[1];

20.3 list——双向链表

list 是双向链表。每个节点包含数据、前驱指针和后继指针。它的优势在于：任意位置插入删除都是 O(1)，只要你已经有那个位置的迭代器。

但代价也很明显：不支持随机访问。你想取第5个元素？得从头遍历过去，O(n)。

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};

auto it = lst.begin();
std::advance(it, 2);      // 移动到第3个元素
lst.insert(it, 99);       // 在迭代器位置插入，O(1)

lst.remove(3);            // 删除所有值为3的元素
lst.sort();               // list 自带排序

20.4 forward_list——单向链表

forward_list 是 C++11 引入的。它比 list 更省内存，因为每个节点只保存一个后继指针。但代价是只能单向遍历。

说实话，我平时用得不多。除非你特别在意内存占用，或者你的场景确实只需要单向遍历，否则用 list 更省心。

#include <forward_list>

std::forward_list<int> flst = {1, 2, 3, 4};
flst.push_front(0);       // 只能在头部插入
flst.pop_front();         // 只能在头部删除

// 没有 size() 方法！需要自己遍历计数

20.5 array——固定大小数组

array 是 C++11 的另一个新成员。它跟普通数组一样，大小在编译期就固定了。但它是个容器，有 STL 的接口，比如 begin()、end()、size()。

#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};
std::cout << arr.size();    // 输出 5
std::cout << arr[3];        // 随机访问

// 跟普通数组比，多了边界检查的 at()
std::cout << arr.at(10);    // 会抛出 std::out_of_range 异常

20.6 容器适配器

容器适配器不是独立的容器，而是基于其他容器实现的接口封装。说白了，就是给你一个更简单的操作界面。

stack——栈

后进先出（LIFO）。底层默认用 deque，但也可以指定 vector 或 list。

#include <stack>

std::stack<int> stk;
stk.push(1);
stk.push(2);
stk.push(3);

while (!stk.empty()) {
    std::cout << stk.top();  // 查看栈顶
    stk.pop();                // 弹出栈顶
}
// 输出：321

queue——队列

先进先出（FIFO）。底层默认也是 deque。

#include <queue>

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);

while (!q.empty()) {
    std::cout << q.front();  // 查看队首
    q.pop();                  // 弹出队首
}
// 输出：123

priority_queue——优先队列

每次取出的都是最大（或最小）的元素。底层默认用 vector，内部用堆（heap）实现。

#include <queue>

std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(2);

while (!pq.empty()) {
    std::cout << pq.top();   // 每次取最大值
    pq.pop();
}
// 输出：4321

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

20.7 知识体系总览

下面这张图帮你理清这些容器的关系。我建议你把它存下来，面试前看一眼都管用。

20.8 如何选择？

说实话，这个问题没有标准答案。我一般按这个思路来选：

1. 默认用 vector——大多数场景它都够用，而且性能好
2. 需要头尾操作——换 deque
3. 需要中间频繁插入删除——用 list
4. 内存极度受限——考虑 forward_list
5. 大小编译期已知——用 array
6. 需要特定访问模式——用对应的适配器