Insertion into sorted vector [duplicate]

Question

How does one insert an element into a sorted vector such that after the insertion the vector is still sorted?

std::vector<int> myVec {1, 1, 3, 6, 9};

sortedInsert(myVec, 4);

for(auto& out : myVec) std::cout << out << " ";
std::cout << std::endl;

/*
* Expected output: 
* 1 1 3 4 6 9
*/

Answer 1

You can use the <algorithm> library function std::upper_bound to find where to insert the element.

#include <algorithm>

template <class T, class Compare = std::less<>>
std::vector<T>::iterator sorted_insert(std::vector<T>& vec, const T& val, Compare comp = Compare{}) {
    return vec.insert(std::upper_bound(vec.begin(), vec.end(), val, comp), val);
}

When doing a sorted insertion, the position at which you want to insert is just before an element that is greater than the value you want to insert. i.e:

std::vector<int> myVec { 1, 1, 3, 6, 9};
//                             ^
// A sorted insert on this vector with value = 2 would insert here

std::upper_bound returns an iterator to the first element in a sorted container that is greater than the value supplied, or, if there are no elements greater than the value supplied, std::upper_bound will return the end iterator of that sorted container.

Therefore, using a vector's insert method with the returned iterator from std::upper_bound will insert the supplied value such that the vector remains sorted post-insertion.