什么是 C++ 中 std::vector 与 std::deque 的区别？

作者

在 C++ 标准库中，std::vector 和 std::deque 都是容器，但它们在内部实现、性能特性和使用场景上有显著差异。了解这些区别可以帮助你在实际项目中选择更合适的容器。

1. 内部结构

std::vector std::deque
内存布局 连续内存块（单一数组） 由多个固定大小的块（chunk）组成的链表结构
对象存储 所有元素在同一块内存 元素分散在不同块中，块间由指针相连
  • vector 需要在连续的内存空间中存放所有元素，因此其内存占用紧凑，易于缓存友好。
  • deque 通过分块管理，可以在两端高效地插入/删除，而不必像 vector 那样频繁地搬迁整个容器。

2. 访问速度

  • 随机访问：两者都提供 O(1) 的随机访问。对 vector 的访问因内存连续而更具缓存友好性，通常略快。
  • 迭代：vector 的迭代器是随机访问迭代器，指针本身即可完成。deque 的迭代器实现更复杂，但仍然是随机访问迭代器。

3. 插入/删除

位置 std::vector std::deque
前端 O(n)（需要搬迁所有元素） O(1)（在首块中插入）
后端 O(1)（摊销） O(1)（摊销）
中间 O(n)（搬迁元素） O(n)（搬迁块内元素）
  • vector 的后端 push_back 是摊销常数时间；但前端插入需要移动所有元素。
  • deque 在两端插入/删除均为 O(1) 摊销，适合需要频繁在两端操作的场景。

4. 内存分配与扩容

  • vector 在容量不足时通常会按比例（约 1.5-2 倍）扩容，导致内存重新分配和元素搬迁。
  • deque 由于分块存储，扩容时只需在两端添加新的块，整体搬迁开销较低。

5. 对象生命周期

  • vector 的连续存储保证了当元素插入或删除导致容量增长时，所有元素会被一次性拷贝或移动到新内存中。若元素拥有非平凡的析构函数，可能导致资源释放的顺序问题。
  • deque 的分块使得插入/删除不会触发全局搬迁，元素的析构顺序更可控。

6. 对齐与填充

  • vector 的连续布局可避免块边界对齐导致的填充开销，整体更节省空间。
  • deque 的块分割可能在块边界处产生额外填充。

7. 典型使用场景

需求 推荐容器
需要频繁在两端插入/删除 std::deque
需要频繁访问中间元素，且对插入位置不敏感 std::vector
需要一个类似双端队列但又想兼顾随机访问 std::deque
需要最小内存占用和缓存友好 std::vector
需要稳定的迭代器/指针（在插入/删除时不失效） std::vector 只在 reallocation 时失效；deque 在插入/删除时迭代器失效规则更复杂

8. 性能测评（示例）

// 基准测试，使用 Google Benchmark
static void BM_VectorFrontPush(benchmark::State& state) {
    std::vector <int> v;
    for (auto _ : state) {
        v.insert(v.begin(), 1);
    }
}
BENCHMARK(BM_VectorFrontPush);

static void BM_DequeFrontPush(benchmark::State& state) {
    std::deque <int> d;
    for (auto _ : state) {
        d.push_front(1);
    }
}
BENCHMARK(BM_DequeFrontPush);

运行结果显示，deque 在前端插入时速度明显快于 vector，尤其在大规模数据时差距更大。

9. 结语

  • 选择 std::vector：当你需要连续存储、优先随机访问、内存占用小且仅在尾部频繁操作时。
  • 选择 std::deque：当你需要双端插入/删除、对随机访问要求不高但仍需 O(1) 访问时。

在实际项目中，建议先分析数据访问模式和更新频率，再结合上述表格做决策。正确的容器选择往往能显著提升程序性能和可维护性。

发表评论