Inserting multiple values into a vector at specific positions

Question

Say I have a vector of integers like this std::vector<int> _data; I know that if I want to remove multiple items from _data, then I can simply call

_data.erase( std::remove_if( _data.begin(), _data.end(), [condition] ), _data.end() );

Which is much faster than eraseing multiple elements, as less movement of data is required within the vector. I'm wondering if there's something similar for insertions.

For example, if I have the following pairs

auto pair1 = { _data.begin() + 5, 5 };
auto pair2 = { _data.begin() + 12, 12 };

Can I insert both of these in one iteration using some existing std function? I know I can do something like:

_data.insert( pair2.first, pair2.second );
_data.insert( pair1.first, pair1.second );

But this is (very) slow for large vectors (talking 100,000+ elements).

EDIT: Basically, I have a custom set (and map) which use a vector as the underlying containers. I know I can just use std::set or std::map, but the number of traversals I do far outweighs the insertion/removals. Switching from a set and map to this custom set/map already cut 20% of run-time off. Currently though, insertions take approximately 10% of the remaining run time, so reducing that is important.

The order is also required, unfortunately. As much as possible, I use the unordered_ versions, but in some places the order does matter.

Answer 1

One way is to create another vector with capacity equal to the original size plus the number of the elements being inserted and then do an insert loop with no reallocations, O(N) complexity:

template<class T>
std::vector<T> insert_elements(std::vector<T> const& v, std::initializer_list<std::pair<std::size_t, T>> new_elements) {
    std::vector<T> u;
    u.reserve(v.size() + new_elements.size());
    auto src = v.begin();
    size_t copied = 0;
    for(auto const& element : new_elements) {
        auto to_copy = element.first - copied;
        auto src_end = src + to_copy;
        u.insert(u.end(), src, src_end);
        src = src_end;
        copied += to_copy;
        u.push_back(element.second);
    }
    u.insert(u.end(), src, v.end());
    return u;
}

int main() {
    std::vector<int> v{1, 3, 5};
    for(auto e : insert_elements(v, {{1,2}, {2,4}}))
        std::cout << e << ' ';
    std::cout << '\n';
}

Output:

1 2 3 4 5