wstawiając element do posortowanego wektora i zachowując elementy posortowane

Question

Tak więc mam wektor i chcę, aby elementy były sortowane przez cały czas. Jak mam wstawić element do tego wektora i zachować elementy posortowane, kiedy je wyskakuję. Spojrzałem jednak na std::lower_bound, które dało odwrotność tego, co chciałem.

Na przykład to jest to, czego chcę: po naciśnięciu wszystkich elementów w wektorze powinno być: 1 2 3 4 5. Oznacza to, że wektor musi je przechowywać jako 5 4 3 2 1. Jeśli jest używany dolna granica, wektor przechowuje je jako 1 2 3 4 5, i jest popped jako 5 4 3 2 1. Ponadto, funktor porównania zostanie przekazany, aby funkcja lower_bound używała funkcji porównania. Czy istnieje sposób na przeciwstawienie się funktorowi porównania?

Answer 1

Aby zachować wektor posortowany przez cały czas, należy zawsze wstawiać nowe elementy do właściwej pozycji. Aby elementy pop rosły w porządku rosnącym, a wektor zapewnia tylko metodę pop_back(), należy posortować elementy w porządku malejącym. więc najpierw trzeba znaleźć właściwą pozycję, a następnie wstawić tam:

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 
}