C++ STL 之 unordered_set 介绍

末蓝、 2022-09-21 14:26 348阅读 0赞

## 简介 ##

C++ 11中出现了两种新的关联容器:unordered\_set和unordered\_map，其内部实现与set和map大有不同，set和map内部实现是基于RB-Tree，而unordered\_set和unordered\_map内部实现是基于哈希表(hashtable)，由于unordered\_set和unordered\_map内部实现的公共接口大致相同，所以本文以unordered\_set为例。

unordered\_set是基于哈希表，因此要了解unordered\_set，就必须了解哈希表的机制。哈希表是根据关键码值而进行直接访问的数据结构，通过相应的哈希函数(也称散列函数)处理关键字得到相应的关键码值，关键码值对应着一个特定位置，用该位置来存取相应的信息，这样就能以较快的速度获取关键字的信息。比如：现有公司员工的个人信息（包括年龄），需要查询某个年龄的员工个数。由于人的年龄范围大约在\[0，200\]，所以可以开一个200大小的数组，然后通过哈希函数[![f(key)=key][f_key_key]][f_key_key_f_key_key]得到key对应的key-value，这样就能完成统计某个年龄的员工个数。而在这个例子中，也存在这样一个问题，两个员工的年龄相同，但其他信息（如：名字、身份证）不同，通过前面说的哈希函数，会发现其都位于数组的相同位置，这里，就涉及到“冲突”。准确来说，冲突是不可避免的，而解决冲突的方法常见的有：开发地址法、再散列法、链地址法(也称拉链法)。而unordered\_set内部解决冲突采用的是----链地址法，当用冲突发生时把具有同一关键码的数据组成一个链表。下图展示了链地址法的使用:

![20150707111017370][]

## unordered\_set ##

模板原型:

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **template** < **class** Key,  
2.      **class** Hash = hash<Key>,  
3.      **class** Pred = equal\_to<Key>,  
4.      **class** Alloc = allocator<Key>  
5.  > **class** unordered\_set;

C++ 11中对unordered\_set描述大体如下：无序集合容器（unordered\_set）是一个存储唯一(unique，即无重复）的关联容器（Associative container），容器中的元素无特别的秩序关系，该容器允许基于值的快速元素检索，同时也支持正向迭代。

在一个unordered\_set内部，元素不会按任何顺序排序，而是通过元素值的hash值将元素分组放置到各个槽(Bucker，也可以译为“桶”），这样就能通过元素值快速访问各个对应的元素（均摊耗时为O（1））。

原型中的Key代表要存储的类型，而hash<Key>也就是你的hash函数，equal\_to<Key>用来判断两个元素是否相等，allocator<Key>是内存的分配策略。一般情况下，我们只关心hash<Key>和equal\_to<Key>参数，下面将介绍这两部分。

## hash<Key> ##

hash<Key>通过相应的hash函数，将传入的参数转换为一个size\_t类型值，然后用该值对当前hashtable的bucket取模算得其对应的hash值。而C++标准库，为我们提供了基本数据类型的hash函数：

1.  整型值：bool、char、unsigned char、wchar\_t、char16\_t、char32\_t、short、int、long、long long、unsigned short、unsigned int、unsigned long、unsigned long long。上述的基本数据类型，其标准库提供的hash函数只是简单将其值转换为一个size\_t类型值，具体可以参考标准库functional\_hash.h头文件，如下所示：
    
    **\[cpp\]**  [view plain][]   [copy][view plain]
    
    1.   /// Primary class template hash.  
    2.    **template**<**typename** \_Tp>  
    3.      **struct** hash;  
    4.    
    5.    /// Partial specializations for pointer types.  
    6.    **template**<**typename** \_Tp>  
    7.      **struct** hash<\_Tp\*> : **public** \_\_hash\_base<**size\_t**, \_Tp\*>  
    8.      \{  
    9.        **size\_t**  
    10.       operator()(\_Tp\* \_\_p) **const** noexcept  
    11.       \{ **return** **reinterpret\_cast**<**size\_t**>(\_\_p); \}  
    12.     \};  
    13.   
    14.   // Explicit specializations for integer types.  
    15. \#define \_Cxx\_hashtable\_define\_trivial\_hash(\_Tp)     \\  
    16.   **template**<>                      \\  
    17.     **struct** hash<\_Tp> : **public** \_\_hash\_base<**size\_t**, \_Tp>  \\  
    18.     \{                                                   \\  
    19.       **size\_t**                                            \\  
    20.       operator()(\_Tp \_\_val) **const** noexcept              \\  
    21.       \{ **return** **static\_cast**<**size\_t**>(\_\_val); \}            \\  
    22.     \};  
    23.   
    24.   /// Explicit specialization for bool.  
    25.   \_Cxx\_hashtable\_define\_trivial\_hash(**bool**)  
    26.   
    27.   /// Explicit specialization for char.  
    28.   \_Cxx\_hashtable\_define\_trivial\_hash(**char**)  
    29.   
    30.   /// Explicit specialization for signed char.  
    31.   \_Cxx\_hashtable\_define\_trivial\_hash(**signed** **char**)  
    32.   
    33.   /// Explicit specialization for unsigned char.  
    34.   \_Cxx\_hashtable\_define\_trivial\_hash(unsigned **char**)  
    35.   
    36.   /// Explicit specialization for wchar\_t.  
    37.   \_Cxx\_hashtable\_define\_trivial\_hash(**wchar\_t**)  
    38.   
    39.   /// Explicit specialization for char16\_t.  
    40.   \_Cxx\_hashtable\_define\_trivial\_hash(char16\_t)  
    41.   
    42.   /// Explicit specialization for char32\_t.  
    43.   \_Cxx\_hashtable\_define\_trivial\_hash(char32\_t)  
    44.   
    45.   /// Explicit specialization for short.  
    46.   \_Cxx\_hashtable\_define\_trivial\_hash(**short**)  
    47.   
    48.   /// Explicit specialization for int.  
    49.   \_Cxx\_hashtable\_define\_trivial\_hash(**int**)  
    50.   
    51.   /// Explicit specialization for long.  
    52.   \_Cxx\_hashtable\_define\_trivial\_hash(**long**)  
    53.   
    54.   /// Explicit specialization for long long.  
    55.   \_Cxx\_hashtable\_define\_trivial\_hash(**long** **long**)  
    56.   
    57.   /// Explicit specialization for unsigned short.  
    58.   \_Cxx\_hashtable\_define\_trivial\_hash(unsigned **short**)  
    59.   
    60.   /// Explicit specialization for unsigned int.  
    61.   \_Cxx\_hashtable\_define\_trivial\_hash(unsigned **int**)  
    62.   
    63.   /// Explicit specialization for unsigned long.  
    64.   \_Cxx\_hashtable\_define\_trivial\_hash(unsigned **long**)  
    65.   
    66.   /// Explicit specialization for unsigned long long.  
    67.   \_Cxx\_hashtable\_define\_trivial\_hash(unsigned **long** **long**)  
    
    对于指针类型，标准库只是单一将地址转换为一个size\_t值作为hash值，这里特别需要注意的是char \*类型的指针，其标准库提供的hash函数只是将指针所指地址转换为一个sieze\_t值，如果，你需要用char \*所指的内容做hash，那么，你需要自己写hash函数或者调用系统提供的hash<string>。
2.  标准库为string类型对象提供了一个hash函数，即：Murmur hash，。对于float、double、long double标准库也有相应的hash函数，这里，不做过多的解释，相应的可以参看functional\_hash.h头文件。

上述只是介绍了基本数据类型，而在实际应用中，有时，我们需要使用自己写的hash函数，那怎么自定义hash函数？参考标准库基本数据类型的hash函数，我们会发现这些hash函数有个共同的特点：通过定义函数对象，实现相应的hash函数，这也就意味我们可以通过自定义相应的函数对象，来实现自定义hash函数。比如：已知平面上有N，每个点的x轴、y轴范围为\[0，100\]，现在需要统计有多少个不同点？hash函数设计为：将每个点的x、y值看成是101进制，如下所示:

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  \#include<bits\\stdc++.h>  
2.  **using** **namespace** std;  
3.  **struct** myHash   
4.  \{  
5.      **size\_t** operator()(pair<**int**, **int**> \_\_val) **const**  
6.      \{  
7.          **return** **static\_cast**<**size\_t**>(\_\_val.first \* 101 + \_\_val.second);  
8.      \}  
9.  \};  
10. **int** main()  
11. \{  
12.     unordered\_set<pair<**int**, **int**>, myHash> S;  
13.     **int** x, y;  
14.     **while** (cin >> x >> y)  
15.         S.insert(make\_pair(x, y));  
16.     **for** (auto it = S.begin(); it != S.end(); ++it)  
17.         cout << it->first << " " << it->second << endl;  
18.     **return** 0;  
19. \}

## equal\_to<key> ##

该参数用于实现比较两个关键字是否相等，至于为什么需要这个参数？这里做点解释，前面我们说过，当不同关键字，通过hash函数，可能会得到相同的关键字值，每当我们在unordered\_set里面做数据插入、删除时，由于unordered\_set关键字唯一性，所以我们得确保唯一性。标准库定义了基本类型的比较函数，而对于自定义的数据类型，我们需要自定义比较函数。这里有两种方法:重载==操作符和使用函数对象，下面是STL中实现equal\_to<Key>的源代码：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **template**<**typename** \_Arg, **typename** \_Result>  
2.      **struct** unary\_function  
3.      \{  
4.        /// @c argument\_type is the type of the argument  
5.        **typedef** \_Arg  argument\_type;     
6.    
7.        /// @c result\_type is the return type  
8.        **typedef** \_Result   result\_type;    
9.      \};  
10. **template**<**typename** \_Tp>  
11.     **struct** equal\_to : **public** binary\_function<\_Tp, \_Tp, **bool**>  
12.     \{  
13.       **bool**  
14.       operator()(**const** \_Tp& \_\_x, **const** \_Tp& \_\_y) **const**  
15.       \{ **return** \_\_x == \_\_y; \}  
16.     \};

## 扩容与缩容 ##

在vector中，每当我们插入一个新元素时，如果当前的容量（capacity)已不足，需要向系统申请一个更大的空间，然后将原始数据拷贝到新空间中。这种现象在unordered\_set中也存在，比如当前的表长为100，而真实存在表中的数据已经大于1000个元素，此时，每个bucker均摊有10个元素，这样就会影响到unordered\_set的存取效率，而标准库通过采用某种策略来对当前空间进行扩容，以此来提高存取效率。当然，这里也存在缩容，原理和扩容类似，不过，需要注意的是，每当unordered\_set内部进行一次扩容或者缩容，都需要对表中的数据重新计算，也就是说，扩容或者缩容的时间复杂度至少为[![O(N)][O_N]][O_N_O_N]。

code：

// unordered_set::find
    #include <iostream>
    #include <string>
    #include <unordered_set>
    
    int main ()
    {
      std::unordered_set<std::string> myset = { "red","green","blue" };
    
      std::string input;
      std::cout << "color? ";
      getline (std::cin,input);
    
      std::unordered_set<std::string>::const_iterator got = myset.find (input);
    
      if ( got == myset.end() )
        std::cout << "not found in myset";
      else
        std::cout << *got << " is in myset";
    
      std::cout << std::endl;
    
      return 0;
    }

[f_key_key]: http://latex.codecogs.com/gif.latex?\dpi%7b100%7d&space;\fn_jvn&space;f%28key%29=key
[f_key_key_f_key_key]: http://private.codecogs.com/eqnedit.php?latex=\dpi%7b100%7d&space;\fn_jvn&space;f%28key%29=key
[20150707111017370]: /images/20220721/97ac9300bfcc4d3c8434551bfd993385.png
[view plain]: http://blog.csdn.net/dream_you_to_life/article/details/46785741#
[O_N]: http://latex.codecogs.com/gif.latex?\dpi%7b100%7d&space;\fn_jvn&space;O%28N%29
[O_N_O_N]: http://private.codecogs.com/eqnedit.php?latex=\dpi%7b100%7d&space;\fn_jvn&space;O%28N%29