本篇文章是 TinySTL 实现的系列文章的第一篇。撰写初衷是为了对学习《STL 源码剖析》一书所做的总结回顾，并记录一些思考，顺便也作为我参照SGI STL源码实现的一个 TinySTL 项目的介绍文档，相关代码会陆续上传到我的github。

1 traits 编程技法

traits 编程技法是C++泛型编程中常用技巧，这里先简单地概括一下其作用和目的。

• 作用：通过函数模板来对具体对象或变量进行推导以获取其类型或某种特性。
• 目的1：针对获得的类型和某种特性来对实现函数进行优化以达到更高的性能。
• 目的2：通过提取出的类型作为模板函数的返回类型，方便函数实现。

关于目的1，这里可以举一个迭代器的例子。例如 STL 中的迭代器型别有五种类型

比如我有个迭代器iter，现在有个操作要求iter前进n步来读写数据。

因为事先不知道迭代器的类型，我只能保守地猜测其只能自增自减，这样复杂度就是O(n)，但如果我运用traits技巧使用模板iterator_traits<iter>::category（后续会介绍，现在只需要知道其可以获得迭代器类型即可）来获得迭代器类型知道了其是Randon access iterator，那么直接iter += n即可，此时复杂度就是O(1)。

对于目的2，这里也简单说一下。因为在C++11之前并没有decltype关键字，所以在编写模板函数的时候，函数返回类型是不能通过模板参数推导的，这时就可以使用traits技巧来获得类型作为模板函数的返回类型。

比如现在有个模板函数需要接受一个函数迭代器，然后返回其指向的值，那么模板参数是迭代器，函数的返回类型却是其指向值的类型。显然没办法通过模板参数推导来得到迭代器的指向值类型，这时就可以对迭代器使用traits技巧来提取其指向值类型作为函数的返回类型。

如果对迭代器类型不太熟悉还不太懂那也没关系，后续文章还会详细介绍，先接着往下看。

2 POD类型

要说type_traits模板就必须先说POD类型。

POD 是 Plain Old Data 的缩写，是 C++ 定义的一类数据结构概念，比如 int、float 等都是 POD 类型的。Plain 代表它是一个普通类型，Old 代表它是旧的，与 C 语言兼容，那么就可以使用 memcpy() 这种最原始的函数进行操作。两个系统进行交换数据，如果没有办法对数据进行语义检查和解释，那就只能以非常底层的数据形式进行交互，而拥有 POD 特征的类或者结构体通过二进制拷贝后依然能保持数据结构不变。

也就是说，能用 C 的 memcpy() 等函数进行操作的类型就是 POD 类型的数据。

在C++的各标准中对POD类型的有详细定义，从使用中可以概括为标量类型和POD类。

• 标量类型：整型(char、int等等)，浮点型(double、float等等)，枚举类型，指针类型，指向成员指针类型，std::nullptr_t类型。
• POD类：包括满足 trivial 条件和 standard-layout 条件的struct、class、union。
  • 只有默认的构造/析构函数、拷贝/移动函数、拷贝/移动运算符。
  • 不能有虚函数和虚基类。
  • 普通成员有相同的访问级别，如类成员都为public或都为private或都为protected。
  • 第一个成员为自身的数据成员，而不能是由父类定义的数据。
  • 只要有父类，普通成员只能在其中一个类中，不可分散。

可以使用std::is_pod<classname>::value的值来判断一个类是否为POD类型。

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

#include <iostream>

using namespace std;
//满足POD类型条件
class A1{
    int a;
    double b;
};
// A2继承了A1但父类子类同时有成员且A2的第一个成员为A1类型，故而不是pod类型
class A2:public A1{
    A1 num1;
    double num2;
};

int main(){
    A1 a1;
    A2 a2;
    cout << std::is_pod<A1>::value << endl;
    cout << std::is_pod<A2>::value << endl;
    return 0;
}

那么知道了一个对象或变量是不是POD类型有什么用呢？答案是以此提高程序运行效率。

假如事先知道了某函数的操作对象是POD类型，那么我们就可以针对其特性，使用底层的memcpy()、memove()等C函数对其操作，而不需要调用类似constructor，destructor等函数。这在大规模而操作频繁的程序中有显著的效率提升。

3 type_traits 模板

type_traits在SGT STL 2.91版本中命名为__type_traits，因为当时并未加入STL标准，属于SGI的“私房菜”，故而命名前有两个下划线，这里为了方便描述就去掉了开头的下划线。

从前文已经得知traits编程技巧的作用是为了取得对象或变量的某种特性，而目的则是为了根据特性作出相应优化而提升效率。而这里的type_traits模板所能取得特性就是是否具有所谓“平凡”（trivial）的默认构造函数、拷贝构造函数、赋值运算符、析构函数，以及是否是POD类型。如果具有上述的性质，那么在进行相应的构造、拷贝、赋值、析构的时候就可以使用malloc()、memcpy()这些C函数直接对内存进行操作，以获得更高的效率。

那么如何表示其是否具有上述性质呢？用true和false这样的布尔值？当然可以，但这样的话，在使用的时候，就不方便根据不同特性来对实际函数进行重载了，因为都是bool类型嘛。

根据SGI STL的方案，我们可以使用两个不含有任何成员的类来区分：

1
2

struct true_type { };
struct false_type { };

不含有任何成员，就意味着开销最低。

然后使用实现基本的type_traits模板：

1
2
3
4
5
6
7
8

template<typename type>
struct type_traits {
    using has_trivial_default_constructor   = _false_type;
    using has_trivial_copy_constructtor     = _false_type;
    using has_trivial_assignment_operator   = _false_type;
    using has_trivial_destructor            = _false_type;
    using is_POD_type                       = _false_type;
};

在这个模板里我们先将所有性质都设为false_type，也就是说给所有使用该模板的类型一个最保守的值，接着使用模板特化的方法，为已知为true_type的类型提供特化版本。例如：

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

// 针对各种算术整型的特化版本
template<>
struct type_traits<bool> {
    using has_trivial_default_constructor   = _true_type;
    using has_trivial_copy_constructtor     = _true_type;
    using has_trivial_assignment_operator   = _true_type;
    using has_trivial_destructor            = _true_type;
    using is_POD_type                       = _true_type;
};

template<>
struct type_traits<char> {
    using has_trivial_default_constructor   = _true_type;
    using has_trivial_copy_constructtor     = _true_type;
    using has_trivial_assignment_operator   = _true_type;
    using has_trivial_destructor            = _true_type;
    using is_POD_type                       = _true_type;
};

...

指针类型当然也具有上述性质，但是对于指针就没必要一个个特化了，只需要使用偏特化就可以覆盖各种类型的指针了：

1
2
3
4
5
6
7
8
9

// 针对指针的偏特化版本
template<typename type>
struct type_traits<type*> {
    using has_trivial_default_constructor   = true_type;
    using has_trivial_copy_constructtor     = true_type;
    using has_trivial_assignment_operator   = true_type;
    using has_trivial_destructor            = true_type;
    using is_POD_type                       = true_type;
};

4 一点小扩展–is_const的实现

C++11的标准中加入了decltype关键字，使得许多原本需要使用traits技巧来取得对象类型的地方可以直接使用decltype()，避免了各种弯弯绕绕。比如在第一节迭代器的例子里。

但traits技巧依然在许多地方很有用，事实上即使是最新的各版本STL实现，依然有着广泛使用。比如我们可以使用类似技巧来实现is_const，其作用是判断一个类型是否是const的。实现如下

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

// 一个辅助实现 true_type 和 false_type 的类
template<typename T, T v>
struct intergral_constant {
    using value_type = T;
    using type       = intergral_constant<T, v>;

    static constexpr T value = v;
};

using true_type = intergral_constant<bool, true>;
using false_type = intergral_constant<bool, false>;

// 接受普通类型时继承 false_type ,此时其静态成员 value 为 false
template<typename T>
struct is_const: public false_type { };

// 偏特化使得接受 const 类型时继承 true_type，此时其静态成员 value 为 true
template<typename T>
struct is_const<const T>: public true_type { };

5 附录

本部分代码已上传到 github，代码链接在这里。

• TinySTL实现项目（二）：空间分配器allocator与全局construct、destroy
• TinySTL实现项目（三）：具有SGI特色的两级分配器alloc模板类
• TinySTL实现项目（四）：迭代器、反向迭代器及初始化工具
• Linux 系统编程（二）：文件、文件操作函数和相关实例
• Linux 系统编程（一）：C/C++程序编译与gdb调试