Geek asks and answers

Insert an element into a sorted vector and save the sorting elements

So, I have a vector, and I want the elements to be sorted at any time. How should I insert an element into this vector and save the sorted elements when I pull them out. I looked in std::lower_bound, however, this gave the opposite of what I wanted.

For example, this is what I want: when I pop up all the elements in the vector, it should be: 1 2 3 4 5. This means that the vector should store them as 5 4 3 2 1. If you use the lower border, the vector saves them as 1 2 3 4 5, and it is set as 5 4 3 2 1. In addition, the comparison functor will be passed so that the function lower_bounduses the comparison function. Is there a way to take the opposite of the comparison functor?

+5
source share
1 answer

In order for your vector to be sorted all the time, you should always insert new elements in the correct position. Since you want to post elements in ascending order, and the vector provides only the pop_back () method, you must sort the elements in descending order. so first you need to find the correct position and then paste in 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
}
+22
source

More articles:


All Articles