C++ std::vector 插入两个元素替代算法失败

Question

在我的项目中，我需要将两个元素插入到两个索引中。我正在实现替代实现而不是 vector 插入，因为两次插入调用移位 vector 元素两次，我可以用一次移位做同样的事情。但是，替代方案要慢得多。这种行为的解释是什么？

#include <vector>
#include <chrono>
#include <iostream>

void insert2(std::vector<int>& items, size_t first, size_t last, int item = -1) {
    // assert(last < items.size() + 2);
    // assert(first < last);
    // assert(0 <= first);
    // Creating two temporary objects
    // items.reserve(std::max(items.capacity(), items.size() + 2));
    items.emplace_back(); items.emplace_back();

    // Moving elements from the back to last
    for(auto p = items.end() - 1, q = items.begin() + last; p != q; --p) {
        // *p = std::move(*(p - 2));
        *p = *(p - 2);
    }
    // Emplace at last
    // new(&items[last]) ...
    items[last] = item;
    // Moving elements from last to first
    for(auto p = items.begin() + last - 1, q = items.begin() + first; p != q; --p) {
        // *p = std::move(*(p - 1));
        *p = *(p - 1);
    }
    // Emplace at first
    // new(&items[first]) ...
    items[first] = item;
}

auto now() {
    return std::chrono::steady_clock::now();
}

int main() {
    const size_t N = 100;
    const size_t M = 100;
    auto begin = now();

    begin = now();
    for(size_t n = 0; n < N; n++) { // run the same N times
        for(size_t i = 0; i < M + 1; i++) {
            for(size_t j = i + 1; j < M + 2; j++) {
                std::vector<int> v(M);
                insert2(v, i, j);
            }
        }
    }
    std::cout << "insert2 " << std::chrono::duration_cast<std::chrono::nanoseconds>(now() - begin).count() / (1000.0 * N) << "us\n";

    begin = now();
    for(size_t n = 0; n < N; n++) { // run the same N times 
        for(size_t i = 0; i < M + 1; i++) {
            for(size_t j = i + 1; j < M + 2; j++) {
                std::vector<int> v(M);
                v.insert(v.begin() + i, -1);
                v.insert(v.begin() + j, -1);
            }
        }
    }
    std::cout << "insert1 " << std::chrono::duration_cast<std::chrono::nanoseconds>(now() - begin).count() / (1000.0 * N) << "us\n";
}

我的 Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz 输出带 O0

insert2 7941.29us
insert1 4005.15us

与 O3，

insert2 763.64us
insert1 688.365us

Live demo on quick-bench

Answer 1

我使用了@MarekR 创建的基准并对其进行了修改，以便基准循环内不会发生(重新)分配，请参阅 http://quick-bench.com/UX9aEcrP06xBe51qKX3LjZWMU38 .然后我只对 vector 大小的 1/3 和 2/3 进行了一次双插入。对于包含 100 个整数元素(常量 N)的 vector ，自定义版本实际上速度较慢，但​​是，对于 1000 个元素，它已经更快了。而且，对于 1M 元素，自定义版本几乎快了 1.5 倍，这与备用元素“移动” 的数量相对应。使用 std::vector::insert，您需要移动 N 个元素，而使用自定义版本只需 N * 2/3。

老实说，我仍然不知道为什么自定义版本对于小 vector 的速度较慢。不管怎样，我想您可能也会对这个答案感兴趣。