STL与泛型编程第五周

本页内容是作为 Boolan C++ 开发工程师培训系列的笔记。
因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！

万用哈希函数

在第三周的内容里提到，哈希表需要通过哈希函数来为每一个元素生成一个 Hash code 来作为该元素在哈希表中的 Key。对于一些 Built-in 类型来说，标准库自带了哈希函数（比如数值，字符串）。但对于一些复杂的类型（比如自定义对象）来说，有没有一种通用办法来生成哈希函数？

有一种思路是：因为对象都是由 Built-in 类型组成的，我们可以将对象元素里面的各个基本部分分开计算出 Hash code ，再将其组合到一起（当然简单的加是比较愚蠢的）。

哈希函数的形式与使用

在讨论哈希函数的实现之前，我们先来看一看哈希函数的调用。哈希函数分为三种类型：

非成员哈希函数
成员哈希函数
偏特化版本的哈希函数

非成员哈希函数的是通过函数来表现的：

sizt_t customer_hash_func(const Customer& c) {
....
}

而使用时候需要指定元素类型和哈希函数类型：

unordered_set<Customer, size_t(*) (const Customer&)> custset(20, customer_has_func);

如果是成员哈希函数，需要以运算符重载的形式实现函数功能：

std::size_t operator() (const Customer& c) const {...};

调用的时候在实例化类的时候指定该哈希参数即可：

unordered_set<Customer, CustomerHash> custset;

偏特化版本是成员函数的另外一种形式，是使用结构体实现的：

template <typename T, typename Hash = hash<T>.....>
class unordered_set;

使用的方法与类成员函数的使用方法一致，也是通过 () 的重载来实现。不过不同的是，使用的时候需要借助 hash 结构体指定类型：

template<>
struct hash<MyString> {
...
    sizt_t operator () (const MyString& s) const noexcept {
        return hash<string>() (string(s.get())); } //using hash<string> specialization, defined in bits\basic_string.h
}

万用哈希函数的实现

哈希函数需要针对元素的内容来进行 Hash code 的计算。因此，我们需要哈希函数有能力接收不同类型和不同数量的参数。TR1 版本的 C++ 中提供了一种解决方法：通过递归的手段来对每一个元素进行 Hash code (Seed) 的计算，然后把这些 Hash code 通过一定的算法组合在一起。

为了实现这个方法，我们需要按递归的原理确定几个 case:

基础情况：单个 Seed 与单个元素的基础部分。该情况应该直接使用指定的算法算出新的 Seed，也就是只计算一次（3）。
多个参数情况：该情况需要先将参数列表进行分割：
- 如果未指定 Seed 的默认值，则需要在函数里设定 Seed 的默认值（1）。
- 如果指定了 Seed 的默认值，那么直接进行元素的分割操作（2）。

根据以上的思路，我们不难得出相应的实现方法：

基础形式（3）：

template<typename T>
inline voild hash_val(sizet& seed, const T& val) {
    hash_combine(seed, val); // combines seed once

多个参数形式，无 Seed 初始值（1）：

template<typename... Types>
inline size_t hash_val(const Types&... args) {
   size_t seed = 0; // setting default seed value
   hash_val(seed, args...); //recursively  calling (2) version until reached form 3
   return seed;

多个参数形式，有 Seed 初始值（2）：

template<typename T, typename... Types>
inline size_t hash_val(size_t& seed, const Types&... args) {
    hash_combine(seed, val); // illiterately adding single element seed to the final seed;
    hash_val(seed, args...); separate the next single element
}

基础的 hash_combine() 函数则迭代的对传递进来的每一个 Seed 通过如下算法组合到了最后的结果中：

inline void hash_combine(size_t& sed, const T& val) {
    seed ^=std::hash<T>()(val) + 0X9e3779b9 + (seed<<6) + (seed>>2); //a scatter function for seeds;
}

值得注意的是，以上所有的函数在传递 Seed 的时候都是通过引用来传递的。Seed 在（1）中初始化，直到递归完毕得到结果。使用引用传递保证了在 Seed 的传递过程中实现正确的迭代累积。

PS: 0X9e3779b9 是黄金分割的小树部分。

Tuple的用例

Tuple 是除了 STL 内容之外，标准库定义的一种数据结构。这种数据结构可以指定存放任意个元素，每个元素的类型也可以是任意的。Tuple 的使用方法如下：

//initialize
tuple<string, int, int, complex<double>> t; // a tuple that contains 4 elements with its own types
tuple<int, float, string> t1(41, 63, "nico"); // elements has its own default value
auto t2 = make_tuple(41, 63, "nico"); // auto deduces elements type
//access
get<0>(t1); //get the frist elements of t1
tuple_size<TupleType>::value // return elements amounts
tuple_element<1, TUpleType>::type T; // return the type of specified element in tuple
//other operations:
t1 < t2; t1 = t2;
cout << t1;
tie(i, f, s) = t2; // read elements from t2 and assign them to the parameters in tie() in order; type must match

Tuple的实现细节

Tuple 是一个类，本身也是通过 C++ 中模板的无限参数的功能来实现的。Tuple 在实现中分为头部（Head）和尾部（Tail）。头部代表了当前 Tuple 中第一个元素，而尾部则代表了除此之外剩下的元素。这个看上去和先前的万用哈希函数非常相似；但有一点明显不同的是，Tuple 的实现是通过递归加上继承的方法来实现的。

<html>

</html>

从上图可以看出来，tuple 类通过继承来实现对元素的存储。每一次继承都会分出当前元素的头部和尾部；头部存储在当前类中，尾部则继续递归，直到 Tuple 中再也没有元素为止。那应该如何实现呢？

首先，tuple 类接收两部分模板参数 Head, Tail…。而同时，该类继承了当前 tuple 类的尾部部分；这种方式的继承使得 tuple 类的继承会如同上图所示，一步一步的继承下去，直到遇到基础情况（我们设定为空类）。

template<> class tuple<> {}; // basic case
class tuple<Head, Tail...>: private tuple<Tail...> {
    ....
}

在类中，每一个类都存储当前的头部元素：

Head m_head;
tpyename Head::type head() { return m_head; } // member function that return current head

同时，当前的类有一个指针，指向当前类中尾部的开头：

inherited& tail() { return *this; }

看到这里你可能会问：tail() 是怎么知道我们指向的是当前的尾部开头，而不是当前的类开头的？

实际上， tail() 在这里就是指向了当前的类开头，因为返回的是 this。但是，我们看到前面返回的类型是 inherited&; 这个类型是一个指向当前尾部的引用。因此，即便我们的指针指向的同一个位置，但是在下次递归展开以后，该指针依然能够正确表达下一次递归（子类）中的尾部开头地址。换句话说，指针指向的地址没有变化，变化的是指针指向的数据结构的范围。

<html>

</html>

Type Traits

类型萃取机（Type Traits）是一种有效的分辨类是否具有某种类型的机制。通过这种机制，我们可以针对不同的类型指定不同的操作。这种机制往往应用于算法中（典型例子：Copy()）；根据类型的不同，算法可以做出更有效的针对于该类型的操作。

在 G 2.9 版本中，Type Traits 分为六大类，用于判断几个问题：

Dummy member：不知道是什么也不重要
Has_trivial_default_constructor：默认构造函数对于类是否重要？
Has_trivial_copy_constructor：拷贝构造函数对于类是否重要？
Has_trivial_assignment_constructor：拷贝赋值函数对于类是否重要？
Has_trivial_destructor：析构函数对于类来说是否重要？
is_POD_Type：类中是否有传统的 C 数据结构？

我们知道面向对象设计中，如果类中含有指针，是一定要设计 Big Three 的。因此以上的内容对于算法判断类的具体类型，是非常重要的。

而在 C++11 中，类型萃取机的内容被进行了大量扩展；从此，对类的内容判断的手段也就更加多样化了。需要进一步了解C++ 11的 Type Traits 可以查阅网站：CppReference

Type Traits的使用

前面说过，Type Traits 主要用于类型的判断。我们可以将 Type Traits 想象成问真假的问题；也就是说， Type Traits 的返回值只有 true 和 false。使用 Type Traits 其实很简单，只需要一个接收任意类型的模板函数中使用 Type Traits 来判断就可以：

type_traits_output(const T& x) {
    cout << is_void<T>::value << endl;
    .....
}

C++ 11中的 Type Traits 可以对各种类型做出判断，详情可以见侯老师的几个例子，也可以查询上面的文档；本处就不再赘述。

部分Type Traits的实现

Type Traits 实现的本质是模板对类型的操作。对于一些复杂的判断，比如对类、结构体、C中的结构（POD）或者是 Moveable 元素的判断，在标准库的源码中并没有给出源码。不过可以推测的是，编译器应该参与了这一部分工作。而对于一些比较简单的类型判断，比如 void 和 integral，在源码中还是能找到实现的代码的。下面就来看看这两个 Type Traits 是如何实现的。

首先，无论是 void 和 intergral，在参数传入的时候，都需要考虑去掉一些会影响判断的额外状态；比如 const，volatile。为此，这两个 Type Traits 通过对一个名为 remove_cv 的类偏特化，对特定的，带有 const 和 volatile 关键字的类型进行了处理。remove_cv 自身并不对接收的类型进行处理，而是通过在其内部的两个类 remove_const 和 remove_volatile 进行处理。这两个函数都拥有两个版本：

泛化版本：接收一个参数，返回参数的同类型，也就是不对参数的类型做任何处理
特化版本：接收一个带 const or volatile 关键字的参数，返回参数的普通类型，也就是去掉了关键字的影响。

经过以上的处理，所有带有额外关键字的类型，都会被转化为其对应的普通类型。

接下来，得到了存粹的类型以后，这两个 Type Traits 会通过自身的一个 helper 模板类，对传入的类型进行类型种类的判断。is_void 的判断比较简单，只需要通过一个 void 的特化类进行判断即可；只要是类型转入了该特特化类，返回的值都会是真的。is_integral 的判断也是通过对对应类型的特化返回真值来实现的。可以返回真值的类型有 int、char、bool、long、long long，以及他们的 unsigned 版本。

Cout

Cout 是一个类对象。它属于 IO_stream_withassign 类，而这个类继承自 IOstream 类。这些类的对象的主要功能为输入输出。

Cout 所属的类中定义了绝大部分对基本类型的输出。但如果要使用 Cout 对复杂的类型进行输出的时候，需要在该类型所属类中进行相应的运算符重载。标准库中的重载接收两个参数：

第一参数：运算符左边的类型，比如 Cout 对应的就是 basic_ostream
第二参数：运算符右边的类型，比如 String 对应的就是 basic_stream

表现为代码如下：

operator<<(basic_ostream<_CharT,_Traits>&_os, const basic_string<_CharT,_Traits,Alloc>&_str) {...}

该形式还可以应用到对其他类型的重载，比如智能指针，线程，正则表达式等等。

Move拷贝构造

move() 是 C++2.0 中的一种新的拷贝构造方式，其实质是拷贝构造中的浅拷贝。因此，在进行拷贝构造的时候，相对于传统的拷贝构造（深拷贝），move() 拥有着绝对的速度优势。但也因为 move() 基于浅拷贝实现，因此使用的时候必须要注意：

经过 move() 拷贝构造之后，源数据因为指针的失效，已经不能够再使用了。因此，使用 move() 必须要在不再使用源数据的情况之下操作。
move() 的实现往往搭配着一个引用的引用 && 类型，比如 myString(myString&& str)。

Move拷贝构造对容器的影响

如果元素是支持 move() 的，我们则称该元素为 Movable。对于不同的容器，元素是否支持 move()，对初始化是有很大的影响的。

除此之外，容器自身的结构也对拷贝构造有一些影响。某些容器需要在空间不足的情况下扩容，从而进行大量的拷贝构造（比如 Vector）；而关联容器或者 List 则只需要在创建新元素的时候做拷贝构造。这两者之间的的差别也是非常大的。

目录

STL与泛型编程 第五周