第一节 · 取之不竭 · 顺序容器

在第一弹中，我们学习了 vector——一种动态数组。实际上，C++ 标准库提供了多种顺序容器，它们都用于存储和管理元素序列，但各有特点。

选择合适的容器，就像选择合适的工具——虽然锤子和扳手都能敲东西，但各有各的最佳使用场景。

---

顺序容器概览

容器	说明	特点
vector	动态数组	随机访问快，尾部增删快
deque	双端队列	随机访问快，两端增删快
list	双向链表	任意位置增删快，不支持随机访问
forward_list	单向链表	内存紧凑，只能单向遍历
array	固定数组	大小固定，性能最优
string	字符串	专门用于存储字符

---

deque：双端队列

deque（double-ended queue）在两端都可以高效地添加或删除元素：

#include <deque>
#include <iostream>
using namespace std;

int main()
{
    deque<int> d;
    
    // 在两端添加元素
    d.push_back(1);
    d.push_back(2);
    d.push_front(0);
    d.push_front(-1);
    // d: -1, 0, 1, 2
    
    // 在两端删除元素
    d.pop_front();
    d.pop_back();
    // d: 0, 1
    
    // 支持随机访问
    cout << d[0] << endl;  // 0
    cout << d.at(1) << endl;  // 1
    
    // 遍历
    for (int x : d)
        cout << x << " ";
    cout << endl;
    
    return 0;
}

deque 与 vector 的区别：

• vector：只在尾部高效增删

• deque：在头部和尾部都高效增删

• deque 的内存不连续，但支持随机访问

---

list：双向链表

list 是双向链表，在任意位置插入和删除都很高效，但不支持随机访问：

#include <list>
#include <iostream>
using namespace std;

int main()
{
    list<int> lst = {1, 2, 3, 4, 5};
    
    // 在两端操作
    lst.push_front(0);
    lst.push_back(6);
    
    // 在中间插入
    auto it = lst.begin();
    advance(it, 3);  // 移动到第 4 个位置
    lst.insert(it, 100);
    // lst: 0, 1, 2, 100, 3, 4, 5, 6
    
    // 删除元素
    lst.remove(100);  // 删除所有值为 100 的元素
    
    // 不支持随机访问
    // cout << lst[0];  // 错误！
    
    // 只能顺序遍历
    for (int x : lst)
        cout << x << " ";
    cout << endl;
    
    return 0;
}

list 的特有操作：

list<int> lst1 = {1, 3, 5};
list<int> lst2 = {2, 4, 6};

// 合并两个有序链表
lst1.merge(lst2);  // lst1: 1,2,3,4,5,6, lst2 变空

// 排序
list<int> lst = {5, 2, 8, 1, 9};
lst.sort();  // 1, 2, 5, 8, 9

// 反转
lst.reverse();

// 去除连续重复元素
list<int> lst3 = {1, 1, 2, 2, 2, 3};
lst3.unique();  // 1, 2, 3

// 移动元素
list<int> a = {1, 2, 3};
list<int> b = {4, 5, 6};
auto it = a.begin();
++it;  // 指向 2
a.splice(it, b);  // 将 b 的所有元素移动到 a 的 it 位置之前
// a: 1, 4, 5, 6, 2, 3
// b: 空

---

forward_list：单向链表

forward_list 是单向链表，比 list 更节省内存：

#include <forward_list>

forward_list<int> flst = {1, 2, 3, 4, 5};

// 只能在头部添加
flst.push_front(0);

// 在某个位置之后插入
auto it = flst.begin();
flst.insert_after(it, 100);  // 在第一个元素后插入
// flst: 0, 100, 1, 2, 3, 4, 5

// 删除某个位置之后的元素
flst.erase_after(it);
// flst: 0, 1, 2, 3, 4, 5

// 没有 size() 方法！需要用 distance
auto size = distance(flst.begin(), flst.end());

---

容器的通用操作

所有顺序容器都支持以下操作：

vector<int> v = {1, 2, 3, 4, 5};

// 大小相关
v.size();       // 元素个数
v.empty();      // 是否为空
v.max_size();   // 最大容量

// 访问元素
v.front();      // 第一个元素
v.back();       // 最后一个元素

// 迭代器
v.begin();      // 指向第一个元素
v.end();        // 指向最后一个元素之后
v.rbegin();     // 反向迭代器，指向最后一个元素
v.rend();       // 反向迭代器，指向第一个元素之前

// 修改
v.clear();      // 清空所有元素
v.assign({1, 2, 3});  // 重新赋值

// 交换
vector<int> v2;
v.swap(v2);     // 交换内容

---

容器适配器

除了基本容器，标准库还提供了容器适配器，它们基于其他容器实现特定的数据结构：

stack：栈（后进先出）

#include <stack>

stack<int> s;
s.push(1);
s.push(2);
s.push(3);

cout << s.top() << endl;  // 3
s.pop();
cout << s.top() << endl;  // 2
cout << s.size() << endl; // 2

queue：队列（先进先出）

#include <queue>

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

cout << q.front() << endl;  // 1
cout << q.back() << endl;   // 3
q.pop();
cout << q.front() << endl;  // 2

priority_queue：优先队列（堆）

#include <queue>

priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);

while (!pq.empty())
{
    cout << pq.top() << " ";  // 5 4 3 1 1（从大到小）
    pq.pop();
}

---

如何选择容器

• 需要随机访问：vector、deque、array

• 在中间频繁插入删除：list、forward_list

• 在两端频繁操作：deque

• 大小固定：array

• 存储字符：string

• 后进先出：stack

• 先进先出：queue

• 按优先级处理：priority_queue

默认情况下，优先选择 vector，除非有特殊需求。

---

习题

• 使用 deque 实现一个简单的撤销/重做功能。

• 使用 list 实现约瑟夫环问题。

• 比较 vector、list 在中间位置插入大量元素的性能差异。