STL sorted set where the conditions of order may c

Question

I have a C++ STL set with a custom ordering defined.

The idea was that when items get added to the set, they're naturally ordered as I want them.

However, what I've just realised is that the ordering predicate can change as time goes by.

Presumably, the items in the set will then no longer be in order.

So two questions really:

1. Is it harmful that the items would then be out of order? Am I right in saying that the worst that can happen is that new entries may get put into the wrong place (which actually I can live with). Or, could this cause crashes, lost entries etc?

2. Is there a way to "refresh" the ordering of the set? You can't seem to use std::sort() on a set. The best I can come up with is dumping out the contents to a temp container and re-add them.

Any ideas?

Thanks,

John

Answer 1

The only safe way to do this with the STL is to create a new set with the changed predicate. For example you could do something like this when you needed to sort the set with a new predicate:

std::set<int> newset( oldset.begin(), oldset.end(), NewPred() );

Answer 2

Just a follow up:

While running this code the Visual Studio C debug libraries started throwing exceptions complaining that the "<" operator was invalid.

So, it does seem that changing the sort ordering is a bad thing. Thanks everyone!

Answer 3

I agree with the other answers, that this is going to break in some strange and hard to debug ways. If you go the refresh route, you only need to do the copy once. Create a tmp set with the new sorting strategy, add each element from the original set to the tmp set, then do

 orig.swap(tmp);

This will swap the internals of the sets.

If this were me, I would wrap this up in a new class that handles all of the details, so that you can change implementations as needed. Depending on your access patterns and the number of times the sort order changes, the previously mentioned vector, sort, lowerbound solution may be preferable.

Answer 4

set uses the ordering to lookup items. If you would insert N items according to ordering1 and insert an item according to ordering2, the set cannot find out if the item is already in.

It will violate the class invariant that every item is in there only once.

So it does harm.