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

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 2

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.