How to save items sorted by dynamic attribute?

Question

I use STL std :: multiset <> as a sorted list of pointers. The sort order is determined by the property of the items pointed to by something like 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 property values ​​used to sort the set can change (you can change Ax in the above example), 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 can save the list sorted by erasing and reinserting the elements when the corresponding attribute changes, but saving the book becomes a little painful. I feel that all this is wrong. Can anyone suggest a better way to keep the list sorted when the sort order can change dynamically? Changes occur in predictable ways at a predictable time, but my current approach just feels wrong.

Answer 1

The Boost Multi-Index supports sorting everything you want and supports changing the fields that the list falls into, although you cannot just enter a1.x=1 , you should use MultiIndex :: replace () instead.
I can't think of a faster / more natural way to do this, since deleting and re-nesting the element had to be done anyway.

Answer 2

I would rather use a sorted std::vector . At one of those points where you predictably change x for one of the given elements, just redraw the vector. This is a little cleaner than having to remove and reinsert items. This can be too much overhead, though if you often change one property of a set of items and re-sort. It would be much more useful if you are likely to immediately change many of these properties.

Answer 3

As others have pointed out, using std :: set or std :: multiset just doesn't shorten it.

You probably didn’t notice, because you use pointers, but the assumption is that the objects are immutable (although in this case it means that the pointers are const, but not pointed).

Therefore, you cannot use (directly) a standard container that will automatically perform your accounting.

At this point you have several solutions:

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

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

Alternatively, you can use 'invasive' containers. I mean, you can use the "Observer" template here → your object can notify its container every time its value changes, so that the container moves it to its "new" correct position (using the internal std :: multiset).

If efficiency is a problem, I would not consider sorting a vector. Sorting a full container every time one change of an object is waste, the erase / insert method is much more efficient.