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

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 2

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 3

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 4

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 5

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 6

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!