What & How & Why

您在这里: start » cs » programming » cpp » boolan_cpp » stl_generic_5

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:programming:cpp:boolan_cpp:stl_generic_5 [2024/01/14 13:46] – 移除 - 外部编辑 (未知日期) 127.0.0.1cs:programming:cpp:boolan_cpp:stl_generic_5 [2024/01/14 13:47] (当前版本) – ↷ 链接因页面移动而自动修正 codinghare
行 1: 行 1:
 +======STL与泛型编程 第五周======
 +本页内容是作为 //Boolan// C++ 开发工程师培训系列的笔记。\\
 +<wrap em>因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！</wrap>
 +----
 +
 +====万用哈希函数====
 +
 +在第三周的内容里提到，哈希表需要通过哈希函数来为每一个元素生成一个 //Hash code// 来作为该元素在哈希表中的 //Key//。对于一些 //Built-in// 类型来说，标准库自带了哈希函数（比如数值，字符串）。但对于一些复杂的类型（比如自定义对象）来说，有没有一种通用办法来生成哈希函数？
 +\\
 +\\
 +有一种思路是：因为对象都是由  //Built-in// 类型组成的，我们可以将对象元素里面的各个基本部分分开计算出 //Hash code// ，再将其组合到一起（当然简单的加是比较愚蠢的）。
 +
 +===哈希函数的形式与使用===
 +
 +在讨论哈希函数的实现之前，我们先来看一看哈希函数的调用。哈希函数分为三种类型：
 +  * 非成员哈希函数
 +  * 成员哈希函数
 +  * 偏特化版本的哈希函数
 +非成员哈希函数的是通过函数来表现的：
 +<code cpp linenums:1>
 +sizt_t customer_hash_func(const Customer& c) {
 +....
 +}
 +</code>
 +而使用时候需要指定**元素类型**和**哈希函数类型**：
 +<code cpp linenums:1>
 +unordered_set<Customer, size_t(*) (const Customer&)> custset(20, customer_has_func);
 +</code>
 +如果是成员哈希函数，需要以运算符重载的形式实现函数功能：
 +<code cpp linenums:1>
 +std::size_t operator() (const Customer& c) const {...};
 +</code>
 +调用的时候在实例化类的时候指定该哈希参数即可：
 +<code cpp linenums:1>
 +unordered_set<Customer, CustomerHash> custset;
 +</code>
 +偏特化版本是成员函数的另外一种形式，是使用结构体实现的：
 +<code cpp linenums:1>
 +template <typename T, typename Hash = hash<T>.....>
 +class unordered_set;
 +</code>
 +使用的方法与类成员函数的使用方法一致，也是通过 ''()'' 的重载来实现。不过不同的是，使用的时候需要借助 ''hash'' 结构体指定类型：
 +<code cpp linenums:1>
 +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
 +}
 +</code>
 +
 +===万用哈希函数的实现===
 +
 +哈希函数需要针对元素的内容来进行 //Hash code// 的计算。因此，我们需要哈希函数有能力接收**不同类型和不同数量**的参数。//TR1// 版本的 C++ 中提供了一种解决方法：通过**递归**的手段来对每一个元素进行 //Hash code// (Seed) 的计算，然后把这些  //Hash code// 通过一定的算法组合在一起。
 +\\
 +\\
 +为了实现这个方法，我们需要按递归的原理确定几个 case:
 +  * 基础情况：单个 //Seed// 与单个元素的基础部分。该情况应该直接使用指定的算法算出新的 //Seed//，也就是只计算一次（//3//）。
 +  * 多个参数情况：该情况需要先将参数列表进行分割：
 +    * 如果未指定 //Seed// 的默认值，则需要在函数里设定 //Seed// 的默认值（//1//）。
 +    * 如果指定了 //Seed// 的默认值，那么直接进行元素的分割操作（//2//）。
 +根据以上的思路，我们不难得出相应的实现方法：
 +\\
 +\\
 +基础形式（//3//）：
 +<code cpp linenums:1>
 +template<typename T>
 +inline voild hash_val(sizet& seed, const T& val) {
 +    hash_combine(seed, val); // combines seed once
 +</code>
 +多个参数形式，无 //Seed// 初始值（//1//）：
 +<code cpp linenums: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;
 +</code>
 +多个参数形式，有 //Seed// 初始值（//2//）：
 +<code cpp linenums:1>
 +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
 +}
 +</code>
 +\\
 +基础的 ''hash_combine()'' 函数则迭代的对传递进来的每一个 //Seed// 通过如下算法组合到了最后的结果中：
 +<code cpp linenums:1>
 +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;
 +}
 +</code>
 +值得注意的是，以上所有的函数在传递 //Seed// 的时候都是通过引用来传递的。//Seed// 在 （//1//）中初始化，直到递归完毕得到结果。使用**引用传递**保证了在 //Seed// 的传递过程中实现正确的迭代累积。
 +\\
 +\\
 +//PS: ''0X9e3779b9'' 是黄金分割的小树部分 ^_^。//
 +
 +====Tuple的用例====
 +
 +//Tuple// 是除了 //STL// 内容之外，标准库定义的一种数据结构。这种数据结构可以指定存放**任意个元素**，每个元素的**类型**也可以是**任意的**。//Tuple// 的使用方法如下：
 +<code cpp linenums:1>
 +//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
 +</code>
 +
 +===Tuple的实现细节===
 +
 +//Tuple// 是一个类，本身也是通过 C++ 中模板的无限参数的功能来实现的。//Tuple// 在实现中分为**头部**（//Head//）和**尾部**（//Tail//）。头部代表了当前 //Tuple// 中第一个元素，而尾部则代表了除此之外剩下的元素。这个看上去和先前的万用哈希函数非常相似；但有一点明显不同的是，//Tuple// 的实现是通过**递归加上继承**的方法来实现的。
 +\\
 +\\
 +<html><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/s_lib_tuple.svg"  width="900"/>
 +</div>
 +</html>
 +\\
 +\\
 +从上图可以看出来，''tuple'' 类通过继承来实现对元素的存储。每一次继承都会分出当前元素的头部和尾部；头部存储在当前类中，尾部则继续递归，直到 //Tuple// 中再也没有元素为止。那应该如何实现呢？
 +\\
 +\\
 +首先，''tuple'' 类接收两部分模板参数 ''Head'', ''Tail...''。而同时，该类继承了当前 ''tuple'' 类的尾部部分；这种方式的继承使得 ''tuple'' 类的继承会如同上图所示，一步一步的继承下去，直到遇到**基础情况**（我们设定为**空类**）。
 +<code cpp linenums:1>
 +template<> class tuple<> {}; // basic case
 +class tuple<Head, Tail...>: private tuple<Tail...> {
 +    ....
 +}
 +</code>
 +在类中，每一个类都存储当前的头部元素：
 +<code cpp linenums:1>
 +Head m_head;
 +tpyename Head::type head() { return m_head; } // member function that return current head
 +</code>
 +同时，当前的类有一个指针，指向当前类中尾部的开头：
 +<code cpp linenums:1>
 +inherited& tail() { return *this; }
 +</code>
 +看到这里你可能会问：''tail()'' 是怎么知道我们指向的是当前的尾部开头，而不是当前的类开头的？
 +\\
 +\\
 +实际上， ''tail()'' 在这里就是指向了当前的类开头，因为返回的是 ''this''。但是，我们看到前面返回的类型是 ''inherited&''; 这个类型是一个指向当前尾部的引用。因此，即便我们的指针指向的同一个位置，但是在下次递归展开以后，该指针依然能够正确表达下一次递归（子类）中的尾部开头地址。换句话说，**指针指向的地址没有变化，变化的是指针指向的数据结构的范围**。
 +\\
 +\\
 +<html><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/tuple_head_tail.svg"  width="600"/>
 +</div>
 +</html>
 +\\
 +
 +====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// 来判断就可以：
 +<code cpp linenums:1>
 +type_traits_output(const T& x) {
 +    cout << is_void<T>::value << endl;
 +    .....
 +}
 +</code>
 +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''
 +表现为代码如下：
 +<code cpp linenums:1>
 +operator<<(basic_ostream<_CharT,_Traits>&_os, const basic_string<_CharT,_Traits,Alloc>&_str) {...}
 +</code>
 +该形式还可以应用到对其他类型的重载，比如智能指针，线程，正则表达式等等。
 +
 +====Move拷贝构造====
 +
 +''move()'' 是 C++2.0 中的一种新的拷贝构造方式，其实质是拷贝构造中的**浅拷贝**。因此，在进行拷贝构造的时候，相对于传统的拷贝构造（深拷贝），''move()'' 拥有着绝对的速度优势。但也因为 ''move()'' 基于浅拷贝实现，因此使用的时候必须要注意：
 +  * 经过 ''move()'' 拷贝构造之后，源数据因为指针的失效，已经不能够再使用了。因此，使用 ''move()'' 必须要在**不再使用源数据的情况之下操作**。
 +  * ''move()'' 的实现往往搭配着一个**引用的引用** ''&&'' 类型，比如 ''myString(myString&& str)''。
 +
 +===Move拷贝构造对容器的影响===
 +
 +如果元素是支持 ''move()'' 的，我们则称该元素为 //Movable//。对于不同的容器，元素是否支持 ''move()''，对初始化是有很大的影响的。
 +\\
 +\\
 +除此之外，容器自身的结构也对拷贝构造有一些影响。某些容器需要在空间不足的情况下扩容，从而进行大量的拷贝构造（比如 //Vector//）；而关联容器或者 //List// 则只需要在创建新元素的时候做拷贝构造。这两者之间的的差别也是非常大的。
 +\\
 +\\
 +\\