Увеличить multi_index order_unique Медианное значение
Я хотел бы быстро получить медианное значение из контейнера boost multi_index с индексом order_unique, однако итераторы индекса не являются произвольным доступом (я не понимаю, почему они не могут быть, хотя это согласуется с std::set...).
Есть ли более быстрый / аккуратный способ сделать это, кроме увеличения итератора container.size() / 2 раза?
2 ответа
Я столкнулся с той же проблемой в другом контексте. Кажется, что STL и Boost не предоставляют упорядоченный контейнер, который имеет произвольный доступ для использования порядка (например, для сравнения).
Моим (не очень красивым) решением было использование класса, который выполнял ввод и "фильтровал" его в наборе. После завершения операции ввода он просто скопировал все итераторы набора в вектор и использовал это для произвольного доступа.
Это решение работает только в очень ограниченном контексте: вы выполняете ввод для контейнера один раз. Если вы снова измените add на контейнер, все итераторы придется скопировать снова. Это действительно было очень неуклюже в использовании, но сработало.
Boost.MultiIndex предоставляет индексы произвольного доступа, но эти индексы не заботятся непосредственно о каком-либо порядке. Однако вы можете отсортировать эти индексы, используя функцию-член sort, после вставки нового элемента, чтобы вы могли эффективно получить медиану.
Похоже, вы должны сделать запрос к Boost.MultiIndex, чтобы вставка могла быть выполнена с использованием заказа напрямую, поскольку это должно быть намного более эффективным.