C++中set vs map有什么区别？

Question

我仍然对STL中的map和set数据结构之间的差异感到困惑.我知道set是以排序的方式存储值,那么map呢？它是按排序顺序存储值吗？地图存储成对的值(键,值),这个功能的优点是什么？

Answer 1

至少对于有序版本(std::map和std::set),通过允许您引入外部键()来确定元素的排序(否则无法从数据类型()中导出,map便于a的用例.如果排序可以完全从(通过比较2个元素)得出,那么你通常最好使用a ,在这种情况下你将避免重复密钥.setmap::key_typemapmap::data_typemap::data_typesetmap::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>您想知道是否使用a map或a set存储多个有序元素的元素.如果key跨越整个data(意思data是空的或其他key == data),那么你最好使用a set在这种情况下你将避免a)重复key存储和b)可能必须保持2 key秒同步.如果key不包含在data那里(你必须)使用a map.棘手的部分是何时key是(适当的)子集data.然后,您必须权衡维护重复keys(a map)的成本与data不与key(a set)重叠的构造成本 ,后者可能出现在find操作中.

Answer 2

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

Answer 3

一个map店关键字排序.它将键映射到值.通常它被实现为密钥的二叉搜索树(红黑树).A set是值无关的地图. unordered_map和unordered_set(C++ 11中的新增功能)存储键未排序并使用哈希表进行搜索.

Answer 4

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

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