C++set源码分析以及c11新特性unordered_set

2018-05-13 本文已影响4人凉拌姨妈好吃

首先先看一下set的模板定义

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

在理解这个定义之前，先了解一下什么是仿函数
仿函数实际上就是拥有函数性质的对象，用法与函数类似，但是其实它是一个类。
它是一个拥有函数功能的对象，必须在类中实现operator()，这个类就有了类似函数的功能。

那么为什么要有仿函数，我们直接用函数不就行了？

因为仿函数是对象！它有记录功能！
下面来看一下仿函数记录功能的应用：
假设有一个vector<string>，你的任务是统计长度小于n的string的个数，如果使用count_if函数的话，你的代码可能长成这样：

 bool LenthIsLessThan(const string& str, int len) {
     return str.length()<len;
 }
 int res=count_if(vec.begin(), vec.end(), LengthIsLessThanFive);
//但是我们的count_if要求函数参数为1，这样使用就不合法

那么根据我们的伪函数的概念，有记录功能，那么我们可以在伪函数内设置一个成员变量用存储长度，如下：

 class ShorterThan {
     public:
         explicit ShorterThan(int maxLength) : length(maxLength) {}
         bool operator() (const string& str) const {
             return str.length() < length;
         }
     private:
         const int length;
 };
 count_if(myVector.begin(), myVector.end(), ShorterThan(length));//直接调用即可

明白了仿函数的概念，那么我们再来看一下set定义

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

第二个参数less<T>也应用了伪函数的概念，我们可以看一看它的源码,也是重写了operator()，继承了binary_function，这个基类可以用来创建具有两个参数的函数对象

template<class _Ty = void>
    struct less
        : public binary_function<_Ty, _Ty, bool>
    {   // functor for operator<
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {   // apply operator< to operands
        return (_Left < _Right);
        }
    };

所以set的排序是通过它的第二个参数进行的，如果要自定义排序行为，可以传入第二个参数，但是默认是使用less

查看set的文档注意到：

The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.

意思就是说在set容器里，我们不能改变里面的值，因为所有的值都是const，但是我们可以插入或者删除这些值
排序的底层框架也是遵循红黑树，前面已经提过红黑树了，就不多说。

unordered_set

底层实现与set的区别

set底层实现是红黑树，而unordered_set的底层是hashtable

什么是hash table？

是根据关键字key直接访问在内存存储位置的数据结构，它是通过一个关键值的函数将所需数据映射到表中的位置来访问数据，这种映射函数叫做"散列函数"，存放记录的数组叫做"散列表"

如何构造hash table?

1.直接定址法：取关键字的某个线性函数为散列地址
即：直接以关键字k或者k加上某个常数（k+c）作为哈希地址，即：h(k) = k + c
坏处：关键字不连续会浪费大量存储空间。
2.除留余数法：取关键值被某个不大于散列表的数p除后的余数作为散列地址（因为留余可能相等，所以这里会发生哈希冲突），对于p得慎重选择，使得元素集合中每一个关键字通过散列函数转换后映射到哈希表的任意地址上的概率相等。

如何解决哈希冲突？

开放定址法

什么是开放定址法？

哈希表中的空闲单元（即为a）既可以被哈希地址为a的关键字使用，也可以被发生冲突的其他关键字使用。谁先找到这个单元谁先占用。

下面介绍几种开放定址

线性探测法：在hash之后，当发现该地址已经存在数据，就放到下一个地址，如果下一个地址也冲突，就继续往下，直到找到没有冲突的位置存下。
平方探测（二次探测）：与上面的类似，也是发现地址存在数据，但是此时不是放到下一个位置，而是放到该位置的平方的位置。
链地址法：如果哈希表空间为0~m-1，设置一个由m个指针分量组成的一维数组ST[m]，凡哈希地址为i的元素都插入到头指针为ST[i]的链表中。（也就是数组+链表结构）
链地址法

unordered_set也是通过链地址法来解决冲突的。
来看一下unordered_set的定义

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

hash<Key>通过相应的哈希函数，将传入的参数转换为一个size_t类型值，然后使用该值对当前的hashtable的桶取模算出对应的hash值。

c++标准库已经提供了基本数据类型的hash函数，但是这里需要注意一点，对于指针，标准库只是将指针的地址转换成一个size_t类型的值作为hash值。如果要使用char *所指向的内容做hash，那么需要自己写hash函数或者调用系统提供的hash<string>
c11为字符串提供了murmur hash这个hash函数（该函数通过不断的乘法旋转减少碰撞率），murmur hash后被google改动为cityhash
当然，我们在使用unordered_set可以传入我们自己写的hash函数
equal_to<Key>
equal_to也是我们前面提到的伪函数

template<class _Ty = void>
    struct equal_to
        : public binary_function<_Ty, _Ty, bool>
    {   // functor for operator==
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {   // apply operator== to operands
        return (_Left == _Right);
        }
    };