C++ 将元素插入已排序的向量并保持元素已排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15048466/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
inserting element to a sorted vector and keeping elements sorted
提问by OGH
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.
所以我有一个向量，我希望元素在任何时候都被排序。我应该如何将一个元素插入该向量并在弹出它们时保持元素排序。std::lower_bound然而，我调查了，这与我想要的相反。
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_boundfunction uses the compare functor. Is there a way to take the opposite of a compare functor?
例如，这就是我想要的：当我弹出向量中的所有元素时，它应该是：1 2 3 4 5。这意味着向量必须将它们存储为 5 4 3 2 1。如果使用下限，向量将它们存储为 1 2 3 4 5，并弹出为 5 4 3 2 1。此外，将传入一个比较函子，以便lower_bound函数使用比较函子。有没有办法取比较函子的反面？
回答by Slava
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:
为了让您的向量一直排序，您应该始终将新元素插入到适当的位置。由于您想按升序弹出元素并且 vector 仅提供 pop_back() 方法，因此您应该按降序对元素进行排序。所以首先你需要找到合适的位置，然后在那里插入：
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
}
