C++ 中的 set 和 map 有什么区别？

What is the difference between set vs map in C++?

提问by SheikCode

I am still confused by the differences between the map and set datastructures in STL. I know set is storing the values in a sorted way, what about map? Does it store the values in sorted order? Map stores pairs of values (key,value), what is the advantage of this feature?

我仍然对 STL 中 map 和 set 数据结构之间的差异感到困惑。我知道 set 以排序的方式存储值，那么 map 呢？它是否按排序顺序存储值？Map 存储成对的值（键，值），这个特性有什么好处？

回答by Vijay Rao

At least for the ordered versions (std::mapand std::set), a mapfacilitates use-cases of a setby allowing you to introduce an external key (map::key_type) to determine ordering of the elements that otherwise can't be derived from map's data type (map::mapped_type). If the ordering can be wholly derived (by comparing 2 elements) from map::mapped_type, then you're typically better off using a set, in which case you'll avoid duplicating the key as map::key_type.

至少对于有序版本 (std::map和std::set)， a通过允许您引入外部键 ( ) 来确定无法从的数据类型 ( )派生的元素的排序，从而map简化了 a 的用例。如果可以从 完全派生（通过比较 2 个元素）排序，那么您通常最好使用 a ，在这种情况下，您将避免将密钥复制为。setmap::key_typemapmap::mapped_typemap::mapped_typesetmap::key_type

In a way, std::mapis redundant and you can always use std::setinstead by introducing a new element type which aggregates keys with data while providing the necessary comparison function. However, this is cumbersome and typically inelegant.

在某种程度上，它std::map是多余的，您始终可以std::set通过引入一种新的元素类型来代替使用，该类型将键与数据聚合在一起，同时提供必要的比较功能。然而，这很麻烦并且通常不优雅。

To clarify why a setmay be cumbersome over a map; A setwill store the <key, data>pair as an element while mapwill maintain a separation between the 2. This means, for instance, that for a findoperation on a setwhere find's parameter is constructed on-the-spot, an entire <key, data>element will have to be constructed while it's really on the keythat's needed for the findoperation. The construction of the datamembers of a set's element is then redundant, and can be rather inefficient if, for instance, datamembers represent disk storage or involve some other complex or else time consuming construction operation. mapalleviates this by only having to construct the actual keyrequired for find.

澄清为什么 aset可能比 a 麻烦map；Aset会将这<key, data>对存储为一个元素，同时map将保持 2 之间的分离。这意味着，例如，对于现场构造where参数的find操作，必须同时构造整个元素这确实是操作所需的。因此， a元素的成员的构造是多余的，并且如果，例如，成员代表磁盘存储或涉及一些其他复杂或耗时的构造操作，则效率可能相当低。只需构建实际所需的setfind<key, data>keyfinddatasetdatamapkeyfind.

To summarize, consider an element <key, data>for which you're wondering whether to use a mapor a setto store multiple ordered elements. If keyspans the entire data(meaning datais empty or else key == data) then you're better off using a setin which case you'll avoid a) duplicating keystorage and b) likely having to keep 2 keys synchronized. If keyis not contained in datathen (you have to) use a map. The tricky part is when keyis a (proper) subset of data. You then have to trade-off the cost of maintaining duplicate keys (for a map) vs the cost of constructing datathat doesn't overlap with key(for a set), the latter which may occur for findoperations.

总而言之，考虑一个<key, data>您想知道是使用 amap还是 aset来存储多个有序元素的元素。如果key跨越整个data（意思data是空或否则key == data），那么你最好使用 aset在这种情况下，你将避免 a) 重复key存储和 b) 可能必须保持 2 keys 同步。如果key不包含在datathen （您必须）中，请使用map. 棘手的部分是 whenkey是data. 然后，您必须权衡维护重复keys（对于 a map）的成本与data不与key（对于 a set）重叠的构建成本 ，后者可能发生在find操作。

回答by NPE

Conceptually, a setis a collection of things, whereas a map is a mapping of keys to values.

从概念上讲，集合是事物的集合，而映射是键到值的映射。

回答by Alexey Voytenko

A mapstores keys sorted. It maps keys to values. Usually it is implemented as a binary search tree (red-black tree) for keys. A setis a map where values are irrelevant. unordered_mapand unordered_set(new in C++11) store keys unsorted and use hash table for search.

Amap存储已排序的键。它将键映射到值。通常它被实现为键的二叉搜索树（红黑树）。Aset是值不相关的映射。 unordered_map和unordered_set（C++11 中的新功能）存储未排序的键并使用哈希表进行搜索。

回答by SzG

std::mapand std::setare extremely similar. They both have a sorted collection of unique keys. Additionally, maphas a value associated with each key.

std::map并且std::set极其相似。它们都有一个排序的唯一键集合。此外，map具有与每个键关联的值。

回答by Marius Bancila

std::mapis an associative container storing pairs of key-values with unique keys. std::setis also an associative container that stores a sorter set of objects (or keys).

std::map是一个关联容器，用于存储具有唯一键的键值对。std::set也是一个关联容器，用于存储一组排序对象（或键）。

You should have a look at std::mapand std::set.

你应该看看std::map和std::set。