unordered container

• 无序容器使用哈希函数组织元素
  
  有序关联容器使用关键字的小于运算符或者给定比较算法来组织元素
  

• 在关键字类型没有明显序关系的情况下，无序容器是非常有用的
  

• 如果维护元素的序代价非常高昂，也建议使用无序容器
  

• 虽然理论上使用哈希算法能获得更好的平均性能，但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作
  

• 通常可以用无序关联容器替换对应的有序关联容器，也可以用有序关联容器来替换对应的无序关联容器
  
  由于元素未按顺序存储，一个使用无序关联容器的程序的输出通常会与使用有序关联容器的版本不同
  

  有序关联容器	无序版本
  map	unordered_map
  set	unordered_set
  multimap	unordered_multimap
  multiset	unordered_multiset

哈希函数

模板函数

又称作哈希模板

形如hash<key_type>, 为关键字到哈希值的映射

关联容器中的每个元素都有哈希值, 哈希值决定了元素所在桶

支持哈希模板的类型

标准库为内置类型（包括指针）提供了hash模板

一些标准库类型，如string和智能指针, 也有对应的hash模板

因此, 无序关联容器的关键字类型可以是内置类型(包括指针), string, 和智能指针

无序容器对关键字类型的要求

1. 要求重载了小于运算符 < , 或者提供代替小于运算符的可调用对象
   
2. 要求重载了相等运算符 == , 或者提供代替相等运算符的可调用对象
   
3. 哈希模板支持, 或者提供代替哈希计算函数的可调用对象
   

示例: 提供代替的可调用对象

1. 同时提供代替相等运算符和哈希值计算的可调用对象
   

   Copy 1size_t hasher(const Sales_data &sd)
    2{
    3    return hash<string>() (sd.isbn());
    4    // 使用一个标准库hash类型对象来计算ISBN成员的哈希值，该hash类型建立在string类型之上
    5}
    6
    7bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
    8{
    9    return lhs.isbn() == rhs.isbn();
   10}
   11
   12using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
   13SD_multiset bookstore(42, hasher, eqOp);

2. 只提供哈希计算函数
   
   元素类型重载了相等运算符 ==
   

   Copy1unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);
   2// 如果自定义类重载了==运算符，可以只传入哈希函数
   3// 省略最后的相等运算符
   

桶

• 无序容器在存储上组织为一组桶，每个桶保存零个或多个元素
  
• 无序容器使用哈希函数将元素映射到桶; 对于相同参数，哈希函数必须返回相同的结果
  
• 容器将具有相同哈希值的元素保存在同一个桶中; 如果容器允许关键字重复，所有具有相同关键字的元素都在同一个桶中
  
• 需要访问元素时，容器首先计算元素的哈希值，即元素所在的桶标识
  
• 若一个桶保存有多个元素，顺序访问这些元素来查找我们需要的那个，此时会用到关键字类型的比较操作
  
• 无序容器的性能依赖于哈希函数的质量和桶的个数与大小
  

桶操作

1. 获取桶个数
   
2. 容器中桶个数上限
   
3. 第n个桶的元素个数(桶大小)
   
4. 返回元素所在桶
   

Copy1c.bucket_count();
2
3c.max_bucket_count();
4
5c.bucket_size(n);
6
7c.bucket(k);

遍历桶中元素

1. 类型成员
   

   指向元素的迭代器
   local_iterator
   const_local_iterator	具有底层const

2. 获取迭代器操作
   

   		常量版本
   begin	指向第n个桶的首元素	cbegin
   end	指向第n个桶的尾后元素	cend

   Copy1c.begin(n);
   2c.end(n);
   3c.cbegin(n);
   4c.cend(n);

哈希策略

1. 获取平均桶大小
   
   每个桶的平均元素个数; 返回类型为float
   

   Copy1c.local_factor();

2. 平均桶大小的上限
   
   容器试图维护的平均桶大小; 返回类型为float
   
   容器会保证平均桶大小不超过该上限: 如有需要, 容器会添加新的桶, 使得load_factor的返回值小于等于max_load_factor的返回值
   

   Copy1c.max_load_factor();

3. 将元素重新装桶(重组存储)
   

   Copy1c.rehash(n);

   满足以下2点:
   

   • 桶个数不小于n
     
     bucket_count
     

     c.bucuket_count() >= n;

   • 桶中有空位
     

     c.bucket_count() > c.size() / c.max_local_factor();

4. 设置容器最小容量
   
   容器可以保存n个元素, 且不会发生rehash
   

   Copy1c.reserve(n);