Эффективно найти средний элемент в set'е

#cpp

std::set обычно представлен бинарным деревом поиска. У него есть методы begin и end,
которые позволяют получить минимум и максимум, а также lower_bound и upper_bound для
бинарного поиска. А что если мне надо получить итератор, указывающий на элемент в середине
сета (или один из них, если в нём чётное число элементов)?

Есть ли эффективный способ сделать это (за O(log(size)) вместо O(size))?

{1} => 1
{1,2} => 1 или 2
{1,2,3} => 2
{1,2,3,4} => 2 или 3 (но в ту же сторону от середины, что и с {1,2})
{1,312,10000,14000,152333} => 10000


PS: Этот вопрос на английском.
    

Ответы

Ответ 1

Или, если все-таки использовать set, то можно поддерживать итератор, указывающий
на медианный элемент и число элементов k до этого итератора.


Изначально set пустой, итератор равен set.end(), k равно нулю
При добавлении элемента в set:


новый элемент больше медианного => при необходимости (если k * 2 + 3 <= set.size())
сдвигааем итератор на один вперед и увеличиваем k на единицу.
новый элемент меньше медианного => при необходимости сдвигааем итератор на один назад
и уменьшаем k на единицу.

При удалении элемента из set действуем аналогично, при необходимости двигаем итератор
на единицу вперед/назад
Таким образом, в любой момент времени у нас есть итератор на медианный элемент, дополнительные
расходы для поддержания этого итератора составляют O(log n) на каждую операцию вставки/удаления


И еще вот полезный вопрос на английском Stack Overflow примерно про это же (там без
удаления, но идея такая же)


Ответ 2

Если писать свое декартово дерево не хочется, то можно использовать встроенную в
gcc структуру данных rope


Ответ 3

Думаю, что нет. Ну смотрите, для поиска минимума в BST нужно всегда идти в левую
ветку, максимума - в правую. И вот хотите Вы найти средний. И с самого начала неизвестно,
что делать. Условно, у вас в корне дерева стоит "10", больше Вы ничего не знаете о
содержимом. Куда пойдете?