前言

迭代器（iterators）是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。《Designt Patterns》一书提供有 23 个设计模式（design patterns）的完整描述，其中iterator 模式定义如下：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。
不论是泛型思维或 STL 的实际运用，迭代器（iterators）都扮演着重要的角色。STL 的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在-起。容器和算法的泛型化，从技术角度来看并不困难，C++的class templates 和 function templates 可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。
———— 《STL源码剖析》侯捷

本篇博客将会讲解 STL 中的 type_traits 与 iterator 组件完整的实现。

__type_traits

iterator_traits 负责萃取迭代器的特性，__type_traits 则负责萃取型别（type）的特性。此处我们所关注的型别特性是指:这个型别是否具备 non-trivialdefalt ctor？是否具备 non-trivial copy ctor？是否具备 non-trivial assignment operator？是否具备 non-trivial dtor？如果答案是否定的，我们在对这个型别进行构造、析构、拷贝．赋值等操作时，就可以采用最有效率的措施（例如根本不调用身居高位，不谋实事的那些 constructor，destructor），而采用内存直接处理操作如 malloc ()、memncpy() 等等，获得最高效率。这对于大规模而操作频繁的容器，有着显著的效率提升。

__type_traits 提供了一种机制，允许针对不同的型别属性（type attributes），在编译时期完成函数派送决定（ functiondispatch）。这对于撰写 template 很有帮助，例如，当我们准备对一个 “元素型别未知” 的数组执行 copy 操作时,如果我们能事先知道其元素型别是否有一个 trivial copy constructor ，便能够帮助我们决定是否可使用快速的 memcpy() 或 memnove ()。

根据 iterator_traits 得来的经验，我们希望，程序之中可以这样运用 __type_traits<T>，T 代表任意型别:

1
2
3
4
5
__type_traits<T>::has_trivial_default_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type  // POD : Plain old Data

  • POD 型别

    POD是 C++ 定义的一类数据结构概念，比如 int、float 等都是 POD 类型的。

    Plain 代表它是一个普通类型，Old 代表它是旧的，与几十年前的 C 语言兼容，那么就意味着可以使用 memcpy() 这种最原始的函数进行操作。

    两个系统进行交换数据，如果没有办法对数据进行语义检查和解释，那就只能以非常底层的数据形式进行交互，而拥有 POD 特征的类或者结构体通过二进制拷贝后依然能保持数据结构不变。

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

1
2
struct __true_type {};
struct __false_type {};

这两个空白 classes 没有任何成员，不会带来额外负担，却又能够标示真假，满足我们所需。

在 TinySTL 中，标识真假的两个结构体这样实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// helper struct
// 定义具有 true / false 性质的对象，详见 STL源码剖析 P.104

template <class T, T v>
struct m_integral_constant {
    // 可通过 value 访问具有 true / false 性质的值
    static constexpr T value = v;
};

template <bool b>
using m_bool_constant = m_integral_constant<bool, b>;

typedef m_bool_constant<true>  m_true_type;
typedef m_bool_constant<false> m_false_type;

值得注意的是，在 SGI-STL 中，为了安全性，__type_traits 采用了最保守的做法，即对于 C++ 所有的基本型别，如 char, unsignedchar, int, float 等，__type_traits 中每一个成员的值都是 __true_type，即表示这些型别都可以通过最快速的方式（如 memcpy）来进行拷贝或赋值的操作。但用户的自定义类的所有特性都会被定义为 __false_type，即针对用户的自定义类，采取最保守的拷贝、赋值、析构等操作。

在 TinySTL 中，并没有为每个类型都定义一份 __type_traits 而是直接使用了 std 中的一些功能如std::is_trivially_copy_assignable 等（之所以这样写主要是因为原作者就是这样写的而且确实能省很多代码）。

iterator 完整实现

重要部分讲解

下面的结构体用于判断某个类型是否为迭代器类型，即检查类型 T 是否具有 iterator_category 内部类型。

1
2
3
4
5
6
7
8
9
template <class T>
struct has_iterator_cat {
    private:
        struct two { char a; char b; };
        template <class U> static two test(...);
        template <class U> static char test(typename U::iterator_category* = 0);
    public:
        static const bool value = sizeof(test<T>(0)) == sizeof(char);
};

在该结构体内部，定义了一个私有的嵌套结构体 two，它包含两个 char 类型的成员变量。然后，定义了两个重载的 test 函数模板，一个接受任意类型 U 的参数（使用可变参数模板），另一个接受参数类型为 typename U::iterator_category* 的参数。

在 test 函数模板的实现中，第一个重载的函数使用 ... 接受任意类型的参数，并返回 two 类型。第二个重载的函数使用了 SFINAE 技术，它接受一个指向 U::iterator_category 类型的指针参数，并返回 char 类型。这意味着，当类型 T 存在名为 iterator_category 的内部类型时，第二个重载的函数会匹配，返回 char 类型；否则，第一个重载的函数会匹配，返回 two 类型。

最后，在 has_iterator_cat 结构体中定义了一个静态常量 value，它通过比较 sizeof(test<T>(0)) 和 sizeof(char) 的大小来确定 T 是否具有 iterator_category 内部类型。如果两者的大小相等，则表示 T 具有 iterator_category，value 被设为 true；否则，表示 T 不具有 iterator_category，value 被设为 false。

通过使用 has_iterator_cat 结构体和其静态常量 value，可以在编译时检查类型 T 是否具有 iterator_category 内部类型。

SFINAE 是 “Substitution Failure Is Not An Error” 的缩写，即 “替换失败不是错误”。SFINAE 是 C++ 中的一种模板元编程技术，它允许根据类型推导和模板参数推导的失败来选择重载函数或模板的特定实例。在模板实例化过程中，如果发生了无法匹配的情况，不会引发编译错误，而是将该实例化候选项从候选项集中排除。SFINAE 的核心思想是，当在模板实例化过程中遇到了编译错误（例如，找不到某个成员、推导失败等），编译器将忽略该错误，而不会导致整个编译失败。这样，编译器会继续查找其他可行的候选项，并选择可行的候选项进行实例化。SFINAE 常常与模板特化、函数重载、模板参数推导和类型推导一起使用，通过在编译时根据条件选择特定的实例，达到编写更加通用和灵活的代码的目的。

完整实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#ifndef TINYSTL_ITERATOR_H_
#define TINYSTL_ITERATOR_H_

// 这个头文件用于迭代器设计，包含了一些模板结构体与全局函数，

#include <cstddef>  // ptrdiff_t, size_t
#include "type_traits.h"

namespace tinystl {

// 五种迭代器类型
struct input_iterator_tag {};  // 只读
struct output_iterator_tag {};  // 只写
struct forward_iterator_tag : public input_iterator_tag {};  // 可读写
struct bidirectional_iterator_tag : public forward_iterator_tag {};  // 双向
struct random_access_iterator_tag : public bidirectional_iterator_tag {};  // 随机访问

/// @brief iterator 模板结构体，如果每个新设计的迭代器都继承自它，就可保证符合 STL 规范
/// @tparam Category  迭代器类型（必须提供）
/// @tparam T         迭代器所指对象的类型（必须提供）
/// @tparam Distance  ptrdiff_t（默认）
/// @tparam Pointer   T*（默认）
/// @tparam Reference T&（默认）
template <class Category, class T, class Distance = ptrdiff_t, 
    class Pointer = T*, class Reference = T&>
struct iterator {
    typedef Category    iterator_category;  // 迭代器类型
    typedef T           value_type;         // 迭代器所指对象的类型
    typedef Distance    difference_type;    // 迭代器之间的距离类型
    typedef Pointer     pointer;            // 指向迭代器所指对象的指针类型
    typedef Reference   reference;          // 迭代器所指对象的引用类型
};

// iterator traits

// =========================================== traits =========================================== //
// 这部分的实现太精彩了

template <class T>
struct has_iterator_cat {
    private:
        struct two { char a; char b; };
        template <class U> static two test(...);
        template <class U> static char test(typename U::iterator_category* = 0);
    public:
        static const bool value = sizeof(test<T>(0)) == sizeof(char);
};

template <class Iterator, bool>
struct iterator_traits_impl {};

// `iterator_traits`结构体就是使用`typename`对参数类型的提取(萃取), 
// 并且对参数类型在进行一次命名, 看上去对参数类型的使用有了一层间接性.
template <class Iterator>
struct iterator_traits_impl<Iterator, true> {
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::difference_type   difference_type;
};

template <class Iterator, bool>
struct iterator_traits_helper {};

// 判断某个类型的迭代器是否可以转换为输入迭代器或输出迭代器
template <class Iterator>
struct iterator_traits_helper<Iterator, true>
    : public iterator_traits_impl<Iterator,
    std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
    std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value> {};


// 萃取迭代器的特性
// 1. 先利用`has_iterator_cat`判断是否有`iterator_category`这个类型
// 2. 再利用`iterator_traits_helper`判断是否可以转换为输入迭代器或输出迭代器
template <class Iterator>
struct iterator_traits 
  : public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {};



// 针对原生指针(native pointer)而设计的 traits 偏特化版本
template <class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag  iterator_category;  // 原生指针是随机访问迭代器
    typedef T                           value_type;
    typedef ptrdiff_t                   difference_type;
    typedef T*                          pointer;
    typedef T&                          reference;
};

// 针对原生指针(const native pointer)而设计的 traits 偏特化版本
template <class T>
struct iterator_traits<const T*> {
    typedef random_access_iterator_tag  iterator_category;  // 原生指针是随机访问迭代器
    typedef T                           value_type;
    typedef ptrdiff_t                   difference_type;
    typedef const T*                    pointer;
    typedef const T&                    reference;
};

// 如果 T 和 U 能够转换为相同的类型，则继承自 m_true_type
template <class T, class U, bool = has_iterator_cat<iterator_traits<T>>::value>
struct has_iterator_cat_of
  : public m_bool_constant<std::is_convertible<
  typename iterator_traits<T>::iterator_category, U>::value> {};

// 否则继承自 m_false_type
template <class T, class U>
struct has_iterator_cat_of<T, U, false> : public m_false_type {};

// 萃取某种迭代器
template <class Iter>
struct is_input_iterator : public has_iterator_cat_of<Iter, input_iterator_tag> {};

template <class Iter>
struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag> {};

template <class Iter>
struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag> {};

template <class Iter>
struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag> {};

template <class Iter>
struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag> {};

template <class Iterator>
struct is_iterator : public m_bool_constant<is_input_iterator<Iterator>::value ||
    is_output_iterator<Iterator>::value> {};

// ============================================================================================ //


/// @brief 用于获取某个迭代器的 category
template <class Iterator>
typename iterator_traits<Iterator>::iterator_category iterator_category(const Iterator&) {
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();  // 返回默认构造的 category 对象，即迭代器的类别
}

/// @brief 用于获取某个迭代器的 disstance_type
template <class Iterator>
typename iterator_traits<Iterator>::difference_type* distance_type(const Iterator&) {
    // **这里用到了0可以转换成指针的性质, 相当于返回一个空指针, 但是可以通过它们确定不同的参数类型.** 
    return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

/// @brief 用于获取某个迭代器的 value_type
template <class Iterator>
typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) {
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

/*****************************************************************************************/
// distance
// 计算两个迭代器之间的距离
/*****************************************************************************************/

/// @brief distance 的重载版本，用于 input_iterator_tag 类型的迭代器
template <class InputIterator>  // 以算法所能接受的最低阶迭代器类型，来为其迭代器类别参数命名
typename iterator_traits<InputIterator>::difference_type __distance(InputIterator first, 
    InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type n = 0;
    // input_iterator_tag 类型的迭代器只能使用 ++ 操作符
    while (first != last) {
        ++first; ++n;
    }
    return n;
}

/// @brief distance 的重载版本，用于 random_access_iterator_tag 类型的迭代器
template <class RandomAccessIterator>  // 以算法所能接受的最低阶迭代器类型，来为其迭代器类别参数命名
typename iterator_traits<RandomAccessIterator>::difference_type __distance(RandomAccessIterator first, 
    RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;  // 随机访问迭代器可以直接相减
}

/// @brief 计算两个迭代器之间的距离，根据迭代器的类型调用不同的函数
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, 
    InputIterator last) {
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());  // 通过迭代器的类别来调用不同的函数
}


/*****************************************************************************************/
// advance
// 使迭代器前进 n 个距离
/*****************************************************************************************/

/// @brief 使迭代器前进 n 个距离
/// @tparam InputIterator  迭代器类型
/// @tparam Distance     距离类型
/// @param i  迭代器
/// @param n  距离
/// @param    迭代器的类型
template <class InputIterator, class Distance>
void __advance(InputIterator& i, Distance n, input_iterator_tag) {
    while (n--) ++i;
}

template <class BidirectionalIterator, class Distance>
void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++i;
    else while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
    i += n;
}

template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
    __advance(i, n, iterator_category(i));
}


// ====================================== reverse_iterator ====================================== //
// 模板类：reverse_iterator
// 反向的迭代器需要先了解 adaptor 的理念，而且本身并没有什么难点，这里就不放了。

}  // namespace tinystl

#endif  // TINYSTL_ITERATOR_H_

总结

设计适当的相应型别（associated types），是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍力自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员…）。至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以迭代器为对外接口就行。

traits 编程技法大量运用于 STL 中。它利用 “内嵌型别” 的编程技巧与编译器的 template 参数推导功能，增强 C++ 未能提供的关于型别认证方面的能力，弥补 C++ 不为强型别（strong typed）语言的遗憾。