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

Question

在我的项目中，我需要将两个元素插入两个索引中。我正在实现一种替代实现，而不是向量插入，因为两个插入调用两次将向量元素移位，并且我可以一次移位来完成相同的操作。但是，替代方案要慢得多。对此行为的解释可能是什么？

#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®Core™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。然后我只对向量大小的 1/3 和 2/3 进行了一次双插入。对于包含 100 个整数元素（常量 ）的向量N，自定义版本实际上较慢，但是，对于 1000 个元素，它已经更快了。而且，对于 1M 个元素，自定义版本几乎快了 1.5 倍，这与备用元素“移动”的数量相对应。使用 时std::vector::insert，您需要移动N元素，而使用自定义版本时仅需要移动元素N * 2 / 3。

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