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.

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

}

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).