12.1 序列容器

序列容器（Sequence Containers）将数据以线性（连续或链式）的方式组织起来。每个元素都有自己确定的相对位置，你可以明确指定把元素插入到序列的开头、中间还是末尾。

1. std::vector（动态数组）

std::vector 是 C++ 中最重要、最通用的容器。除非你有非常明确的理由拒绝它，否则在需要保存一组数据时，默认首选 vector。

• 底层结构：一块堆上分配的连续内存。
• 优点：支持随机访问（通过 [] 取值，时间复杂度 O(1)），CPU 缓存友好（连续内存访问极快），在末尾添加或删除元素非常快。
• 缺点：如果在头部或中间插入/删除元素，需要移动大量元素（O(N)）；当容量不足时会自动扩容，这涉及重新分配内存并拷贝所有旧元素。

#include <iostream>
#include <vector>

int main() {
    // 声明一个存 int 的 vector，通过初始化列表赋初值
    std::vector<int> nums = {10, 20, 30};

    // 在尾部追加元素（极快）
    nums.push_back(40);

    // 随机访问
    std::cout << "第二个元素是: " << nums[1] << "\n"; // 输出 20

    // 遍历
    for (int n : nums) {
        std::cout << n << " ";
    }
    return 0;
}

{% hint style=“info” %} 容量与大小： vector 有两个重要的概念：size()（当前有多少个元素）和 capacity()（当前分配了多少元素的预留空间）。你可以使用 reserve(N) 提前分配好空间，避免扩容带来的性能损耗。 {% endhint %}

2. std::deque（双端队列）

deque（读作 “deck”）是 Double-Ended Queue 的缩写。它可以看作是两个端点都开放的动态数组。

• 底层结构：多个分段连续的内存块组成的数组集合，由一个中央控制器管理。
• 优点：支持随机访问，同时允许在头部和尾部快速插入/删除（O(1)）。
• 缺点：内部结构比 vector 复杂，连续内存特性的优势不如 vector；中间插入/删除一样很慢。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {2, 3};

    d.push_back(4);    // 尾部追加: {2, 3, 4}
    d.push_front(1);   // 头部追加: {1, 2, 3, 4} (vector 没有这个方法！)

    std::cout << d[0] << "\n"; // 输出 1
}

3. std::list（双向链表）

std::list 就是数据结构课程中经典的双向链表。

• 底层结构：双向链表结构，每个元素节点除了存数据，还存了前后节点的指针。内存不连续。
• 优点：在序列的任何位置插入和删除元素都极快（O(1) 的开销，前提是找到了目标位置）。
• 缺点：不支持随机访问（不能写 list[5]，要找第 5 个元素只能从头遍历），由于内存碎片化导致 CPU 缓存命中率极差，额外内存开销大（存指针）。

#include <list>
#include <iostream>

int main() {
    std::list<int> l = {10, 20, 30};
    l.push_front(5);
    l.push_back(40);
    // 不能用 l[2]，只能通过迭代器遍历或查找
}

4. std::forward_list（单向链表，C++11）

forward_list 是只保存指向下一个元素指针的单向链表。 目的是为了提供一个空间和时间开销可以与手写 C 风格单链表相媲美的数据结构。它比 list 更省内存，但功能也更受限（不能轻易做到向后回溯，因为没有前置指针）。

5. std::array（静态数组，C++11）

是对 C 风格原生数组 int arr[N] 的超薄封装，保留了原生数组零开销的优势，同时拥有了面向对象的行为（获取 size、迭代器规范防越界等）。

• 大小在编译期就必须确定，不能扩容！分在栈上。

#include <array>

int main() {
    // 包含 5 个元素的静态数组
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    std::cout << arr.size(); // 输出 5
}

总结：序列容器怎么选？

需求场景	推荐容器
默认首选（绝大多数情况）	std::vector
频繁需要在头部和尾部增删元素	std::deque
频繁需要在中间增删元素，且不在乎随机访问	std::list
大小固定不变的数组	std::array