How to keep items sorted based on dynamic attribute?

Question

I'm using an STL std::multiset<> as a sorted list of pointers. The sort order is determined by a property of the items being pointed to, something along the lines of this simplified example:

struct A
{
  int x;
};

bool CompareAPointers(const A* lhs, const A* rhs)
{ return lhs->x < rhs->x; }

std::multiset<A*, CompareAPointers> sorted_set;

The complication is that the values of the property used to sort the set can change (you can change A.x in the example above), which can make the sort order incorrect:

A a1, a2;
a1.x = 1;
a2.x = 2;
sorted_set.insert(&a1);
sorted_set.insert(&a2);
a1.x = 3;

I'm able to keep the list sorted by erasing and reinserting elements when the relevant attribute changes, but the book keeping is getting to be a bit of a pain. I feel like I'm going about this all wrong. Can anyone suggest a better way to keep a list sorted when the sort order can dynamically change? The changes occur in predictable ways at predictable times, but my current approach just feels wrong.

Answer 1

I would consider using a sorted std::vector instead. At one of those points where you predictably modify x for one of the set's members, then just re-sort the vector. It's a little cleaner than having to remove and reinsert items. This might be too much overhead though if you're frequently modifying a single set member's property and re-sorting. It would be much more useful if you're likely to be changing many of these properties at once.

Answer 2

Boost Multi-Index supports sorting anything you want and supports changing the fields the list gets oderdered by, although you can't just type a1.x=1 anymore, instead, you have to use MultiIndex::replace().
I can't think of a faster/more natural way of doing this, as deleting and reinserting the element would've to be done anyway.

Answer 3

As others pointed out, using a std::set or std::multiset just does not cut it.

You probably did not notice since you use pointers, but the assumption is that objects are immutable (though in this case it means that the pointers are const, but not the pointed value).

Therefore, you cannot use (directly) a standard container which will do your book-keeping automatically.

At this point you have several solutions:

• you may use a library, in this case the Boost.MultiIndex comes to mind, even though you will have to learn to use it
• or you may wrap a standard container in a dedicated class (for example, your set)

I think both are equally valid. Since the operation is very simple you may not want to use the Boost library for this yet (learning curve, integration, ...).

Also, you may consider using 'invasive' containers. What I mean is that you could use the 'Observer' pattern here >> your object can notify its container each time its value change, so that the container reposition it at its 'new' correct position (using a std::multiset internally).

If efficiency is a concern, I would not consider sorting a vector. Sorting a full container each time a single object change is a waste, your erase/insert method is much more efficient.