STL容器：set/map/multiset/multimap 与hash_set/hash_map/hash_multiset/hash_multimap

朱雀 2022-08-26 05:54 185阅读 0赞

转自[http://blog.csdn.net/v\_july\_v/article/details/7382693][http_blog.csdn.net_v_july_v_article_details_7382693]

本文第一部分、从set/map谈到hashtable/hash\_map/hash\_set，简要介绍下set/map/multiset/multimap，及hash\_set/hash\_map/hash\_multiset/hash\_multimap之区别(万丈高楼平地起，基础最重要)，

## 第一部分、从set/map谈到hashtable/hash\_map/hash\_set ##

稍后本文第二部分中将多次提到hash\_map/hash\_set，下面稍稍介绍下这些容器，以作为基础准备。一般来说，STL容器分两种，

*  序列式容器(vector/list/deque/stack/queue/heap)，
 *  关联式容器。关联式容器又分为set(集合)和map(映射表)两大类，以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器均以RB-tree完成。此外，还有第3类关联式容器，如hashtable(散列表)，以及以hashtable为底层机制完成的hash\_set(散列集合)/hash\_map(散列映射表)/hash\_multiset(散列多键集合)/hash\_multimap(散列多键映射表)。也就是说，set/map/multiset/multimap都内含一个RB-tree，而hash\_set/hash\_map/hash\_multiset/hash\_multimap都内含一个hashtable。

所谓关联式容器，类似关联式数据库，每笔数据或每个元素都有一个键值(key)和一个实值(value)，即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时，容器内部结构(RB-tree/hashtable)便依照其键值大小，以某种特定规则将这个元素放置于适当位置。

包括在非关联式数据库中，比如，在MongoDB内，文档(document)是最基本的数据组织形式，每个文档也是以Key-Value（键-值对）的方式组织起来。一个文档可以有多个Key-Value组合，每个Value可以是不同的类型，比如String、Integer、List等等。   
\{ "name" : "July",    
  "sex" : "male",    
   "age" : 23 \}

**set/map/multiset/multimap**

set，同map一样，所有元素都会根据元素的键值自动被排序，因为set/map两者的所有各种操作，都只是转而调用RB-tree的操作行为，不过，值得注意的是，两者都不允许两个元素有相同的键值。  
    不同的是：set的元素不像map那样可以同时拥有实值(value)和键值(key)，set元素的键值就是实值，实值就是键值，而map的所有元素都是pair，同时拥有实值(value)和键值(key)，pair的第一个元素被视为键值，第二个元素被视为实值。  
    至于multiset/multimap，他们的特性及用法和set/map完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于RB-tree的insert\_equal()而非insert\_unique()。

**hash\_set/hash\_map/hash\_multiset/hash\_multimap**

hash\_set/hash\_map，两者的一切操作都是基于hashtable之上。不同的是，hash\_set同set一样，同时拥有实值和键值，且实质就是键值，键值就是实值，而hash\_map同map一样，每一个元素同时拥有一个实值(value)和一个键值(key)，所以其使用方式，和上面的map基本相同。但由于hash\_set/hash\_map都是基于hashtable之上，所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。  
    至于hash\_multiset/hash\_multimap的特性与上面的multiset/multimap完全相同，唯一的差别就是它们hash\_multiset/hash\_multimap的底层实现机制是hashtable（而multiset/multimap，上面说了，底层实现机制是RB-tree），所以它们的元素都不会被自动排序，不过也都允许键值重复。

所以，综上，说白了，什么样的结构决定其什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有自动排序功能，而hash\_set/hash\_map/hash\_multiset/hash\_multimap都是基于hashtable之上，所以不含有自动排序功能，至于加个前缀multi\_无非就是允许键值重复而已。

[http_blog.csdn.net_v_july_v_article_details_7382693]: http://blog.csdn.net/v_july_v/article/details/7382693