set map implementation in C++

Question

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

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

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

Спасибо!

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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