Keep Vector Elements Sorted
Explore how to maintain a sorted order in C++ vectors by implementing an insert_sorted function using STL algorithms like lower_bound and sort. Understand the method to insert elements efficiently without losing the vector's sorted property, and learn how this approach compares to other STL containers like sets and maps.
We'll cover the following...
The vector is a sequential container that keeps elements in the order in which they were inserted. It does not sort elements, nor change their order in any way. Other containers, such as set and map, keep elements sorted, but those containers are not random-access and may not have the features we need. We can, however, keep our vector sorted. It just requires a little bit of management.
How to do it
The idea with this recipe is to create a simple function, insert_sorted(), that inserts an element into the correct position in a vector to keep the vector sorted.
For convenience, we'll start with a type ...