Можно или почему я не могу искать элемент по индексу в std :: set?

Question

На этом сайте есть пара вопросов о доступе к элементам в std::set по индексу, но ответы, которые я видел, были старыми и неосвещающими.

Упорядоченные множества могут быть (и часто) реализованы как двоичныеискать деревья.В бинарном дереве поиска, сохраняя количество узлов в дереве, укорененном в каждом узле, мы можем получить доступ к k -ому элементу в отсортированном порядке за O(log n) время, не увеличивая алгоритмическую сложность других операций (пожалуйста, исправьте меня, еслиэто ошибка в моем мышлении).

Тем не менее, если я хочу k-й элемент в отсортированном порядке от set::set, я должен пройти от begin() до k, используя O(k) время вместо.В общем, это может равняться O(n) времени.

Итак, мои вопросы:

• Правильно ли, что мы можем поддерживать сбалансированное по высоте дерево двоичного поиска, в котором ономожно найти k-й элемент за O(log n) время, не нарушая сложность времени других операций?
• Если так, есть ли функция или альтернативная структура данных в стандартной библиотеке C ++, которую я мог бы использовать дляэтот эффект?
• Если да для первого, но нет для второго, было ли это или рассматривается?Разве это не реализовано из-за какого-то технического барьера или просто потому, что стоимость реализации считается слишком дорогой для потенциальной полезности этой функции?

Answer 1

Это позволяет дополнить (сбалансированное) дерево поиска дополнительной информацией, которую можно использовать для осуществления поиска по индексу в логарифмическом времени.Такое расширенное дерево поиска можно назвать деревом статистики заказов .

. Увеличение дерева не влияет на асимптотическую сложность в худшем случае основных операций (вставка, поиск, стирание): их худшееслучай все еще логарифмический.Я не знаю, предотвращает ли она амортизированную постоянную сложность, которая требуется для операций стирания и подсказки вставки упорядоченных ассоциативных контейнеров.

Однако асимптотическая сложность не является единственным критерием для функции.Дополнение дерева увеличивает коэффициент сложности логарифмических операций, делая все (или большинство) других операций более медленными.Это также увеличивает пространственные издержки структуры данных.Таким образом, то, что такая структура данных возможна, не обязательно означает, что было бы неплохо использовать ее для реализации универсальных ассоциативных контейнеров, предоставляемых стандартной библиотекой.

Нет.В стандартной библиотеке нет контейнера, основанного на дереве поиска с поиском по логарифмическому индексу.

Я нашел предложение n3700 , основанное на библиотеке компонентов Boost tree, в которой предлагается добавить общие структуры дерева.Он включает класс rank_tree, который выглядит как расширенное дерево поиска, которое предоставляет искомую операцию.