inserendo un elemento in un vettore ordinato e mantenendo gli elementi ordinati

Question

Quindi ho un vettore e voglio che gli elementi siano ordinati in ogni momento. Come dovrei fare per inserire un elemento in quel vettore e mantenere ordinati gli elementi quando li faccio uscire. Ho esaminato std::lower_bound, tuttavia, questo ha dato il contrario di ciò che volevo.

Ad esempio, questo è quello che voglio: Quando ho pop tutti gli elementi nel vettore dovrebbe essere: 1 2 3 4 5. Ciò significa che il vettore deve memorizzarli come 5 4 3 2 1. Se l'uso limite inferiore, il vettore li memorizza come 1 2 3 4 5, ed è spuntato come 5 4 3 2 1. Inoltre, un functor di confronto verrà passato in modo che la funzione lower_bound utilizzi il functor di confronto. C'è un modo per prendere l'opposto di un funtore comparativo?

Answer 1

Per mantenere sempre ordinato il vettore, è necessario inserire sempre nuovi elementi nella posizione corretta. Poiché si desidera eseguire il pop degli elementi in ordine ascendente e il vettore fornisce solo il metodo pop_back(), è necessario ordinare gli elementi in ordine decrescente. quindi prima è necessario trovare la posizione corretta e quindi inserire lì:

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 
}