STL源码剖析——hash_set、hash_multiset、hash_map、hash_multimap

hash_set

STL只规范复杂度与接口，但不规范实现方法，
set以多半以RB-tree为底层机制。SGI在STL标准规格之外又提供了一个所谓的hash_set，以hashtable为底层机制。

set能快速搜寻元素，不论底层是RB-tree或是hashtable
RB-tree具有自动排序功能，hashtable没有，所以set具有自动排序而hash_set没有
hash_set实值就是键值，和set一样。

构造函数

成员函数

菜，有几个不懂，以后会了继续补充！！！

size()
clear()
max_size()
empty()
swap()
begin()
end()
insert()//insert_unique
insert_noresize()
find()
count()
equal_range()
erase()
resize()
bucket_count()
max_bucket_count()
elems_in_bucket()
==

hash_multiset

• hash_multiset的特性与multiset完全相同，唯一差别在于hash_multiset的底层机制为hashtable，不会自动排序
• hash_multiset和hash_set差别：hash_multiset插入操作采用底层机制hashtable的insert_equal()，hash_set采用insert_unique()

hash_map

hash_map以hashtable为底层机制
map以RB-tree为底层机制
hash_map有实值和键值，使用方式和map完全相同

构造函数

成员函数

[]
size()
clear()
max_size()
empty()
swap()
begin()
end()
insert()//insert_unique
insert_noresize()
find()
count()
equal_range()
erase()
resize()
bucket_count()
max_bucket_count()
elems_in_bucket()
==

hash_multimap

• hash_multimap的特性与multimap完全相同，唯一差别在于hash_multiset的底层机制为hashtable，不会自动排序
• hash_multimap和hash_map差别：hash_multimap插入操作采用底层机制hashtable的insert_equal()，hash_map采用insert_unique()

C++ 11后

hash_set、hash_multiset、hash_map、hash_multimap改为unorder_set、unordered_multiset、unordered_map、unordered_multimap