unordered_set笔记

http://www.cplusplus.com/reference/unordered_set/unordered_set/

unordered_set 模板原型:

template < class Key,  
    class Hash = hash<key>,
	class Pred = equal_to<key>,
	class Alloc = allocator<key>
	> class unordered_set;

当比较unordered_set中某两个元素时, 先调用hash<key>, 如果hash<key> 不相等, 说明两个元素不同, 如果hash<key> 值相等, 则调用equal_to<key>, 判断两个元素是否完全相等. (Hash函数和Compare函数都可以自定义)

C++ 11中对unordered_set描述大体如下:无序集合容器(unordered_set)是一个存储唯一(unique,即无重复)的关联容器(Associative container),容器中的元素无特别的秩序关系,该容器允许基于值的快速元素检索,同时也支持正向迭代。 在一个unordered_set内部,元素不会按任何顺序排序,而是通过元素值的hash值将元素分组放置到各个槽(Bucker,也可以译为“桶”),这样就能通过元素值快速访问各个对应的元素(均摊耗时为O(1))。 原型中的Key代表要存储的类型,而hash也就是你的hash函数,equal_to用来判断两个元素是否相等,allocator是内存的分配策略。一般情况下,我们只关心hash和equal_to参数,下面将介绍这两部分。

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

/// Primary class template hash. template struct hash;

/// Partial specializations for pointer types. template struct hash<\_Tp*> : public \_\_hash\_base<size\_t, \_tp*=""> { size\_t operator()(\_Tp* \_\_p) const noexcept { return reinterpret_cast(__p); } }; </size_t,>

// Explicit specializations for integer types.

define \_Cxx\_hashtable\_define\_trivial\_hash(\_Tp) \
======================================================

template<> \ struct hash<\_Tp> : public \_\_hash\_base<size\_t, \_tp=""> \ { \ size\_t \ operator()(\_Tp \_\_val) const noexcept \ { return static_cast(__val); } \ }; </size_t,>

/// Explicit specialization for bool. \_Cxx\_hashtable\_define\_trivial_hash(bool)

/// Explicit specialization for char. \_Cxx\_hashtable\_define\_trivial_hash(char)

/// Explicit specialization for signed char. \_Cxx\_hashtable\_define\_trivial_hash(signed char)

/// Explicit specialization for unsigned char. \_Cxx\_hashtable\_define\_trivial_hash(unsigned char)

/// Explicit specialization for wchar\_t. \_Cxx\_hashtable\_define\_trivial\_hash(wchar_t)

/// Explicit specialization for char16\_t. \_Cxx\_hashtable\_define\_trivial\_hash(char16_t)

/// Explicit specialization for char32\_t. \_Cxx\_hashtable\_define\_trivial\_hash(char32_t)

/// Explicit specialization for short. \_Cxx\_hashtable\_define\_trivial_hash(short)

/// Explicit specialization for int. \_Cxx\_hashtable\_define\_trivial_hash(int)

/// Explicit specialization for long. \_Cxx\_hashtable\_define\_trivial_hash(long)

/// Explicit specialization for long long. \_Cxx\_hashtable\_define\_trivial_hash(long long)

/// Explicit specialization for unsigned short. \_Cxx\_hashtable\_define\_trivial_hash(unsigned short)

/// Explicit specialization for unsigned int. \_Cxx\_hashtable\_define\_trivial_hash(unsigned int)

/// Explicit specialization for unsigned long. \_Cxx\_hashtable\_define\_trivial_hash(unsigned long)

/// Explicit specialization for unsigned long long. \_Cxx\_hashtable\_define\_trivial_hash(unsigned long long)

对于指针类型,标准库只是单一将地址转换为一个size_t值作为hash值,这里特别需要注意的是char *类型的指针,其标准库提供的hash函数只是将指针所指地址转换为一个sieze_t值,如果,你需要用char *所指的内容做hash,那么,你需要自己写hash函数或者调用系统提供的hash<string>。 标准库为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进制,如下所示:

#include<bits\stdc++.h>  
using namespace std;  
struct myHash   
{  
    size_t operator()(pair<int, int> __val) const  
    {  
        return static_cast<size_t>(__val.first * 101 + __val.second);  
    }  
};  
int main()  
{  
    unordered_set<pair<int, int>, myHash> S;  
    int x, y;  
    while (cin >> x >> y)  
        S.insert(make_pair(x, y));  
    for (auto it = S.begin(); it != S.end(); ++it)  
        cout << it->first << " " << it->second << endl;  
    return 0;  
} 

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


template<typename _Arg, typename _Result>  
    struct unary_function  
    {  
      /// @c argument_type is the type of the argument  
      typedef _Arg  argument_type;     

      /// @c result_type is the return type  
      typedef _Result   result_type;    
    };  
template<typename _Tp>  
    struct equal_to : public binary_function<_Tp, _Tp, bool>  
    {  
      bool  
      operator()(const _Tp& __x, const _Tp& __y) const  
      { return __x == __y; }  
    }; 

扩容与缩容

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

code:

// unordered_set::find
#include <iostream>
#include <string>
#include <unordered_set>  </unordered_set></string></iostream>

int main ()
{
std::unordered_set<std::string> myset = { "red","green","blue" };  </std::string>

std::string input;
std::cout &lt;&lt; "color? ";  
  getline (std::cin,input);  

  std::unordered_set<std::string>::const_iterator got = myset.find (input);  </std::string>

if ( got == myset.end() )
std::cout &lt;&lt; "not found in myset";  
  else  
    std::cout &lt;&lt; *got &lt;&lt; " is in myset";  

  std::cout &lt;&lt; std::endl;  

  return 0;  
}
Licensed under CC BY-NC-SA 4.0
Built with Hugo
主题 StackJimmy 设计