найти индекс элемента внутри коллекции, какую коллекцию использовать?

Question

У меня проблема с выбором правильной структуры данных, это требования:

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

Порядок не является обязательным, важно получить индекс элемента, независимо от того, как он реализован внутри, но в любом случае я думаю, что лучший подход - это порядок.Индекс элемента - это порядок внутри коллекции.Так что какой-то порядок должен быть использован.Когда я удаляю элемент, другие элементы от этого до конца меняют свой порядок / индекс.

Первый подход - использование связанного списка, но я не хочу O (n).Я также думал об использовании и упорядоченном словаре, который дал бы O (log n) для поиска / вставки / удаления, не так ли?Есть ли лучший подход?Я знаю, что TRIE выдаст O (1) для обычных операций, но я не вижу, как получить индекс элемента, мне пришлось бы перебирать дерево и давать O (n), я не прав?

Answer 1

Звучит так, как будто вы хотите упорядоченную структуру данных, то есть (сбалансированный) BST. Вставка и удаление действительно были бы O (lg n ), что достаточно для многих приложений. Если вы также хотите, чтобы элементы имели индекс в структуре , то вам нужно дерево статистики заказов (см., Например, CLR, Введение в алгоритмы , глава 14), которая обеспечивает эту операцию в O (LG N ). Динамическая повторная сортировка всей коллекции будет O ( n lg n ).

Если под «порядком в коллекции» вы подразумеваете, что любой случайный порядок достаточно хорош, тогда просто используйте динамический массив (вектор): амортизированные O (1), добавление и удаление, O ( n lg *) 1019 * n ) сортировка на месте, но поиск O ( n ), пока вы не выполните сортировку, после чего поиск становится O (lg n ) с двоичным поиском. Однако удаление будет O ( n ), если данные останутся отсортированными.

Если ваши данные похожи на строки, вы можете расширить дерево таким же образом, как BST, чтобы стать деревом статистики заказов.

Answer 2

Вы не упоминаете массив / вектор, но он соответствует большинству этих критериев.

(Обратите внимание, что «Элементы имеют уникальный идентификационный номер» действительно независимо от структуры данных; это означает то же самое, что и индекс? Или это неизменный ключ, который больше зависит от данных, которые выперекладываем в структуру ...)

В любом сценарии будут временные компромиссы: вы говорите, что связанный список - это O (n), а для чего O (n)?Вы действительно не вписываетесь в свои требования к производительности для добавления, удаления или поиска;что важнее?

Answer 3

Хорошо, если ваша коллекция отсортирована, вам не нужно O (n), чтобы найти элементы.Например, можно использовать бинарный поиск для определения индекса элемента.Также можно написать простую оболочку для Entry внутри вашего массива, которая запомнит его индекс в коллекции.