Ensure multiset is reordered when objects change

Question

I have a multiset with a custom predicate function, e.g multiset<MyClass *,MyCompFunc> where MyCompFunc looks at an attribute on the MyClass objects. During the progress of the application, the objects might change in a way that should cause them to be reordered.

What's the correct way to get the multiset to become reordered when this happens? Manually sort it, or remove the modified object, update it, and re-insert it?

Answer 1

The usual is to remove, update, and re-insert. Virtually anything else at least temporarily violates the primary invariant of a set/multiset, which clearly isn't a good thing.

Answer 2

I still can't find anything which says this explicitly, but if you modify a key[*], then for example your comparator doesn't satisfy the requirements of 25.3 (strict weak order):

comp induces a well-defined relation on the equivalence classes determined by equiv

comp isn't a well-defined relation if it returns different values for the same inputs at different times.

In your case I believe that it's fine to modify fields of MyClass which aren't involved in the comparison.

Interestingly, 23.1.2/2 says, "Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.3) on elements of Key". I think we can take this to mean that the comparator induces a strict weak ordering on Key objects which are elements of the container, not necessarily on all objects of type Key. For instance if the Key is a pointer then I'm pretty sure it's fine to write a comparator that dereferences it, provided you don't use a null pointer as a key. By the same reasoning, I hope we can modify a key which isn't in the container.

[*] by "modify", I mean do anything which changes the results of the comparator with that key and some other key. In this case of course you aren't really modifying the key itself (which is just a pointer value), but that's what I'm calling it.

Answer 3

Don't access the objects by reference. Copy them, and re-insert them if their key changed. You might use an observer to automate this.

Answer 4

If you will be changing part of the comparison key of the object, first remove the item from the set, then perform the modification, then add it back into the set. This way you avoid breaking the invariant of the set, as sets just aren't designed to reorder on a key change.