Insertion into sorted vector

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
*/

There are already questions and answers on exactly this topic, like [this one](https://stackoverflow.com/questions/15843525) or [this one](https://stackoverflow.com/questions/15048466); though your question and (self-)answer is a bit more concise, I'll give you that... — codeling, Apr 14 '22 at 10:13
@codeling imho it doesnt hurt to have duplicates around. I am just not sure which one to close as dupe of which ;) — 463035818_is_not_an_ai, Apr 14 '22 at 10:15
well the second link from codeling is very close to this one. I am closing this one as duplicate. Not because I think this is a poor question or answer! — 463035818_is_not_an_ai, Apr 14 '22 at 10:16
yeah I also don't feel too strongly about dupes; I posted the links mainly for reference, didn't vote to close (yet?); but this question here feels a bit like a "set up" to get points, with it's immediate *self-answer* — codeling, Apr 14 '22 at 10:17
@codeling writing questions/answers to get points isnt something bad, is it ? ;) — 463035818_is_not_an_ai, Apr 14 '22 at 10:18
If you have many insertions/removals switching to `std::set` instead might be worth a consideration... — Aconcagua, Apr 14 '22 at 10:20
@463035818_is_not_a_number not in and of itself but getting them via duplicate questions to which there are already perfectly good answers somewhere else doesn't feel right to me ;) — codeling, Apr 14 '22 at 10:21
@463035818_is_not_a_number I swear I'm not that annoying. I'm just blind. I guess having a duplicate Q/A is better than having to try and search through 10 year old questions with heaps of redundant answers. — fortytoo, Apr 14 '22 at 10:21
@spitconsumer i am completely with you. Finding q/as is difficult sometimes and having another duplicate as entry point can be good, especially when it is well written — 463035818_is_not_an_ai, Apr 14 '22 at 10:22
@463035818_is_not_a_number Ah, of course, should have been `std::multi_set` instead ;) — Aconcagua, Apr 14 '22 at 10:23
The [other one](https://stackoverflow.com/questions/15843525/how-do-you-insert-the-value-in-a-sorted-vector) would have been better duplicate – even better formatted answer... — Aconcagua, Apr 14 '22 at 10:26

fortytoo · Answer 1 · 2022-04-14T10:19:02.213

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.

Worth to note: `std::lower_bound` would work as well, sorting new elements *in front of* equal ones instead of behind – which would be less efficient with `std::vector` (more elements to move towards end) but more with e.g. `std::list` (insertion location found earlier, no moving needed). — Aconcagua, Apr 14 '22 at 10:18

Insertion into sorted vector

1 Answers1