С статистикой порядка с использованием С++ STL

Учитывая пустой массив, мне нужно сделать два типа запросов

Вставка элемента в массив
Поиск индекса какого-либо элемента k (очевидно, массив нужно сортировать)

Это можно сделать, используя set container

set<int> st;
set.insert(t);

Это добавит мой элемент в O(log(n)).

И для второго запроса

set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);

Это занимает время O(n). (O(n) [для distance() [+ O(log(n) [для set::find()]).

Есть ли способ сделать оба запроса в O(log(n)) с помощью предопределенных контейнеров С++?

http://www.cplusplus.com/reference/stl/

Ответ 1

Нет. Это невозможно (с предопределенными контейнерами). Контейнеры последовательности стандартной библиотеки С++ имеют:

O (1) произвольный доступ и O (N) вставка/удаление или
O (N) случайный доступ и O (1) вставка/удаление

Обратите внимание, что deque является исключением, но только тогда, когда вставка/удаление происходит на концах массива. Общий случай все еще равен O (N).

Кроме того, классификация итераторов не включает категорию для этого случая. У вас есть двунаправленные итераторы (те list, set, multiset, map и multimap), которые берут O (N) раз, чтобы перейти в случайную позицию, а следующая категория - случайная итераторы доступа (те vector, deque и string). Нет промежуточной категории.

Добавление новой категории вообще не будет тривиальным. В библиотеке также реализовано множество алгоритмов (например, for_each), которые работают с контейнерами. Существует реализация для каждой категории итераторов.

Деревья статистики заказов были предложены в Boost несколько раз. Насколько я знаю:

2004: Первое предложение (я не знаю, было ли это реализовано)
2006: "Структуры иерархических данных"
2006: AVL Array (переименован в "Ранковый список" в Boost)
2012: Дерево счетчиков

Основная трудность для их принятия заключалась в обобщенном мнении о том, что они не являются преимуществом, а представляют опасность. Сегодня программисты используются для решения всех проблем, которые они знают, с типичными контейнерами. Опытные программисты опасаются, что новички могут вслепую использовать предлагаемый контейнер для всего, вместо того, чтобы тщательно выбирать.

Ответ 2

Я не думаю, что это возможно с контейнерами стандартной библиотеки, поскольку поддержка доступа по индексу потребует изменения реализации (добавьте счетчик к каждому node). Это увеличит размер каждого node. И философия С++ - это "не платите за то, что вы не используете".

Если вам это действительно нужно, там предлагается countertree реализация для boost (и она поддерживает хотя бы некоторые из С++ 11 функции), которые соответствуют вашим требованиям.

Ответ 3

Хотя я согласен с тем, что в С++ нет полностью встроенного способа сделать это, есть один хороший способ: использовать дерево сегментов. Пусть дерево сегментов обозначает частоту каждого встреченного элемента. Вставка элемента в основном обновляет счет на 1, в то время как запрос - это операция суммы сегмента от индексов 0 до element - 1. Оба они легко могут быть выполнены в O(logn). Я знаю, что недостатком является то, что вам нужно знать количество элементов, которые могут присутствовать, но во многих практических задачах достаточно хорошей верхней границы.