лучшая структура данных для поиска byIndex и byName

Question

предположим, что вам нужно реализовать контейнер из T элементов, значение которого можно получить по числовому индексу (произвольный доступ) и по имени (в виде строки)

который лучше с точки зрения выполнения обычных операций , таких как поиск, добавление и удаление элементов:

(в этом случае поиск по индексу должен осуществляться путем перемещения по карте)

std::map<std::string,T> container;

или (быстрый произвольный доступ по индексу, но требуется поиск по имени)

std::vector<std::pair<std::string,T>> container;

или предоставив два отдельных контейнера (быстрый поиск, но медленная операция добавления / удаления)

std::vector<T> byIndexContainer;
std::map<std::string,T> byNameContainer;

или вы можете предложить другую структуру данных, которая лучше?

Answer 1

Или вы можете использовать самые классные Boost :: MultiIndex контейнеры.

Answer 2

Доступ к карте - только логарифмическое время - все хранится как внутренне отсортированное. Поэтому, если у вас есть 10000 элементов, вы можете ожидать, что он примет дюжину вызовов std :: string :: operator <. Если вам нужен лучший произвольный доступ через строковый ключ, используйте hash_map (не совсем стандартный). </p>

Если вам не нужен произвольный доступ для скорости, а потому, что вам действительно нужен индекс по какой-то причине, одним из решений, не требующих больших усилий, является сохранение отсортированного вектора, который делает недействительными индексы при вставке или что-то еще. Вы не можете иметь статический индекс (такой же после удаления) в целом, потому что, когда вы удаляете что-то, вам нужно либо изменить индексы, сдвигая вещи, либо назвать этот индекс «недействительным», и в этом случае ваши «индексы» действительно ключи, потому что n-й индекс не n-й предмет, и вы не можете использовать все индексы. В этом случае просто используйте строки напрямую.

Если вам ДЕЙСТВИТЕЛЬНО нужны целочисленные ключи, а также строковые ключи, вам, вероятно, нужно использовать метод с двумя контейнерами. Некоторое время назад я написал что-то, что содержит список уникальных ключей (вы можете специализировать его для целых чисел), если хотите. Это где-то на работе, хотя, если вы не прокомментируете, я не буду искать это.

Answer 3

Ваш пример с двумя отдельными контейнерами будет быстрым для индексации и, как вы говорите, немного медленнее для добавления / удаления. Он сочетает в себе лучшее для целочисленной индексации и индексации строк. Вы всегда можете создать свой собственный тип, который имеет эти два.