c++ - std::deque 在末尾插入是否比 std::vector 快？

Question

我开始比较:

• 插入列表的前面
• 插入 vector 的后面
• 插入双端队列的前端

但后来我注意到，即使在 push_back() 上，双端队列似乎也更快。我一定是做错了某事，我无法相信更通用的容器会优于特定的容器。

我的代码使用谷歌基准测试:

#include "benchmark/benchmark.h"
#include <deque>
#include <vector>

#define NUM_INS 1000

static void BM_InsertVector(benchmark::State& state) {
    std::vector<int> v;
    v.reserve(NUM_INS);
    while (state.KeepRunning()) {
        state.PauseTiming();
        v.clear();
        state.ResumeTiming();
        for (size_t i = 0; i < NUM_INS; i++)
            v.push_back(i);
    }
}
BENCHMARK(BM_InsertVector);

static void BM_InsertDeque(benchmark::State& state) {
    std::deque<int> v;
    while (state.KeepRunning()) {
        state.PauseTiming();
        v.clear();
        state.ResumeTiming();
        for (size_t i = 0; i < NUM_INS; i++)
            v.push_back(i);
    }
}
BENCHMARK(BM_InsertDeque);

BENCHMARK_MAIN();

结果:

Run on (1 X 2592 MHz CPU )
2016-02-18 14:03:47
Benchmark         Time(ns)    CPU(ns) Iterations
------------------------------------------------
BM_InsertVector       2820       2470     312500                                 
BM_InsertDeque        1872       1563     406977

我注意到在处理元素数量时一些差异，但 deque 总是优于 vector。

编辑:编译器:gcc 5.2.1 版编译:g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread

我认为 -O3 实际上是有用的；当我关闭它时，双端队列性能会稍微更差。

Answer 1

将元素持续添加到动态容器基本上有 3 个成本来源:

1. 内存管理。
2. 容器的内部簿记。
3. 需要对元素本身执行的任何操作。尤其;任何在插入时使引用无效的容器都可能四处移动/复制元素。

让我们从 1 开始。vector 不断要求双倍内存，而 deque 分配固定大小的 block (deque 通常实现为数组的数组，较低层的数组具有固定大小)。请求更多的内存可能比请求更少的内存花费更长的时间，但通常除非您的堆非常零散，否则一次请求大块是获得一些内存的最快方法。分配 1 meg 一次，然后请求 1 KB 1000 次可能更快。所以很明显 vector 最终会在这里占据优势(直到容器太大以至于受到碎片的影响)。然而，这不是最终的:您只要求 1000 个元素。我写了下面的代码http://coliru.stacked-crooked.com/a/418b18ff8a81c1c0 .它不是很有趣，但它基本上使用了一个简单的分配器，该分配器递增一个全局变量以查看执行了多少分配。

在您的基准测试过程中，vector 请求内存 11 次，而 deque 仅 10 次。deque 一直请求相同数量的内存, vector 要求加倍金额。同样，vector 必须调用 free 10 次。 deque 0。这似乎是 deque 的小胜利。

对于内部簿记，vector 的实现比deque 更简单。毕竟，vector 只是一个动态数组，而 deque 是一个数组数组，严格来说更复杂。所以这显然是 vector 的胜利。

最后，关于操作本身的元素。在 deque 中，没有任何东西被移动过。使用 vector，每个新的堆分配还涉及移动所有元素。它可能经过优化，可以将 memcpy 用于普通类型，但即便如此，也需要调用 10 次 memcpy 来复制 1、2、4、8 ... 512 个整数。这显然是 deque 的胜利。

我可以推测，加速到 O3 允许在 deque 中非常积极地内联许多更复杂的代码路径，从而减少 2 的权重。但显然，除非你做了一个更详细(非常小心!)的基准测试，你永远无法确定。

大多数情况下，这篇文章是为了表明它比简单的专用容器更复杂，而不是更通用的容器。不过我会做一个预测(把我的脖子伸出来，就像被切断一样):如果你增加元素的数量，即使增加 2 或 4 倍，你也不会看到 deque赢了。这是因为 deque 将进行 2 倍或 4 倍的堆分配，但 vector 只会增加 1-2 倍。

我不妨在这里注意到 deque 实际上是一种奇怪的数据结构；它在理论上是一个数组数组，但在许多实现中，数组要么是特定大小，要么只是一个元素，以较大者为准。此外，它的一些大 O 保证是无稽之谈。 push_back 只是固定的常数时间，因为在 C++ 中，只有对元素本身的操作才计入大 O。否则应该清楚，因为它是一个数组数组，所以顶级数组将是大小与已存储的元素数量成正比。最终，顶级数组用完了空间，您必须重新分配它，移动 O(N) 个指针。所以它不是真正的 O(1) push_back。