Ищем индексированный контейнер с поиском и вставкой / удалением в O (log n) в C ++

Question

Я ищу индексированный контейнер в C ++, который имеет следующие свойства:

• получить элемент в k-й позиции в O (log n)
• вставить элемент в k-й позиции в O (log n)
• удалить элемент в k-й позиции в O (log n)

Я думал об обходном пути, используя карта, которая работает аналогично, но я не могу понять это. В Java также есть контейнер с именем TreeList , который имеет указанные свойства.

Answer 1

Вам нужно дерево статистики заказов . Это двоичное дерево поиска, которое отслеживает размер каждого поддерева, и эту информацию можно использовать для выполнения необходимых операций за логарифмическое время c. Стандартная библиотека C ++ не реализует такую ​​структуру данных, поэтому вам нужно реализовать свою собственную или использовать другую библиотеку. Расширение структур данных *1003* на основе политик GNU включает это.