std :: list со свойствами std :: map?

Question

По сути, я хочу иметь std :: list, но со свойствами std :: map, такими как find (), действительно ли мне нужно перебирать каждую запись в списке, чтобы найти то, что мне нужно?

Answer 1

Если вам нужны свойства std :: map, почему бы не использовать std :: map? Это будет более эффективно, чем циклически проходить через каждый элемент.

Answer 2

Оформить заказ Boost.MultiIndex , это проще и эффективнее, чем использование нескольких контейнеров с указателями.

Answer 3

Если вы хотите контейнер, где:

1) Порядок вставки не важен (это список)
2) Скорость поиска равна.

Затем используйте

станд :: набор <>

Answer 4

Если вы беспокоитесь о времени поиска, но хотите сохранить порядок, вы можете оставить два контейнера с одинаковыми данными.

Answer 5

Используйте std :: find или std :: find_if , чтобы найти первую позицию некоторого значения в некотором диапазоне итераторов.

Answer 6

Цель std :: list - не найти / не найти. Вот для чего используется std :: map. Список отлично подходит для вставки, извлечения, перемещения и использования алгоритмов сортировки. Если вам просто нужно хранить данные и случайно находить их, используйте карту. Если вы хотите структурировать, как и где хранятся ваши данные, используйте список.

Answer 7

Вариант 1

Звучит так, будто вам нужна карта отдельных элементов, а не карта пар. Используйте std::set<T>, который является адаптером, реализованным как std::map<T,void>. Это означает, что все ваши элементы будут уникальными; то есть в вашем контейнере не будет дубликатов. Это также подразумевает, что ваши элементы не будут строго упорядочены; то есть вы не можете полагаться на положение какого-либо элемента в любой момент времени. Затем вы можете использовать find() функцию-член std::set<T>, которая будет выполнять быстрый поиск элемента в логарифмическом времени.

Вариант 2

Если вам нужен контейнер, обеспечивающий быстрый доступ к наименьшему или наибольшему элементу, тогда вы можете использовать std::priority_queue<T,C> с контейнером C на ваш выбор. Если не указан, используемый контейнер по умолчанию - std::vector<T>. std::priority_queue<T> использует алгоритмы make_heap(), push_heap() и pop_heap() и, следовательно, требует, чтобы базовый контейнер поддерживал итераторы с произвольным доступом; std::list<T> будет недостаточно в этом случае. Доступ к «первому» (наибольшему или наименьшему) элементу за постоянное время с помощью функции-члена top(). Нажмите и вытолкните первый элемент с помощью функций-членов push() и pop(), которые работают в логарифмическом времени (на самом деле 2 * log (n), потому что они должны искать, а также всплывать).

Вариант 3

Если вам нужен просто список, содержащий пары, просто объявите его так:

std::list<std::pair<T> > the_list;

Это не даст ничего, кроме связанного списка с ограничениями и преимуществами любого другого связанного списка, но будет содержать пары, как карта. Таким образом, вы будете использовать стандартные алгоритмы для управления списком. Возможно, вам потребуется передать специализированные функции или функторы в алгоритмы с этим списком, чтобы разыменовать ключ или значение из пары.

Если все, что вам нужно, это искать элемент в списке, не заботясь об эффективности, вы можете сделать это с помощью алгоритма std::find() за O (n) время. Это именно то, для чего предназначен этот алгоритм, чтобы обеспечить функциональность линейного поиска по времени для любого контейнера, который не может быть лучше, чем этот. Это то, что мы используем с несортированными массивами или векторами, со списками и т. Д. Это должно быть вашим последним средством, потому что это может быть намного медленнее, чем альтернативы, хотя и замедлять само по себе. Используйте этот подход, если вы не часто выполняете поиск, если знаете, что элемент находится рядом с первым итератором, если контейнер мал, когда нет более быстрых альтернатив и т. Д.

Answer 8

Мне нужно было то же самое, поэтому я написал нечто, представляющее собой комбинацию списка и карты. Я называю это map_list <> и hash_map_list <>. По сути, я взял исходный код в xmap.h и xlist.h и скомбинировал их в xmap_list.h. Этот класс работает, сохраняя ключ в данной карте, но в сочетании с указателем на узел, который содержит значение. Этот узел содержит итератор, который указывает обратно на карту. Узлы хранятся в отдельном связанном списке. Таким образом, вы можете использовать функцию поиска, как обычно с классом карты, но вы также можете перебирать элементы в том порядке, в котором вы их вставили, как класс списка. Вы даже можете перебирать сами ключи как в списке. Я не реализовывал каждую последнюю эквивалентную функцию списка, но большинство из тех, что вы используете чаще всего, есть (например, я не обрабатываю пользовательские распределители, хотя вы могли бы легко добавить это самостоятельно). Это выглядит как list <> с функцией find ().

Для проекта, для которого я написал это, я в конечном итоге перешел на boost :: multi_index, но я все еще использую класс map_list <>, когда могу, потому что он намного легче и ближе к std :: интерфейс list <>.

У меня нигде нет загруженного кода, но если я увижу, что кто-то добавил комментарий к этому ответу, я постараюсь опубликовать его где-нибудь и указать местоположение здесь.

Answer 9

@ obecalp имеет хороший ответ. Повышение MultiIndex является хорошим предложением. @Bklyn: Это не"чрезвычайно глупый" вопрос.