一、无序容器概述

• STL内部预先定义好的无序容器有：
  • unordered_set：是无序元素的集合，其中每个元素不能重复
  • unordered_multiset：和unordered set的唯一差别是，其元素可以重复
  • unordered_map：元素都是key/value pair，每个key不能重复，value可以重复
  • unordered_multimap：和unordered_map的唯一差别是，其key可以重复
• 在无序容器中，元素没有明确的排序次序。也就是如果容器中有三个元素，当你迭代器容器内的所有元素时，它们的次序可能不同，当你再插入一个新元素时，先前3个元素的相对次序可能会被改变
• 这些无序容器都有一个可选的template实参，用来指明hash函数和等效准则，该准则被用来寻找某给定值，以便判断是否发生重复。默认的等效准则是操作符==
• 无序容器的主要优点是：当你打算查找一个带某特定值的元素，其速度甚至可能快过关联式容器。事实上无序容器提供的是摊提的常量复杂度，前提是你又一个良好的hash函数。然而提供一个良好的hash函数并非容易的事，可能需要提供更多内存作为bucket
• 底层实现：
  • 无序容器通常以hash table实现出来，内部结构是一个“由linked list组成”的array，源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104260053
  • 这几个函数是用来替换已过时的hash_set、hash_map、hash_multiset、hash_multimap，因此你也可以参阅它们的剖析：https://blog.csdn.net/qq_41453285/article/details/104271408
  • 通过某个hash函数的运算，确定元素落于这个array的位置。Hash函数运算的目标是：让每个元素的落点（位置）有助于用户快速访问任何一个元素

二、都支持的操作

• 先介绍这4个无序容器的相同操作，然后介绍各自的操作

• 因为有序的关联容器有的操作，例如insert、find等，无序容器都可以使用。因此通常可以用一个无序容器替换对应的有序容器来完成任务，反之也可以

无序容器的无序性

• 有序的关联容器key值会按序排列，但是无序容器不会，见下面案例

//当使用顺序容器时，会为key自动排序

map<string, int> word_count; //空的
	
string word;
while (cin >> word) {
    ++word_count[word];
}

for (const auto &w : word_count) {
    cout <<w.first <<"  occurs  "<<w.second<<
        ((w.second>1)?"  times":"  time")<< endl;
}

//无序容器的key随机存储

unordered_map<string, int> word_count; //空的
	
string word;
while (cin >> word) {
    ++word_count[word];
}
for (const auto &w : word_count) {
    cout <<w.first <<"  occurs  "<<w.second<<
        ((w.second>1)?"  times":"  time")<< endl;
}

无序容器的管理桶

• 无序容器提供了一组管理桶的函数，这些成员函数允许我们查询容器的状态以及必要时强制容器进行重组。见下面

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

三、unordered_map、unordered_multimap

• 头文件：#include <unordered_map>

unordered_map提供下标操作、unordered_multimap不提供下标操作

• unordered_map的key唯一，提供下标操作；但unordered_multimapkey不唯一，补提供下标操作
• 使用方法：与map类似，见map文章

添加元素（insert、emplace）

• 见map笔记处

删除元素（erase）

• 见map，原理相同

其他操作

• 详细介绍，见map容器处

四、unordered_set、unordered_multiset

• 头文件：#include <unordered_set>

都不提供下标操作（下标运算符和at函数）

• 因为只有一个key，没有key与value的对应关系

添加元素（insert、emplace）

• 见map笔记处

删除元素（erase）

• 见map，原理相同

其他操作

• 详细介绍，见map容器处