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

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

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

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

Если вам нужен контейнер, в котором:

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

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

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

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

Опция 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). Именно для этого и предназначен этот алгоритм, чтобы обеспечить функциональность поиска по линейному времени для любого контейнера, который не может быть лучше этого. Это то, что мы используем с несортированными массивами или векторами, со списками и т. д. Это должно быть вашим последним средством, потому что он может быть намного медленнее, чем альтернативы, хотя и сам по себе. Используйте этот подход, если вы не часто выполняете поиск, если вы знаете, что элемент находится рядом с первым итератором, если контейнер небольшой, когда нет более быстрых альтернатив и т. д.

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

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

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

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