CODEWITHSUNDEEP
c++c++11vectorc++14
alex berne
alex berne

Reputation: 699

Insert multiple elements at multiple offsets into an vector

I've got an vector<uint32_t> values and an vector<std::pair<uint32_t, uint_32_t>> updates that contains (a lot) accumulated updates to the vector, which I want to enact as cheaply as possible.

An update of {5, 12} should insert 12 right after the the values[5], not concerning any other modifications, i.e. values = {10,20,30} and updates = {{0,5}, {1, 6}, {2, 7}} should result in values = {10, 5, 20, 6, 30, 7}.

I want to modify the vector according to the updates vector like this:

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);
    }

}

If I'd allow duplicated update[i].first, I'd need to use std::stable_sort to keep the relative order.

Obviously, this code is quite slow, using O(n^2) time to move the remainder of the vector back one at a time. There should be a better solution.

There is a question on SO already, that is quite similar: Insert multiple values into vector. While there is an answer that I could use to update my vector in O(1) space and O(n) time, the question is quite old using c++03 and I wanted to know if there is a modern way to do that (or even, if I could avoid calling std::sort beforehand).

Upvotes: 0

Views: 129

Answers (1)

Quimby
Quimby

Reputation: 19123

Perhaps something like this should work. Since we know all updates, we know how much must each value be shifted to make space for the new ones. That is, exactly the amount equal to the number of updates with lower indices that the given value has. we can work from backwards, shifting the values by |updates| positions, insert the update with the highest index, shift the next batch by |updates-1| positions, insert the second-highest update...

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;
    }
}

This needs O(u log u) to sort the updates and O(u+n) to shift the old and add the new values. Only one resize is done. Note that resize zero-initializes the added values, the raw array would be slightly more efficient here. Or do some index magic with emplace_back.

Upvotes: 2

Related Questions