21

Consider the following data structures and code.

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;
    }
}

The output of the above code is the following.

bar
foo
bar
foo

As we might expect, when an object pointed to by the pointer in the set is updated, the set does not automatically re-evaluate the predicate, even though the predicate orders the pointers based on the objects they point at.

Is there a way to force the std::set to re-evaluate the predicates, so that the order is correct again?

merlin2011
  • 71,677
  • 44
  • 195
  • 329
  • 10
    Perhaps `std::set` isn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering. – Some programmer dude Nov 20 '18 at 08:27
  • 1
    If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. a `vector`, then sort it immediately before using it, each time you use it. – Alex Celeste Nov 20 '18 at 09:57
  • @Someprogrammerdude, Do you have a recommendation for another data structure? – merlin2011 Nov 20 '18 at 18:37
  • Also, `SentencePCompare` isn't a proper order. Return type of `compare` cast to `bool` is code smell. – Yakk - Adam Nevraumont Nov 20 '18 at 19:09
  • @Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above. – merlin2011 Nov 20 '18 at 19:19

1 Answers1

34

No.

There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.

Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.

anatolyg
  • 26,506
  • 9
  • 60
  • 134
T.C.
  • 133,968
  • 17
  • 288
  • 421
  • 4
    @anatolyg You literally [`extract`](https://en.cppreference.com/w/cpp/container/set/extract) it. – T.C. Nov 20 '18 at 10:26
  • 4
    Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time. – user202729 Nov 20 '18 at 15:01
  • 1
    Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure. – T.C. Nov 20 '18 at 20:16