体系结构与内核分析第四讲
万用的hash function
hash function就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。
使用以hash table为底层的容器时，必须要为放的元素写一个hash function。在计算机编程里面，所有的data也是由原始的整数、浮点数、字符串组成的，基本的数值型这些本身都有hash function，他们的hash function传回来的就是自己。有没有可能把一个设计出来的数据结构，一个元素，把它拆分开来，然后把它各自的hash code（hash function产生hash code）加起来，就变成这个元素的hash code。hash function是将产生的hash code做到越乱越好，不要重复。将每个hash code相加太过天真：元素容易碰撞，每个篮子挂的元素多，查找慢。从TR1开始有了下面1234帮你写hash function。typename...表示可以接受任意多的模板参数。
hash function设计原则：产生的hash code尽可能减少冲突， 使元素能够尽可能多的落在不同的篮子里。
计算hash code时，0x9e3779b9是借用的黄金比例。
hash function的写法形式有三种：
1.形式1模板参数只需要填元素类型和函数类型就可以，自动产生函数对象被调用。
2.形式2模板参数需要填元素类型和函数类型，创建容器时候还要把真正的函数地址放进来。
3.第三种实现形式是通过对自己的元素作一个偏特化版本实现hash function。G4.9以后有了string的偏特化版本。
代码：
#include
class Customer {
...
};
//-------------------------形式1成员函数---------------------
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const {
return...
};
//-----------------------------------------------------------
unordered_set custset;
//-------------------------形式2一般函数---------------------
size_t customer_hash_func(const Customer& c){
return...
};
//-----------------------------------------------------------
unordered_set
custset(20,customer_hash_func);
unordered_set两种使用方法：一种是针对需要存放的元素类型，定义泛函数。另一种是定义一个hash_function。
tuple
C++11中的tuple（元组）是一个固定大小的不同类型值的集合，是泛化的std::pair。我们可以把他当做一个通用的结构体来用，不需要创建结构体又获取结构体的特征，在某些情况下可以取代结构体使程序更简洁，直观。tuple可以指定任意类型元素。
eg. tuple> t; //sizeof(t) = 32.？
tuple t1(41, 6.3, "nice");
get<0>(t1)取t1的第0个元素。get<1>(t1)取t1的第1个元素...
auto t2 = make_tuple(22, 44, "stacy"); //创建一个tuple,并写入元素。
get<1>(t1) = get<1>(t2); //assign value
tuple之间可以比较大小。
tie绑定，将tuple中对应的各个元素绑定到tie中。
tuple_size获取tuple中value个数。
tuple_element获取tuple中第几个元素的类型。
tuple会自动递归，把元素分隔为head和tail, tail会再分隔为head和tail, 直到tail只有一个元素为止。层层继承， tail作为基类，head作为数据成员。
type traits 类型萃取器
type_traits：回答class中的默认构造、拷贝构造、拷贝赋值、析构函数重要不重要、是否是POD(plain old data, c风格的结构，没有成员函数)等，默认是false。对于自己定义的类型，可以自己定义__type_traits的特化版本。泛化版本（默认）六个typedef。
设计一个复数，有实部和虚部，不必为他写析构函数、拷贝构造函数、拷贝赋值函数，因为不写的话编译器有一个默认版本。
使用：string的析构函数不是虚函数，string的设计上是不打算让用户继承的。has_virtual_destructor是0.，is_polymorphic（是否有多态）是0。
Zoo(const Zoo&) = delete; 不要编译器默认的。
Zoo(Zoo&&) = default; 要编译器默认的搬移构造函数， 和用户不写意义相同。
Zoo& operator=(const Zoo&) = default;
Zoo& operator=(const Zoo&&) = delete; //不要编译器默认的搬移赋值函数。
萃取器可以得知以上这四个函数是否需要编译器给的。
traits实现原理
is_void的实现：is_void类模板继承自__is_void_helper类模板，首先对类型去除const、volatile（多线程用到，易挥发）属性，用remove_cv函数实现，remove_const和remove_volatile各用一个泛化和偏特化版本的函数来使得传入的是否有const（volatile）都会去掉这两个。再传给__is_void_helper，利用它的泛化和特化void，判断是否是void。
is_integral的实现：也是先除去const和volatile属性，再利用__is_integral_helper的泛化和偏特化判断，如果不是和某种特化版本匹配的类型，那么就会使用泛化版本，泛化版本的回答是false。
有些type_traits的实现找不到源代码，是由编译器实现的。
cout是一个类的对象，extern表示cout可以被外界看到，它能接受这么多类型是因为它作了大量的<<重载。如果你想写自己的类型，那么就要仿照写出<<的重载。sub_match对正则表达式的输出。
moveable元素
moveable元素对于容器速度效能的影响：
分别用moveable和non-moveable以insert的方式放进来，红黑树和哈希表的容器，你只要insert，那么它就会落在该落的地方，但是vector、list、deque你要insert必须要告诉它哪里insert。stl里的insert提供插入位置选择，但对于关联式容器，就算指定插入位置，如果不合理，他还是落在它应该落在的地方。
两种拷贝方式：
eg. M c11(c1);
M c12(std::move(c1));
vector放三百万个元素，而拷贝构造函数却调用了七百多万次，是因为vector的成长是两倍两倍的，在成长的过程中引发拷贝构造。如果一开始指定有足够大的vector，就不会有这么大的拷贝构造。
1.moveable和non-moveable的效率差别很大，2.move copy和copy效率差别很大。
list、deque、关联式容器放三百万个元素，拷贝构造也调用三百万次，这是因为他们不像vector是连续的内存空间。
虽然list、deque、关联式容器一开始放元素moveable和non-moveable的效率差别不大，但是后来的操作也会影响。
string是具有moveable的功能。
网友评论