序列式容器：vector、deque、list、forward_list、array 的使用与底层原理

大家好，我是你们的老朋友。今天我们来聊聊 C++ 里最常用、也最容易踩坑的一类容器——序列式容器。说白了，就是那些能按顺序存放数据的家伙。vector、deque、list、forward_list、array，这五个名字你肯定不陌生。但你真的了解它们背后的脾气秉性吗？

我个人习惯，在项目里选容器之前，一定会先问自己三个问题：数据量多大？插入删除频繁吗？需要随机访问吗？这三个问题问完，选哪个容器基本就定了。别急，我们一个一个来看。

1. vector：最常用的“动态数组”

vector 是我用得最多的容器，没有之一。它的底层原理其实很简单：一块连续的内存空间。就像 C 语言的数组，但多了自动扩容的能力。

为什么 vector 访问元素那么快？因为连续内存嘛，地址直接算出来，O(1) 的随机访问。我在项目中遇到过，用 vector 存了上百万个点云数据，遍历起来嗖嗖的。

但 vector 有个“软肋”——插入和删除。尤其是头部插入，那叫一个慢。为什么呢？因为要挪动后面所有元素。你想想看，如果 vector 里有 10 万个元素，你在头部插一个，后面 10 万个都得往后挪一位。这谁受得了？

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec;
    vec.reserve(100);  // 我建议提前预留空间，避免频繁扩容
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
    }
    // 随机访问
    std::cout << vec[5] << std::endl;  // O(1)
    // 头部插入（慢！）
    vec.insert(vec.begin(), 99);  // 所有元素后移
    return 0;
}

2. deque：双端队列，两头都快

deque 的全称是 double-ended queue。它的设计初衷就是解决 vector 在头部操作慢的问题。deque 在头部和尾部插入删除都是 O(1)，厉害吧？

那它是怎么做到的？deque 的底层不是一块连续的大内存，而是一块一块的“小内存块”拼起来的。每个小内存块叫一个 buffer，这些 buffer 的地址被一个中央控制器（map）管理着。

说白了，deque 像是一串珠子，每个珠子是一段连续内存，珠子之间用线串着。这样在头部插入时，只需要在最前面加一个新珠子就行，不用挪动后面的数据。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;
    dq.push_back(10);   // 尾部插入
    dq.push_front(20);  // 头部插入，O(1)
    std::cout << dq[0] << std::endl;  // 随机访问，但比 vector 慢一点点
    return 0;
}

3. list：双向链表，插入删除的王者

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

但代价是什么？随机访问是 O(n)。你想访问第 5 个元素？对不起，得从头开始一个一个往后找。另外，每个节点额外存储两个指针，内存开销比 vector 大得多。

我记得有一次，我在一个需要频繁在中间插入删除的模块里用了 list，代码写起来很爽，但跑起来发现内存占用比预期高了一倍。后来我仔细一算，每个节点多 16 字节（64 位系统下两个指针），100 万个节点就是 16MB 的额外开销。嗯，这得权衡。

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto it = lst.begin();
    std::advance(it, 2);  // 移动到第 3 个元素，O(n)
    lst.insert(it, 99);   // 插入，O(1)
    // 遍历
    for (int x : lst) {
        std::cout << x << " ";
    }
    return 0;
}

4. forward_list：单向链表，更轻量

forward_list 是 C++11 引入的，它比 list 更“抠门”——只保存单向指针，所以内存更小，但只能单向遍历。你想想看，如果你只需要从头到尾遍历，不需要往回走，那 forward_list 就够用了。

它的插入删除也是 O(1)，但要注意，因为只有单向指针，在某个节点前面插入会比较麻烦，需要先找到前一个节点。所以 forward_list 的设计更偏向于“在头部操作”的场景。

#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> flst = {1, 2, 3, 4};
    flst.push_front(0);  // 头部插入，O(1)
    // 只能单向遍历
    for (int x : flst) {
        std::cout << x << " ";
    }
    return 0;
}

5. array：固定大小的数组

array 是 C++11 对原生数组的封装。它的大小在编译期就固定了，不能动态改变。那它有什么用呢？

我个人觉得，array 最大的价值在于：它提供了 STL 容器的接口，比如 begin()、end()、size()，还能用范围 for 循环。而且它不会像原生数组那样隐式转换成指针，更安全。

#include <array>
#include <iostream>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    std::cout << "Size: " << arr.size() << std::endl;
    // 安全访问
    std::cout << arr.at(3) << std::endl;  // 带边界检查
    return 0;
}

6. 迭代器失效问题——避坑指南

迭代器失效，是 C++ 序列式容器里最让人头疼的问题之一。我曾经在一个多线程项目里，因为迭代器失效导致数据错乱，查了整整两天才找到原因。嗯，从那以后我再也不敢忽视它了。

什么是迭代器失效？简单说，就是容器内部结构变了，导致之前拿到的迭代器指向了错误的位置或野指针。

不同容器的失效情况不一样，我整理了一个表格，方便你对照：

容器	插入操作	删除操作	扩容/重新分配
vector	如果插入导致扩容，所有迭代器失效；否则只有插入点之后的迭代器失效	删除点之后的迭代器失效	所有迭代器失效
deque	头部/尾部插入不失效；中间插入导致所有迭代器失效	头部/尾部删除只影响被删元素；中间删除导致所有迭代器失效	不适用（无扩容概念）
list	所有迭代器都不失效（除了被删的那个）	只有被删元素的迭代器失效	不适用
forward_list	所有迭代器都不失效（除了被删的那个）	只有被删元素的迭代器失效	不适用
array	不支持插入	不支持删除	不适用

// 错误示例：遍历时删除，迭代器失效
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it);  // 失效！it 已经无效了
    }
}

// 正确做法：利用 erase 的返回值
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 3) {
        it = vec.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

7. 知识体系总览

下面这张 SVG 图帮你梳理了本章的核心知识点，包括五个容器的特点、底层结构以及迭代器失效的对比。建议你保存下来，以后选容器时拿出来看一眼。

8. 总结与个人建议

好了，五个容器都讲完了。最后我分享一点个人经验：

• 默认选 vector：除非你有明确的理由不用它。因为 vector 的缓存局部性最好，遍历速度最快。
• 需要双端操作选 deque：比如队列、双端队列场景。
• 需要频繁中间插入删除选 list：但要注意内存开销。
• 内存极度敏感且单向遍历选 forward_list：嵌入式、低内存场景首选。
• 固定大小且需要 STL 接口选 array：比原生数组安全。

记住，没有完美的容器，只有最适合当前场景的容器。选对了，代码跑得又快又稳；选错了，调试起来能让你怀疑人生。嗯，我当年就吃过这个亏，希望你不用再踩一遍。