Std:: map с эффективным доступом n-го элемента
У меня есть набор данных, которые мне нужно хранить в упорядоченной карте (т.е. с эффективной вставкой, удалением и локализацией элементов по ключу), но мне также нужно найти n-й элемент, не пройдя через всей карты (иногда могут быть десятки тысяч предметов).
Я знаю один способ сделать это: используйте красное/черное дерево, но сохраняйте общее количество дочерних элементов на одной из ног каждого node. Это делает вставку и удаление немного медленнее (потому что вам нужно обновлять счетчики на каждом node вдоль пути, как вы это делаете), но вы можете найти n-й элемент для любого n примерно в то же время, что и поиск ключа.
Мне интересно, существует ли существующая реализация на С++ такой вещи, которую я могу использовать. Я могу написать это сам, если нет, но я бы действительно не хотел.
РЕДАКТИРОВАТЬ: У меня есть некоторые пояснения к делу. Я неправильно понял это: после поиска элемента по ключу, им нужна способность эффективно выяснить, какой индекс найден найденным элементом, правильно отобразить полосы прокрутки.
Это законная необходимость, и структура данных, описанная выше, по-прежнему будет работать для нее, поэтому я все еще ищу ответ. Но, как кажется, никто еще не придумал, я сам начну его кодировать.
Ответы
Ответ 1
Это мой ответ на другой вопрос, рассматривающий аналогичную проблему.
ассоциативный/произвольный контейнер доступа
Я думаю, это также может быть применимо к вашему вопросу.
Я искал такую структуру данных в течение длительного времени.
Недавно я нашел довольно многообещающую библиотеку, которая обладает всеми функциональными возможностями, которые вы ищете.
См. cntree:: set со случайным доступом в O (log n).
вот ссылка. http://dl.dropbox.com/u/8437476/works/countertree/index.html
Хотя он, похоже, находится в разработке, я вижу, что он вполне применим.
Ответ 2
Если вы использовали модифицированную Trie, где нетерминальные узлы отслеживали, сколько терминальных узлов было ниже, вы можете выполнить быстрый упорядоченный поиск.
Ответ 3
Я никогда не использовал boost::multi_index_container<>, но похоже, что у него может быть возможность делать то, что вы хотите (хотя я не совсем уверен - это довольно сложная библиотека на первый взгляд).
Он имеет тип ключа произвольного доступа, но я не уверен, как вы обновляете случайный индекс таким образом, чтобы синхронизировать вставленный индекс элемента с другим порядком индекса.
Также обратите внимание на следующее из учебника по использованию случайного индекса:
Эта дополнительная гибкость предоставляется по цене: вставки и удаления в позициях, отличных от конца индекса, имеют линейную сложность, тогда как эти операции являются постоянным временем для индексированных индексов. Эта ситуация напоминает различия в поведении сложности между std:: list и std::vector: в случае индексов произвольного доступа, однако, вставки и удаления никогда не подвергаются копированию любого элемента, поэтому фактическая производительность этих операций может быть приемлемой, несмотря на теоретический недостаток в отношении секвенсированных индексов.
Мне непонятно, будет ли это убийцей для вас или нет, даже если вам удастся синхронизировать случайный индекс для вставленных элементов так, как вам хотелось бы.
Ответ 4
Один из вариантов заключается в разработке контейнера, который основан на std::vector, но также имеет интерфейс карты. Он будет хранить отдельную хэш-таблицу или двоичное дерево, которое использует ключи элементов для доступа к ним, но фактические значения будут указателями на внутренний массив, используемый вектором.
Такое чудовище может показаться бессмысленным, подверженным ошибкам или запахом дизайна некоторыми людьми, но такая структура данных действительно имеет свое место. Я видел, что это использовалось в коде для аппаратных драйверов в розничных системах, где двум пользователям контейнера необходимо обращаться к ним разными способами. Когда используется "потому что оно есть", это плохо, но при правильном использовании это спасатель.
Ответ 5
Поздно к вечеринке (поразите этот вопрос, ища что-то связанное) - но не отсортированный вектор не подходит для использования здесь?
Время вставки хуже - если вы не сделаете большинство/все ваши вставки в одной партии перед сортировкой.
После этого время поиска может фактически бить std:: map - и получение индекса тривиально.
Ответ 6
Попробуйте использовать упорядоченный std:: list и используйте std:: binary_search для поиска. Упорядоченный список может быть реализован с использованием std:: list и вставки узлов с использованием std:: lower_bound. Существует много примеров этого в Интернете и на SO.
Ответ 7
Карта MS VC STL, поддерживаемая красным черным деревом.
Я не думаю, что можно иметь эффективный поиск (по ключу) и эффективный случайный доступ в той же структуре данных.
Если эффективный случайный доступ действительно важен, было бы лучше хранить данные в векторном контейнере с произвольным доступом. Заказ и поиск ключей могут быть выполнены с помощью дополнительных индексов. РСУБД делают это следующим образом.
Или, если вставка/удаление важнее, представляется невозможным управлять чем-то вроде массива ключей (или индекса номера строки) для произвольного доступа.
