STL sorted set where the conditions of order may change

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

1) Harmful - no. Result in crashes - no. The worst is indeed a non-sorted set.

2) "Refreshing" would be the same as re-adding anyway!

Answer 2

This can cause lost entries, when searching for an element in a set the ordering operator is used this means that if an element was placed to the left of the root and now the ordering operator says it's to the right then that element will not longer be found.

Answer 3

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.

Answer 4

This is actually implementation dependent.
The STL implementation can and usually will assumes the predicate used for sorting is stable (otherwise, "sorted" would not be defined). It is at least possible to construct a valid STL implementation that formats your hard drive when you change the behavior of the predicate instance.

So, yes, you need to re-insert the items into a new set.

Alternatively, you could construct your own container, e.g. a vector + sort + lower_bound for binary search. Then you could re-sort when the predicates behavior changes.

Answer 5

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 6

If you can live with an unordered set, then why are you adding them into a set in the first place?

The only case I can think of is where you just want to make sure the list is unique when you add them. If that's the case then you could use a temporary set to protect additions:

if (ts.insert (value).second) {
    // insertion took place
    realContainer.push_back (value);
}

An alternative, is that depending on how frequently you'll be modifying the entries in the set, you can probably test to see if the entry will be in a different location (by using the set compare functionality) and where the position will move then remove the old entry and re-add the new one.

As everyone else has pointed out - having the set unordered really smells bad - and I would also guess that its possible got undefined behaviour according to the std.

Answer 7

While this doesn't give you exactly what you want, boost::multi_index gives you similar functionality. Due to the way templates work, you will never be able to "change" the ordering predicate for a container, it is set in stone at compile time, unless you are using a sorted vector or something similar, to where you are the one maintaining the invariant, and you can sort it however you want at any given time.

Multi_index however gives you a way to order a set of elements based on multiple ordering predicates at the same time. You can then select views of the container that behave like an std::set ordered by the predicate that you care about at the time.

Answer 8

Here's a simple test for you:

struct comparer : public std::binary_function<int, int, bool>
{
  static enum CompareType {CT_LESS, CT_GREATER} CompareMode;
  bool operator()(int lhs, int rhs) const
  {
    if(CompareMode == CT_LESS)
    {
      return lhs < rhs;
    }
    else
    {
      return lhs > rhs;
    }
  }
};

comparer::CompareType comparer::CompareMode = comparer::CT_LESS;

typedef std::set<int, comparer> is_compare_t;

void check(const is_compare_t &is, int v)
{
  is_compare_t::const_iterator it = is.find(v);
  if(it != is.end())
  {
    std::cout << "HAS " << v << std::endl;
  }
  else
  {
    std::cout << "ERROR NO " << v << std::endl;
  }
}

int main()
{
  is_compare_t is;
  is.insert(20);
  is.insert(5);
  check(is, 5);
  comparer::CompareMode = comparer::CT_GREATER;
  check(is, 5);
  is.insert(27);
  check(is, 27);
  comparer::CompareMode = comparer::CT_LESS;
  check(is, 5);
  check(is, 27);
  return 0;
}

So, basically if you intend to be able to find the elements you once inserted you should not change the predicate used for insertions and find.

Answer 9

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 10

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 11

I was looking for the same set-method like John. Something, that simply do the reinsert 'inside'. You're code is prettier and the method doesn't need to resort whole content, it just update position of changed element. I think method like this should be useful