Идентификатор ширины динамического массива?

Question

Мне нужен какой-то динамический массив в C ++, где каждый элемент имеет свой собственный идентификатор, представленный целым числом.

Тип данных нуждается в следующих функциях:

• int Insert () -return ID
• Удалить (int ID)
• Get (ID) - вернуть Элемент

Какой тип данных я должен использовать?Я посмотрел на Вектор и Список, но не могу найти какой-либо идентификатор.Кроме того, я посмотрел на карту и hastable, они могут быть полезными.Однако я не уверен, что выбрать.

Answer 1

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

В противном случае вы, вероятно, захотите использовать карту и просто отслеживать самый низкий неиспользуемый идентификатор иназначьте его при вставке.

Answer 2

A vector дает произвольный доступ в постоянном времени, "id" может быть просто смещением (индексом) вектора. A deque похож, но не хранит все элементы подряд.

Любой из этих вариантов будет подходящим, если значения идентификатора могут начинаться с 0 (или известного смещения от 0 и увеличиваться монотонно). Со временем, если имеется большое количество удалений, vector или deque могут стать малонаселенными, что может быть вредным.

std::map не имеет проблемы с малонаселенностью, но поиск перемещается из постоянного времени в логарифмическое, что может повлиять на производительность.

boost::unordered_map может быть еще лучшим, так как лучший вариант сценария в виде хеш-таблицы, вероятно, будет иметь наилучшие общие характеристики производительности, учитывая вопрос. Тем не менее, использование библиотеки boost может быть необходимым - но в std::tr1 также есть unordered типы контейнеров, если они доступны в вашей реализации STL.

Answer 3

A std::map может работать для вас, что позволяет связать ключ со значением. ключ будет вашим идентификатором, но вы должны указать его самостоятельно при добавлении элемента на карту.

Хеш-таблица является своего рода базовым механизмом, который можно использовать для реализации неупорядоченногокарта.Это соответствует std :: unordered_map.

Answer 4

Кажется, что лучшим контейнером для использования является unordered_map.Он основан на хэше.Вы можете вставлять, удалять или искать элементы в O (n).

В настоящее время unordered_map нет в STL.Если вы хотите использовать контейнер STL, используйте std :: map.Он основан на дереве.Вставляет, удаляет и ищет элементы в O (n * log (n)).

Тем не менее выбор контейнера во многом зависит от интенсивности использования.Например, если вы найдете редкие элементы, вектор и список могут быть в порядке.Эти контейнеры не имеют метода find, но библиотека <algorithm> включает его.