inserting element to a sorted vector and keeping elements sorted

Question

So I have a vector, and I want the elements to be sorted at all times. How should I go about inserting an element into that vector and keeping the elements sorted when I pop them out. I looked into std::lower_bound, however, that gave the opposite of what I wanted.

For example, this is what I want: When I pop all the elements in the vector it should be: 1 2 3 4 5. That means the vector has to store them as 5 4 3 2 1. If use lower bound, the vector stores them as 1 2 3 4 5, and it is popped as 5 4 3 2 1. Also, a compare functor is going to be passed in so that the lower_bound function uses the compare functor. Is there a way to take the opposite of a compare functor?

Answer 1

To keep your vector sorted all the time, you should always insert new elements into proper position. As you want to pop elements in ascending order and vector provides only pop_back() method you should sort elements in descending order. so first you need to find proper position and then insert there:

typedef std::vector<int> ints;

void insert( ints &cont, int value ) {
    ints::iterator it = std::lower_bound( cont.begin(), cont.end(), value, std::greater<int>() ); // find proper position in descending order
    cont.insert( it, value ); // insert before iterator it
}