Разница между списком и мультимножеством в C ++

Question

В C ++:

• Список - это коллекция, которая может содержать неуникальные значения в последовательности

• Мультимножество - это коллекция, которая может содержать неуникальные элементы в последовательности

В чем же тогда разница между этими двумя? Зачем мне использовать над другим?

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

Answer 1

В стандартной библиотеке довольно много контейнеров , они имеют разные свойства и влияют на синхронизацию доступа, вставки и удаления элементов. Вы должны выбрать тот, который наиболее применим в конкретном случае из всей группы. Ваше определение std::multiset и std::list является искусственным и не имеет никакого смысла. Если у стула и лошади есть ноги, это не значит, что они похожи.

Answer 2

Это не так просто, но быть коротким:
Если вам нужно много раз запрашивать поиск по значению, выберите std::multiset.
В противном случае std::list.

Answer 3

Самое большое различие - std::list - это связанный список, тогда как std::multiset - это древовидная структура (обычно это дерево RB). Это означает, что доступ к элементу в std::list имеет O(N) доступ, в то время как std::multiset имеет O(logN).

Это также означает, что итерация std::multiset с begin() до end() даст вам отсортированные данные, а итерация std::list даст вам порядок вставки данных.

Answer 4

От мультисеть :

std::multiset - это ассоциативный контейнер, содержащий отсортированный набор предметов

Операции поиска, вставки и удаления имеют логарифмическую сложность.

Из список :

std::list - это контейнер, который поддерживает постоянное время вставку и удаление элементов из любой точки контейнера

Быстрый произвольный доступ не поддерживается

Таким образом, если вы хотите иметь более быстрый поиск , используйте multiset.

Для более быстрой вставки и удаления : используйте list.