======STL与泛型编程 第五周====== 本页内容是作为 //Boolan// C++ 开发工程师培训系列的笔记。\\ 因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！ ---- ====万用哈希函数==== 在第三周的内容里提到，哈希表需要通过哈希函数来为每一个元素生成一个 //Hash code// 来作为该元素在哈希表中的 //Key//。对于一些 //Built-in// 类型来说，标准库自带了哈希函数（比如数值，字符串）。但对于一些复杂的类型（比如自定义对象）来说，有没有一种通用办法来生成哈希函数？ \\ \\ 有一种思路是：因为对象都是由 //Built-in// 类型组成的，我们可以将对象元素里面的各个基本部分分开计算出 //Hash code// ，再将其组合到一起（当然简单的加是比较愚蠢的）。 ===哈希函数的形式与使用=== 在讨论哈希函数的实现之前，我们先来看一看哈希函数的调用。哈希函数分为三种类型： * 非成员哈希函数 * 成员哈希函数 * 偏特化版本的哈希函数 非成员哈希函数的是通过函数来表现的： sizt_t customer_hash_func(const Customer& c) { .... } 而使用时候需要指定**元素类型**和**哈希函数类型**： unordered_set custset(20, customer_has_func); 如果是成员哈希函数，需要以运算符重载的形式实现函数功能： std::size_t operator() (const Customer& c) const {...}; 调用的时候在实例化类的时候指定该哈希参数即可： unordered_set custset; 偏特化版本是成员函数的另外一种形式，是使用结构体实现的： template .....> class unordered_set; 使用的方法与类成员函数的使用方法一致，也是通过 ''()'' 的重载来实现。不过不同的是，使用的时候需要借助 ''hash'' 结构体指定类型： template<> struct hash { ... sizt_t operator () (const MyString& s) const noexcept { return hash() (string(s.get())); } //using hash 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 inline voild hash_val(sizet& seed, const T& val) { hash_combine(seed, val); // combines seed once 多个参数形式，无 //Seed// 初始值（//1//）： template 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 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()(val) + 0X9e3779b9 + (seed<<6) + (seed>>2); //a scatter function for seeds; } 值得注意的是，以上所有的函数在传递 //Seed// 的时候都是通过引用来传递的。//Seed// 在 （//1//）中初始化，直到递归完毕得到结果。使用**引用传递**保证了在 //Seed// 的传递过程中实现正确的迭代累积。 \\ \\ //PS: ''0X9e3779b9'' 是黄金分割的小树部分 ^_^。// ====Tuple的用例==== //Tuple// 是除了 //STL// 内容之外，标准库定义的一种数据结构。这种数据结构可以指定存放**任意个元素**，每个元素的**类型**也可以是**任意的**。//Tuple// 的使用方法如下： //initialize tuple> t; // a tuple that contains 4 elements with its own types tuple 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::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// 的实现是通过**递归加上继承**的方法来实现的。 \\ \\
\\ \\ 从上图可以看出来，''tuple'' 类通过继承来实现对元素的存储。每一次继承都会分出当前元素的头部和尾部；头部存储在当前类中，尾部则继续递归，直到 //Tuple// 中再也没有元素为止。那应该如何实现呢？ \\ \\ 首先，''tuple'' 类接收两部分模板参数 ''Head'', ''Tail...''。而同时，该类继承了当前 ''tuple'' 类的尾部部分；这种方式的继承使得 ''tuple'' 类的继承会如同上图所示，一步一步的继承下去，直到遇到**基础情况**（我们设定为**空类**）。 template<> class tuple<> {}; // basic case class tuple: private tuple { .... } 在类中，每一个类都存储当前的头部元素： Head m_head; tpyename Head::type head() { return m_head; } // member function that return current head 同时，当前的类有一个指针，指向当前类中尾部的开头： inherited& tail() { return *this; } 看到这里你可能会问：''tail()'' 是怎么知道我们指向的是当前的尾部开头，而不是当前的类开头的？ \\ \\ 实际上， ''tail()'' 在这里就是指向了当前的类开头，因为返回的是 ''this''。但是，我们看到前面返回的类型是 ''inherited&''; 这个类型是一个指向当前尾部的引用。因此，即便我们的指针指向的同一个位置，但是在下次递归展开以后，该指针依然能够正确表达下一次递归（子类）中的尾部开头地址。换句话说，**指针指向的地址没有变化，变化的是指针指向的数据结构的范围**。 \\ \\
\\ ====Type Traits==== **类型萃取机**（//Type Traits//）是一种有效的分辨**类**是否具有某种类型的机制。通过这种机制，我们可以**针对不同的类型指定不同的操作**。这种机制往往应用于算法中（典型例子：//[[cs:programming:cpp:boolan_cpp:stl_generic_4#其他相关例子|Copy()]]//）；根据类型的不同，算法可以做出更有效的针对于该类型的操作。 \\ \\ 在 //G 2.9// 版本中，//Type Traits// 分为六大类，用于判断几个问题： * //Dummy member//：不知道是什么也不重要m( * //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// 可以查阅网站：[[http://en.cppreference.com/w/cpp/header/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::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// 则只需要在创建新元素的时候做拷贝构造。这两者之间的的差别也是非常大的。 \\ \\ \\