Эффективный способ перемещения элемента внутри std :: deque?

Question

Я пытаюсь сохранить отсортированный список.

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

Интересно, что является наиболее эффективным способом.Самый простой способ - выполнить 1 двоичный поиск + 1 вставку + 1 стирание, что может включать выделение и освобождение памяти.

Другой способ - просто вызывать std::sort каждый раз (после изменения ключа), так какбудет делать std::swap под.Но это немного тяжелый O (n log n) (против O (1) с 1 двоичным поиском + 1 вставка + 1 стирание = O (log n)).

Любые предложения приветствуются.

Спасибо!

Answer 1

Первый вопрос Я хотел бы спросить себя, зачем использовать контейнер std::deque.Это не лучшая локальность данных и не самые быстрые вставки.Особенно, когда есть контейнер, специально разработанный для поддержания порядка сортировки при минимальных затратах - std::map.

Если вам нужны как локальность данных, так и поддерживаемый порядок сортировки, посмотрите на boost::intrusive::map и boost::flat_map.Они хранят данные локально и просто обновляют связь при перебалансировке дерева.Единственное отличие состоит в том, что flat_map инкапсулирует реализацию дерева и плоскую базовую память, тогда как intrusive::map оставляет аспект хранения полностью за вами.У меня есть пример очереди сопоставления здесь , которая использует кольцевой буфер в качестве хранилища и навязчивую карту в качестве индексатора сортировки поверх него.

В конечном счете, вам нужно сравнить и сравнитьрешения на основе ваших конкретных данных и моделей использования.