Увеличить multi_index order_unique Медианное значение

Question

Я хотел бы быстро получить медианное значение из контейнера boost multi_index с индексом order_unique, однако итераторы индекса не являются произвольным доступом (я не понимаю, почему это невозможно, хотя это согласуется с std :: установлен ...).

Есть ли более быстрый / аккуратный способ сделать это, кроме увеличения итератора container.size () / 2 раза?

Answer 1

Boost.MultiIndex предоставляют индексы произвольного доступа , но эти индексы не заботятся напрямую ни о каком порядке. Однако вы можете отсортировать эти индексы, используя функцию-член sort, после вставки нового элемента, чтобы вы могли эффективно получить медиану.

Похоже, вы должны сделать запрос Boost.MultiIndex, чтобы вставка могла быть выполнена с использованием заказа напрямую, поскольку это должно быть намного более эффективным.

Answer 2

Я столкнулся с той же проблемой в другом контексте.Кажется, что STL и Boost не предоставляют упорядоченный контейнер, который имеет произвольный доступ для использования порядка (например, для сравнения).

Мое (не очень красивое) решение состояло в том, чтобы использовать класс, который выполнялвход и «отфильтровывают» его в комплекте.После завершения операции ввода он просто скопировал все итераторы набора в вектор и использовал его для произвольного доступа.

Это решение работает только в очень ограниченном контексте: ввод для контейнера выполняется один раз.Если вы снова измените add на контейнер, все итераторы придется скопировать снова.Это действительно было очень неуклюже в использовании, но сработало.