std :: deque比std :: vector更快插入到最后？

Question

我开始比较:

• 插入列表的前面
• 插入向量的背面
• 插入一个双端队列的前面

但后来我注意到即使在push_back()deque上似乎也更快.我必须做一些错误的,我不能相信一个更一般的容器也不太可能超过一个特定的一个.

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

#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总是优于矢量.

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

我认为这-O3实际上是有帮助的; 当我关闭它时,我的deque性能会稍差一些.

Answer 1

我认为向量速度较慢，因为您调用的向量clear()可能会释放底层数组存储，具体取决于您的 STL 实现。

如果是这样的话，那么你的reserve()电话没有帮助；并且您的向量不断调整大小，这需要将每个元素移动到新的、更大的存储中。