Ответ 1
Как минимум для упорядоченных версий (std::map и std::set), map облегчает использование set, позволяя вам ввести внешний ключ (map::key_type), чтобы определить порядок элементы, которые иначе не могут быть получены из типа данных map (map::data_type). Если упорядочение может быть полностью выведено (путем сравнения двух элементов) из map::data_type, тогда вам обычно лучше использовать set, и в этом случае вы избежите дублирования ключа как map::key_type.
В некотором смысле, std::map является избыточным, и вы всегда можете использовать std::set вместо этого, введя новый тип элемента, который объединяет ключи с данными и предоставляет необходимую функцию сравнения. Однако это громоздко и обычно неэлегантно.
Чтобы выяснить, почему a set может быть громоздким по a map; A set будет хранить пару <key, data> в качестве элемента, а map будет поддерживать разделение между 2. Это означает, например, что для операции find в set, где параметр find построенный на месте, весь элемент <key, data> должен быть построен, хотя он действительно находится на key, который необходим для операции find. Конструкция элементов data элемента set тогда избыточна и может быть довольно неэффективной, если, например, члены data представляют дисковое хранилище или связаны с какой-либо другой сложной или долговременной конструкцией. map устраняет это, только создавая фактический key, необходимый для find.
Подводя итог, рассмотрим элемент <key, data>, для которого вам интересно, использовать ли map или set для хранения нескольких упорядоченных элементов. Если key охватывает весь data (это означает, что data пуст или еще key == data), вам лучше использовать set, в этом случае вы избежите a) дублирования хранилища key и b), вероятно, потребуется синхронизировать 2 key. Если key не содержится в data, тогда (вы должны) использовать map. Трудная часть заключается в том, что key является (правильным) подмножеством в data. Затем вам необходимо скомпенсировать стоимость поддержания дубликата key (для a map) и стоимости построения data, которая не перекрывается с key (для a set), последняя, которая может произойти для операций find.