Упорядоченная карта C++, оптимизированная с помощью индексного доступа ⇐ C++

[Anonymous]

Коротко говоря, мой вопрос: как максимизировать производительность упорядоченной карты (например, реализованной как std::map) с хорошей поддержкой индексного доступа?Подробности:
Конечно, мы можем использовать некоторый код, например std::advance(it, index), чтобы обеспечить доступ к индексу там, где это необходимо является итератором std::map. Однако производительность становится серьезной проблемой, когда std::map имеет большой размер, поэтому обход std::map происходит очень медленно.
Я надеюсь, что контейнер map может поддерживать следующее:

[*]Основные операции. Просто ведите себя как обычный std::map . Например, вставка, удаление, доступ к значениям по ключам. Ожидается сложность ниже O(N).
[*]Упорядоченность. Мы можем получить доступ к

Код: Выделить всё

i

-й наименьший (по ключам) элемент[/b] по индексному доступу. Индексы не являются полностью случайными, они немного похожи (поэтому моя первая мысль — использовать что-то вроде кеша, но я понятия не имею). Мы можем изменить карту, вставив или удалив, поэтому сохранение ранее использованных итераторов может оказаться невозможным, поскольку они могут указывать на неправильные позиции после изменения карты.

Какова правильная структура данных или реализация для достижения этой цели? Спасибо!
Цель:
Хорошая реализация упорядоченной карты с хорошей поддержкой доступа к индексу< /strong> (возможно, с кешированием)? Это нормально, если все элементы не хранятся полностью в отсортированном порядке.

Подробнее здесь: https://stackoverflow.com/questions/782 ... dex-access