У меня есть набор данных, которые мне нужно сохранить на упорядоченной карте (т. Е. С помощью эффективной вставки, удаления и поиска элементов по ключу), но мне также нужно иметь возможность найти nth *Элемент 1002 *, не проходя всю карту (иногда на ней могут быть десятки тысяч элементов).
Я знаю один способ сделать это: использовать красное / черное дерево, но сохранить общее количестводочерних элементов на одной из ног каждого узла, а также.Это делает вставку и удаление немного медленнее (потому что вы должны обновить счетчики на каждом узле вдоль пути, как вы делаете), но вы можете найти элемент nth для любого n вПримерно в то же время, что и при поиске ключа.
Мне интересно, существует ли в C ++ реализация такой вещи, которую я могу использовать.Я мог бы написать это сам, если нет, но я бы действительно не хотел.
РЕДАКТИРОВАТЬ: я получил некоторые разъяснения по варианту использования для этого.Я немного неправильно понял: после поиска элемента по ключу им нужна возможность эффективно выяснить, по какому индексу найден элемент, чтобы правильно отобразить полосы прокрутки.
Это равно aзаконная потребность, и структура данных, которую я описал выше, все еще будет работать, поэтому я все еще ищу ответ.Но так как кажется, что никто еще не придумал, я сам начну его кодировать.