侯捷 C++ STL标准库和泛型编程 —— 9 STL周围

最后一篇，完结辽！😋

9 STL周围

9.1 万用Hash Function

Hash Function的常规写法：其中 hash_val 就是万用Hash Function

class CustumerHash
{ 
public:
	size_t operator()(const Customer& c) const
	{ return hash_val(c.fname(), c.lname(), c.no()); }
};
1
2
3
4
5
6

还可以直接用函数实现，或者写一个 hash 的特化版本

原理：

通过三个函数重载实现从给入数据中逐一提取来不断改变 seed

// 第一个函数 首先进入该函数
template <typename... Types>
inline size_t hash_val(const Type&... args)
{
	size_t seed = 0; // 设置初始seed
	hash_val(seed, args...); // 进入第二个函数
	return seed; // seed就是最后的HashCode
}

// 第二个函数 该函数中逐一提取一个参数
template <typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Types&... args)
{
	hash_combine(seed, val); // 逐一取val，改变seed
	hash_val(seed, args...); // 递归调用自己，直到取完进入第三个函数
}

// 第三个函数
template <typename T>
inline void hash_val(size_t& seed, const T& val)
{
	hash_combine(seed, val); // 取最后一个val，改变seed
}

// 改变seed的函数
template <typename T>
inline void hash_combine(size_t& seed, const T& val)
{
    // 乱七八糟的运算，越乱越好
	seed ^= hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

C++11中 variadic templates：

从传入的内容（任意个数，任意元素类型）分为一个和其他，递归再分为一个和其他······

0x9e3779b9：是黄金比例！

9.2 Tuple

可以将一些东西组合在一起

9.2.1 用例

• 创建 tuple

  tuple<string, int, int, complex<double>> t; 
  
  tuple<int, float, string> t1(41, 6.3, "nico"); 
  
  auto t2 = make_tuple(22, 44, "stacy");
  1
  2
  3
  4
  5

• 输出 tuple

  // 输出t1中的第一个
  cout << get<0>(t1) << endl; // 41
  cout << t << endl; // 在VS2022上并没有<<的重载
  1
  2
  3

• 运算

  t1 = t2;
  
  if(t1 < t2) // 以特定的方式进行的比较
  {
      ...
  }
  1
  2
  3
  4
  5
  6

• 绑定解包

  tuple<int, float, string> t3(77, 1.1, "more light");
  int i;
  float f;
  string s;
  
  tie(i, f, s) = t3; // i == 77, f == 1.1, s == "more light"
  1
  2
  3
  4
  5
  6

• // tuple里有多少类型
  tuple_size< tuple<int, float, string> >::value; // 3
  
  // 取tuple里面的类型，前面一堆代表float
  tuple_element<1, TupleType>::type fl = 1.0; // float fl = 1.0;
  1
  2
  3
  4
  5

9.2.2 原理

依然是使用 variadic templates，通过递归继承，不断从 ... 中提取内容

// 空的tuple
template <> class tuple<> {}; // 直到取完

// tuple主体
template <typename Head, typename... Tail>
class tuple<Head, Tail...>
	: private tuple<Tail...> // 递归继承
{
    typedef tuple<Tail...> inherited;
public:
	tuple() {}
	tuple(Head v, Tail... vtail) 
        : m_head(v), inherited(vtail...) {}
	...
protected:
	Head m_head; // 每次取出的元素
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

👈🏻不断的继承就可以实现不同类型的组合了

其余函数：

...
{
public:
    ...
	Head head() { return m_head; }
	inherited& tail() { return *this; } // 通过转型获得Tail部分
    ...
};
1
2
3
4
5
6
7
8

一般不这么用

9.3 type traits

9.3.1 用例

GCC2.9中：

默认的 __type_traits 进行了一系列泛化的设定（trivial 是不重要的意思）

 struct __true_type {};
struct __false_type {};

template <class type>
struct __type_traits
{
	typedef __true_type this_dummy_member_must_be_first;
	typedef __false_type has_trivial_default_constructor;
	typedef __false_type has_trivial_copy_constructor;
	typedef __false_type has_trivial_assignment_operator;
	typedef __false_type has_trivial_destructor;
	typedef __false_type is_POD_type; // Plain Old Data 类似C的struct
};
1
2
3
4
5
6
7
8
9
10
11
12
13

还会通过特化来实现针对不同类型的设定，例

template <> struct __type_traits<int>
{
	typedef __true_type has_trivial_default_constructor;
	typedef __true_type has_trivial_copy_constructor;
	typedef __true_type has_trivial_assignment_operator;
	typedef __true_type has_trivial_destructor;
	typedef __true_type is_POD_type;
};
1
2
3
4
5
6
7
8

C++11中：
有了很多个 type traits，可以回答更多问题

测试：

cout << is_void<T>::value << endl;
cout << is_integral<T>::value << endl;
cout << is_floating_point<T>::value << endl;
cout << is_array<T>::value << endl;
...
1
2
3
4
5

不论是什么类型都可以自动检测它的 traits，非常厉害！（里面有虚函数——就能自动检测出它有多态性）

9.3.2 原理

模板的作用

例 is_integral

依然是采用的一种问答的方式实现的

template <typename _Tp>
struct is_integral
	:public __is_intagral_helper<typename remove_cv<_Tp>::type>::type
{ };
1
2
3
4

首先 remove_cv（const 和 volatile）

// 通过偏特化实现remove const
template <typename _Tp>
struct remove_const
{ typedef _Tp type };

template <typename _Tp>
struct remove_const<_Tp const>
{ typedef _Tp type };

// remove volatile 同理
1
2
3
4
5
6
7
8
9
10

再通过 __is_intagral_helper 进行问答

// 通过偏特化实现
template <typename>
struct __is_integral_helper
	:public false_type { };

template <>
struct __is_integral_helper<bool>
	:public true_type { };

template <>
struct __is_integral_helper<int>
	:public true_type { };

template <>
struct __is_integral_helper<long>
	:public true_type { };

...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

其他深入 class 内部的一些 traits 比如是否有虚函数，是否是一个类，是否是POD等等，其实现可能都与编译器有关

9.4 move

moveable class 中有：

// move ctor
MyString(MyString&& str) noexcept // 用&&与普通版本区别开
    : _data(str._data), _len(str._len)
{
    str._len = 0;
    str._data = NULL; // 避免析构函数释放资源
}

// move assignment
MyString& operator=(MyString&& str) noexcept
{
    if (this != &str)
    {
        _len = str._len;
        _data = str._data;
        str._len = 0;
        str._data = NULL; // 避免析构函数释放资源
    }
    return *this;
}

// dtor
virtual ~MyString()
{
    if(_data) delete _data; // 一定要检查
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

MyString C11(C1); // ctor
MyString C12(move(C1)); // move ctor
1
2

是==浅拷贝==，并且把之前的指向去除了

对于 vector 这样的容器，其用 move 就只是 swap 了三根指针，非常快！

move 之后原来的东西不能再使用，比如拿数据插入容器，用临时对象，编译器看到就会自动使用 move 版本的

MyString C11(C1); 时，创建了一个实例 C11，编译器就不知道是否能用 move，就需要自己 MyString C12(move(C1)); 使用 move，但注意之后==一定不能用原来的 C1==

&&（右值引用）这是C++11引入的特性，右值引用用于处理临时对象或将资源所有权转移给其他对象，以提高性能和资源管理