编程之法:面试和算法心得

 主页   资讯   文章   代码   电子书 

关联式容器

一般来说,STL容器分为:

  • 序列式容器(vector/list/deque/stack/queue/heap),和关联式容器。
  • 其中,关联式容器又分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表),这些容器均以RB-tree(red-black 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_无非就是允许键值重复而已。