views:

38

answers:

2

I would like to quickly retrieve the median value from a boost multi_index container with an ordered_unique index, however the index iterators aren't random access (I don't understand why they can't be, though this is consistent with std::set...).

Is there a faster/neater way to do this other than incrementing an iterator container.size() / 2 times?

A: 

I ran into the same problem in a different context. It seems that the STL and Boost don't provide an ordered container that has random access to make use of the ordering (e.g. for comparing).

My (not so pretty) solution was to use a Class that performed the input and "filtered" it in a set. After the input operation was finished it just copied all iterators of the set to a vector and used this for random access.

This solution only works in a very limited context: You perform input on the container once. If you change add to the container again all iterators would have to be copied again. It really was very clumsy to use but worked.

pmr
+1  A: 

Boost.MultiIndex provide random access indexes, but these index don't take care directly of any order. You can however sort these index, using the sort member function, after inserting a new element, so you will be able to get the median efficiently.

It seems you should make a request to Boost.MultiIndex so the insertion can be done using an order directly, as this should be much more efficient.

Vicente Botet Escriba