c++ - 将多个元素以多个偏移量插入到 vector 中

Question

我有一个 vector<uint32_t> values和一个 vector<std::pair<uint32_t, uint_32_t>> updates包含(大量)对 vector 的累积更新，我希望尽可能便宜地执行这些更新。

{5, 12} 的更新应该插入 12在values[5]之后, 不涉及任何其他修改，即 values = {10,20,30}和 updates = {{0,5}, {1, 6}, {2, 7}}应该导致 values = {10, 5, 20, 6, 30, 7} .

我想根据 updates 修改 vector 像这样的 vector :

static void update(std::vector<uint32_t>& values,
    std::vector<std::pair<uint32_t, uint32_t>> updates) {
    std::sort(updates.begin(), updates.end(),
        [](std::pair<uint32_t, uint32_t> a, std::pair<uint32_t, uint32_t> b){
             return a.first < b.first;
        });
    values.reserve(values.size()+updates.size());
    for(uint32_t i = 0; i < updates.size(); ++i){
        values.insert(values.begin()+i+updates[i].first, updates[i].second);
    }

}

如果我允许重复 update[i].first ，我需要使用 std::stable_sort保持相对顺序。

显然，这段代码很慢，使用了O(n^2)一次将 vector 的其余部分移回一个位置的时间。应该有更好的解决方案。

SO 上已经有一个问题，非常相似:Insert multiple values into vector .虽然在 O(1) 中有一个答案可以用来更新我的 vector 空间和O(n)时间，使用 c++03 的问题已经很老了，我想知道是否有一种现代方法可以做到这一点(或者甚至，如果我可以避免事先调用 std::sort)。

Answer 1

也许这样的事情应该有效。因为我们知道所有更新，所以我们知道每个值必须移动多少才能为新值腾出空间。也就是说，恰好等于给定值具有较低索引的更新次数。我们可以从后向工作，将值移动 |updates| 个位置，插入具有最高索引的更新，将下一批移动 |updates-1| 个位置，插入第二高的更新...

static void update(std::vector<uint32_t>& values,
    std::vector<std::pair<uint32_t, uint32_t>> updates) {
    std::sort(updates.begin(), updates.end(),[](auto a, auto b){
             return a.first > b.first;//From highest to lowest indices.
        });

    const std::size_t N = values.size();
    std::size_t K = updates.size();
    values.resize(N+K);
    std::size_t end = N;
    for(auto [i,v]:updates){
        //Shift the values in [i+1,end) K positions right
        std::move_backward(values.begin()+i+1,
                           values.begin()+end,
                           values.begin()+end+K);
        //Insert the update
        values[i+K]=v;
        //Preceding values are shifted only by K-1 positions
        --K;
        //Already shifted values
        end=i+1;
    }
}

这需要 O(u log u) 对更新进行排序，需要 O(u+n) 移动旧值并添加新值。只完成了一个resize。请注意，resize 零初始化添加的值，原始数组在这里会稍微更有效。或者用 emplace_back 做一些索引魔术。