向已排序的向量中插入元素并保持元素排序

Question

我有一个向量，希望在任何时候都对元素进行排序。当我插入一个元素并在弹出它们时保持元素排序，应该如何处理？我查看了 std::lower_bound，但那与我想要的相反。

例如，这就是我想要的：当我弹出向量中的所有元素时，它应该是 1 2 3 4 5。这意味着向量必须将它们存储为 5 4 3 2 1。如果使用 lower bound，则向量将它们存储为 1 2 3 4 5，并且弹出为 5 4 3 2 1。此外，将传递一个比较函数，以便 lower_bound 函数使用比较函数。是否有一种方法可以取反比较函数？

- OGH

---

顺便说一句，std::set 会使元素保持排序，但不能有重复元素（参见 std::multiset）。至于取反，则可以使用 std::not1。 - chris

也许您正在使用错误的容器。请在此处查看：https://dev59.com/TXRB5IYBdhLWcg3w6LV2#471461 - johnsyweb

Answer 1

为了始终保持向量的排序，您应该始终将新元素插入到适当的位置。由于您希望按升序弹出元素，并且向量仅提供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
}

- Slava