установить реализацию карты в C ++

Question

Я считаю, что и набор, и карта реализованы в виде дерева. set - это бинарное дерево поиска, map - это самобалансирующееся бинарное дерево поиска, например красно-чёрное дерево Я смущен разницей в реализации. Разница, которую я могу изобразить, такова:

1) элемент в наборе имеет только одно значение (ключ), элемент в карте имеет два значения. 2) набор используется для самостоятельного хранения и извлечения элементов. карта используется для хранения и извлечения элементов с помощью ключа.

Что еще важно?

Answer 1

Карты и наборы имеют почти одинаковое поведение, и реализация часто использует одну и ту же базовую технику.

Единственное важное отличие состоит в том, что карта не использует для сравнения весь тип value_type, а только ключевую часть.

Answer 2

Обычно вы сразу узнаете, что вам нужно: если у вас просто есть bool для аргумента «значение» на карте, вы, вероятно, захотите использовать набор.

Set - это дискретная математическая концепция, которая, по моему опыту, появляется снова и снова в программировании. Класс stl set является относительно эффективным способом отслеживания множеств, где наиболее распространенными операциями являются вставка / удаление / поиск.

Карты используются, когда объекты имеют уникальную идентичность, которая мала по сравнению со всем их набором атрибутов. Например, веб-страница может быть определена как URL-адрес и байтовый поток содержимого. Вы можете поместить этот поток байтов в набор, но процесс двоичного поиска будет очень медленным (так как содержимое намного больше, чем URL), и вы не сможете найти веб-страницу, если ее содержимое изменится. URL - это идентификатор веб-страницы, поэтому он является ключом карты.

Answer 3

Карта обычно реализуется как набор >.

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

В обоих случаях ключ (для карты) или значение (для набора) должны быть уникальными. Если вы хотите сохранить несколько одинаковых значений, вы должны использовать multimap или multiset.