c++ - seleccion - ordenamiento burbuja

¿Es posible forzar el conjunto de STL para reevaluar el predicado?

Question

Considere las siguientes estructuras de datos y código.

struct Sentence {
    std::string words;
    int frequency;
    Sentence(std::string words, int frequency) : words(words), frequency(frequency) {}
};
struct SentencePCompare {
    bool operator() (const Sentence* lhs, const Sentence* rhs) const {
        if (lhs->frequency != rhs->frequency) {
            return lhs->frequency > rhs->frequency;
        }
        return lhs->words.compare(rhs->words) < 0;
    }
};
std::set<Sentence*, SentencePCompare> sentencesByFrequency;

int main(){
    Sentence* foo = new Sentence("foo", 1);
    Sentence* bar = new Sentence("bar", 2);
    sentencesByFrequency.insert(foo);
    sentencesByFrequency.insert(bar);
    for (Sentence* sp : sentencesByFrequency) {
        std::cout << sp->words << std::endl;
    }
    foo->frequency = 5;
    for (Sentence* sp : sentencesByFrequency) {
        std::cout << sp->words << std::endl;
    }
}

La salida del código anterior es la siguiente.

bar
foo
bar
foo

Como podríamos esperar, cuando se actualiza un objeto al que apunta el puntero en el conjunto, el conjunto no vuelve a evaluar automáticamente el predicado, aunque el predicado ordene los punteros en función de los objetos a los que apunta.

¿Hay una manera de forzar el std::set para volver a evaluar los predicados, para que la orden sea correcta de nuevo?

Answer 1

No.

Hay una razón por la cual set solo permite el acceso const a sus elementos. Si pasa por alto esto utilizando punteros poco profundos y predicados personalizados y luego destruye el invariante modificando el pointee de una manera que afecta el ordenamiento, pagará el precio en forma de demonios nasales.

Antes de C ++ 17, debe erase e insert nuevamente, lo que incurre en una copia de la clave más la desasignación y la asignación del nodo. Después, puede extract el nodo, modificarlo y reinsertarlo, que es gratuito.