How do I efficiently insert a list into a sorted vector while maintaining order?

Question

I want to insert the contents of an STL list into an existing vector, so that the vector is still sorted after the insertions.

Following is the code which I am trying to do it efficiently. Though it will work, I believe there should be a much better way of concatenating.

Vector V does has some elements prior to described merge operation.

Size(V) > Size(L)

If this information helps anymore.

void merge(std::list<int>& L, std::vector<int>& V) {
    for (auto& x : L) V.push_back(x);
    std::sort(V.begin(), V.end());
}

The code needs to be in C++14.

Answer 1

You can easily do this with vector::insert although I don't believe the implementation can efficiently get the distance from two bidirectional iterators so you may wish to reserve space to avoid unwanted vector resizing. At least since C++11 it appears that list::size must be constant time, so if you're at least on that version you can simply reserve enough space up front. Otherwise since you know that V is bigger than L just double the capacity of V before inserting:

V.reserve(V.size() + L.size());
V.insert(V.end(), L.begin(), L.end());