零、前言

本章主要讲解unordered系列关联式容器及其底层结构和模拟实现，还有哈希的相关应用等

一、unordered系列关联式容器

概念：

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想

最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同

unordered_map/unordered_set与map/set基本上只有底层实现上的区别，前者是哈希，后者是红黑树

unordered_map/unordered_set与unordered_multimap/unordered_multiset的区别是是否允许键值冗余

unordered系列关联式容器因为底层不是红黑树了，所以遍历的结果不是排序好的序列

1、unordered_map介绍及使用

概念：

unordered_map是存储<key, value>键值对的关联式容器，其允许通过key值快速的索引到与其对应是value

在unordered_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同

在内部，unordered_map没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中

unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低

unordered_map实现了直接访问操作符（operator[]），它允许使用key作为参数直接访问value

它的迭代器是单向正向迭代器

接口介绍：

unordered_map的构造

2. unordered_map的容量

3. unordered_map的迭代器

4. unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回

5. unordered_map的查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为 1，对于unordered_multimap才是允许键值冗余的

6. unordered_map的修改操作

7. unordered_map的桶操作

• 使用示例：

void test_unordered_map()
{
  unordered_map<string, string> dict;
  dict.insert(make_pair("string", ""));
  dict.insert(make_pair("sort", ""));
  auto it = dict.begin();
  while (it != dict.end())
  {
    cout << it->first << ":" << it->second << endl;
    ++it;
  }
  cout << endl;
}

2、unordered_set的介绍及使用

概念：

unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素

在unordered_set中，元素的值同时也是唯一地标识它的key

在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中

unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低

它的迭代器是单向前向迭代器

接口介绍：

unordered_set当中常用的成员函数

成员函数 功能

insert 插入指定元素

erase 删除指定元素

find 查找指定元素

size 获取容器中元素的个数

empty 判断容器是否为空

clear 清空容器

swap 交换两个容器中的数据

count 获取容器中指定元素值的元素个数

迭代器相关函数

成员函数 功能

begin 获取容器中第一个元素的正向迭代器

end 获取容器中最后一个元素下一个位置的正向迭代器

使用示例：

void test_unordered_set()
{
  unordered_set<int> s;
  s.insert(3);
  s.insert(4);
  s.insert(5);
  s.insert(3);
  s.insert(1);
  s.insert(2);
  s.insert(6);
  unordered_set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

3、性能比较

• 测试代码：

void test_op()
{
  set<int> s;
  unordered_set<int> us;
  const int n = 1000000;
  vector<int> v;
  srand(time(0));
  for (size_t i = 0; i < n; ++i)
  {
    v.push_back(rand());
  }
  size_t begin1 = clock();
  for (auto e : v)
  {
    s.insert(e);
  }
  size_t end1 = clock();
  size_t begin2 = clock();
  for (auto e : v)
  {
    us.insert(e);
  }
  size_t end2 = clock();
  cout << "set insert:" << end1 - begin1 << endl;
  cout << "unordered_set insert:" << end2 - begin2 << endl;
  cout << "=====================" << endl;
  size_t begin3 = clock();
  for (auto e : v)
  {
    s.find(e);
  }
  size_t end3 = clock();
  size_t begin4 = clock();
  for (auto e : v)
  {
    us.find(e);
  }
  size_t end4 = clock();
  cout << "set find:" << end3 - begin3 << endl;
  cout << "unordered_set find:" << end4 - begin4 << endl;
  cout << "=====================" << endl;
  size_t begin5 = clock();
  for (auto e : v)
  {
    s.erase(e);
  }
  size_t end5 = clock();
  size_t begin6 = clock();
  for (auto e : v)
  {
    us.erase(e);
  }
  size_t end6 = clock();
  cout << "set erase:" << end5 - begin5 << endl;
  cout << "unordered_set erase:" << end6 - begin6 << endl;
}

总结：使用底层为哈希的容器总体的效率是非常高的，对于关联式set/map的复杂度能达到O(logN)，而unordered系列关联式容器可以达到接近O(1)的水平