STL_Iterator

发表于 | 分类于
字数统计: 4k | 阅读时长 ≈ 17
伦敦塔桥 -- 英国

STL_Iterator

1. 文件结构

图 1 文件结构

Iterator 的文件结构如上图所示，有两个部分，一个是核心都文件 stl_iterator.h，里面包含了迭代器相关的数据结构，萃取机等关键代码；一个是 typeTraits.h，里面定义了 _type_traits 型别相关声明和定义。

2. 关键代码

2.1 stl_iterator.h

2.1.1 迭代器的型别

在算法中运用迭代器时，很可能会用到其相应型别。最常见的迭代器相应型别有五种：

  • value_type
  • difference_type
  • reference_type
  • pointer_type
  • iterator_category

以 value_type 为例，为了获取它，常用的手法是：利用**函数模板的参数推导机制**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class I, class T>
void func_impl(I iter, T t) {
    T tmp;  // T 就是迭代器所指之物的型别
    // ...
}
template <class I>
inline void func(I iter) {
    func_impl(iter, *iter); // func 的工作全部移往 func_impl
}

int main() {
    int i;
    func(&i);
    // ...
}

该方法以 func() 为对外接口，却把实际操作置于 func_impl() 之中，由于 func_impl() 是一个函数模板，一旦被调用，编译器会自动进行模板参数推导，于是推导出型别 T。

但是如之前描述所述，迭代器的相应型别不只value_type 一种，并非任何情况下都可以利用上述的模板参数推导来取得，所以 STL 引入了 Traits 编程技法。

《STL源码剖析》 – P84 - P85

2.1.2 Traits 编程技法

上文所述的利用模板的形参推导来获得型别的手法，针对返回值就束手无策了，毕竟函数的模板参数推导机制推到的只是参数，无法推导函数的返回值。**声明内嵌型别**成为了解决方案！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别的声明 （nested type）
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
    // .... 
}
// ...
template <class T>
typename I::value_type // 返回类型，必须要加 typename 告诉编译器这是内嵌型别
func(I ite) { return *ite; }
// ...
MyIter<int> ite(new int(8));
cout << func(ite);  // 输出：8

注意：

行:10，必须加关键词 typename，因为 T 是一个模板参数，在被编译器具现化之前，编译器不知道此时 MyIter<T>::value_type 是一个型别或是一个成员变量或者成员数据。而 typename 告诉编译器这是一个型别，才能顺利通过编译。 （嵌套从属名称）

《Effective C++ 3rd》 – 条款42：了解 typename 的双重意义（P204- P207） 嵌套从属名称

然而迭代器除了是一个智能指针类之外，还可以是一个原生的指针，而原生指针不是 class type，无法定义内嵌型别。所以除了上述的解决方案以为，还需要针对原生指针进行特殊化的处理：模板的偏特化。泛化和偏特化对比如下：

1
2
3
4
5
template <typename T>
class C {...}; // 这个泛化版本允许接受 T 为任何型别

template <typename T>
class C<T*> {...} // 这个特化版本仅适用于“T为原生指针”的情况

所以可以使用如下的特化版本来处理原生指针问题。

1
2
3
4
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
}

所以利用萃取机机制可以让外界方便的获取相应的型别。

图 2 萃取机功能

偏特化的一些细节见：《STL源码剖析》 – P86 - P88

2.1.3 五种型别

2.1.3.1 value_type

所谓的 value_type，是指迭代器指向对象的型别。任何一个打算与 STL 算法有完美搭配的类，都应该定义自己的 value_type 内嵌型别，如上文所述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// class type
template <class T>
struct iterator_traits {
    typedef T value_type;
};
// 原生指针
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type; // 这里不用 const 
};

注意：

行:12 处不应该添加 const，因为我们利用这种机制来声明一个暂时的变量，使其型别和迭代器的 value type 相同，而现在，声明一个无法赋值（const）的暂时变量，没有什么用！因此，如果迭代器是个 pointer-to-const，我们应该设法取其 value type 的 non-const 版本。

《STL源码剖析》 – P88

2.1.3.2 difference_type

difference type 用来表示两个迭代器之间的距离，因此也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其容量的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// class type
template <class I>
struct iterator_traits {
    typedef typename I::difference_type difference_type;
};
// 原生指针
template <class T>
struct iterator_traits<T*> {
    typedef ptrdiff_t difference_type;
};
template <class I>
struct iterator_traits<const *T> {
    typedef ptrdiff_t difference_type;
};

注意：

行:9,13：traits 的两个原生指针的特化版本，以 C++ 内建的 ptrdiff_t（定义于 <cstddef> 都文件） 作为原生指针的 difference type。

《STL源码剖析》 – P90

2.1.3.3 pointer_type, reference_type

这两个不常用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// class type
template <class I>
struct iterator_traits {
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};
// 原生指针
template <class T>
struct iterator_traits<T*> {
    typedef T* pointer;
    typedef T& reference;
};
template <class I>
struct iterator_traits<const *T> {
    typedef const T* pointer;
    typedef const T& reference;
};

注意：

行:15,16：于 value_type 不同，此时需要加上 const，此时是指针与引用。

《STL源码剖析》 – P91 - P92

2.1.3.4 iterator_category

根据移动特性与施行操作，迭代器被分为了五类：

  • input Iterator：这种迭代器所指的对象，不允许外界改变。只读（read only）。
  • Output Iterator：唯写（write only）。
  • Forward Iterator：允许”写入型“算法在此种迭代器所形成的区间上进行读写操作。
  • Bidirectional Iterator：可双向移动。支持某些算法逆向走访迭代器区间。
  • Random Access Iterator：前四种迭代器只供应一部分指针算数能力（前三种支持 operator++，第四种再加上 operator–），第五种则涵盖所有指针算数能力，包括 p + n, p - n, p[n], p1 - p2, p1 < p2。

这些迭代器的分类与从属关系如图3所示。

图 3 迭代器的分类与从属关系

《STL源码剖析》 – P92 - P93

根据迭代器的分类的不同，可以为算法提供不同选择。

以 advance() 为例，它可以使用 Input Iterator，Bidirectional Iterator，Random Access Iterator 三种版本。Forward Iterator 与 Input Iterator 完全相同，避免重复。

（迭代器移动代码如下，详细代码见参考资料）

《STL源码剖析》 – P93 - P94

1
2
3
4
5
6
7
8
9
10
11
// Input Iterator           advance_II()
while (n--) ++i;

// Bidirectional Iterator   advance_BI()
if (n >= 0)
    while (n--) ++i;
else
    while (n++) --i;

// Random Access Iterator   advance_RAI()
i += n;

如果选择 advance_II() 则相对于 advance_RAI() 效率极差。如果选择 advance_RAI()，则他无法接受 Input Interator。 所以需要将三者合一，下面是一种做法：

1
2
3
4
5
6
7
8
9
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
    if (is_random_access_iterator(i)) 
        advance_RAI(i, n);
    else if (is_bidirectional_iterator(i)) 
        advance_BI(i, n);
    else if (is_input_iterator(i)) 
        advance_II(i, n);
}

这种做法有一个缺陷：只有在**运行期才能知道使用哪个版本，会影响效率。最好能够在编译期**就选择正确的版本。重载函数机制可以达到这个目标。（模板元编程思想）

《Effective C++ 3rd》 – 条款48：认识 template 元编程 （P233 - P234）

设计考虑如下：将”迭代器类型“相应型别作为 advance() 的第三参数，这个相应型别**一定必须是 class type，不能只是数值号码类的东西，因为编译器依赖它（一个型别）来进行重载决议**。

C++函数调用时的决议：名字查找，重载决议，可访问性检测

所以定义了以下结构体，他们只是个 tag，所以没有任何成员：

1
2
3
4
5
6
// 五种迭代器类型
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 {};

所以__advance()的重载版本表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n, input_iterator_tag) {
    while (n--) ++i;
}

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

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

可以发现模板只提供了两个参数，还需要让 __advance()有能力从获得的迭代器中推导出其类型。这份工作自然而然就交给了 traits。所以上层接口函数可以如下编写。

1
2
3
4
5
template <class InputIterator, class Distance>
inline 
void advance(InputIterator &i, Distance n, random_access_iterator_tag) {
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}

iterator_traits<InputIterator>::iterator_category() 将产生一个临时对象，其型别对于该隶属于前述五个迭代器类型之一。然后，根据这个型别，编译器才决定调用哪个 __advance() 重载函数。

注意：

任何一个迭代器，其类型永远应该落在“该迭代器所隶属之各种类型中最强化的那个”。如上个例子，既是 Random_Access_Iterator，又是 Bidirectional_Iterator，同时也是 Forward_Iterator，而且也是 Input_Iterator，那么，其类型应该归属于 random_access_iterator_tag。

另外可以发现上面代码，模板参数名称取得并不是 RandomAccessIterator，而是 InputIterator，这是一个 STL 算法的命名规则：以算法能接受的最低阶迭代器类型，来为其迭代器型别参数命名。(方便代码阅读)

《STL源码剖析》 – P97

通过五种迭代器类型的结构体可以发现，它们不仅是以 class 定义的迭代器标签，还满足继承关系。

图 4 迭代器类型标签的继承关系

注意：

首先以 class 来定义迭代器的各种分类标签，可以促成重载机制的成功运作（使编译器得以正确执行重载决议）；

其次通过继承，不必再写“单纯只做传递调用”的函数（例如前述的 __advance() 的 ForwordIterator 版本）。因为如果 advance() 传入的迭代器类型是 ForwordIterator，虽然 __advance() 重载版本中没有与之对应的版本，但是通过重载与继承的结合，advance() 会调用 __advance() 的 InputIterator 版本。

《STL源码剖析》 – P97 - P99

最后，为了符合规范，任何迭代器都应该提供这五个内嵌相应的型别，以便于 traits 萃取，STL 提供了一个 iterator class 如下，如果每个新设计的迭代器都继承自它，就可以保证符合 STL 所需之规范：

1
2
3
4
5
6
7
8
9
10
// 后三个提供了固定的默认值
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T *, class Reference = T &>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
};

《STL源码剖析》 – P100

2.1.4 Iterator 总结

2.1.4.1 五种迭代器类型及其继承关系
1
2
3
4
5
6
//五种迭代器类型 
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 {};

《STL源码剖析》 – P95

2.1.4.2 STL 提供的 Iterator class
1
2
3
4
5
6
7
8
9
10
// 后三个提供了固定的默认值
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T *, class Reference = T &>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
};

《STL源码剖析》 – P100

2.1.4.3 traits

**注意**以下 MiniSTL 代码使用 C++11/14 新特性：using 代替 typedef

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
template <class Iterator>
struct iterator_traits {
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
};

//针对raw pointer设计的偏特化版本
template <class T>
struct iterator_traits<T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using reference = T &;
};

//针对 pointer-to-const 设计的偏特化版本
template <class T>
struct iterator_traits<const T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T; 				// 没有 const
    using difference_type = ptrdiff_t;
    using pointer = const T *;  		// 有 const
    using reference = const T &;		// 有 const
};

因为原生指针无法定义内嵌型别，也就因此无法使用 class type 的版本，但 STL 据对必须接受原生指针作为一种迭代器，解决思路是使用原生指针的偏特化版本，如上所示。

《STL源码剖析》 – P86

**注意**以下 MiniSTL 代码同样使用了 C++11/14 新特性：别名模板，提供了一种更加高效的使用方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Iterator>
using iterator_category_t =
    typename iterator_traits<Iterator>::iterator_category;

template <class Iterator>
using value_type_t = typename iterator_traits<Iterator>::value_type;

template <class Iterator>
using difference_type_t = typename iterator_traits<Iterator>::difference_type;

template <class Iterator>
using pointer_t = typename iterator_traits<Iterator>::pointer;

template <class Iterator>
using reference_t = typename iterator_traits<Iterator>::reference;

如果要用迭代器 $I$ 的 value_type 来声明变量 val 两个版本的差异如下：

1
2
iterator_traits<I>::iterator_value val;
value_type_t<I> val;

注意：

可以发现这样更加方便代码的书写，其实并不仅仅只是书写简单的帮助，利用别名模板还能实现 template template parameter。

MiniSTL / Iterator / stl_iterator.h

侯捷C新标准-C11/14_10 Alias Template

侯捷C新标准-C11/14_11 template template parameter

2.1.4.4 advance()，distance()

整组 advance() 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n, input_iterator_tag) {
    while (n--) ++i;
}

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

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

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

整组 distance() 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class InputIterator>
inline difference_type_t<InputIterator> __distance(InputIterator first,
                                                   InputIterator last,
                                                   input_iterator_tag) {
    difference_type_t<InputIterator> n = 0;
    while (first != last) ++first, ++n;
    return n;
}

template <class InputIterator>
inline difference_type_t<InputIterator> __distance(InputIterator first,
                                                   InputIterator last,
                                                   random_access_iterator_tag) {
    return last - first;
}

template <class InputIterator>
inline difference_type_t<InputIterator> distance(InputIterator first,
                                                 InputIterator last) {
    return __distance(first, last, iterator_category_t<InputIterator>());
}

《STL源码剖析》 – P102 - P103

2.1.4.5 迭代器适配器

insert, reverse, stream 见 adapters 章节

2.2 typeTraits.h

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

__type_trait 提供了一种机制，允许针对不同的型别属性，在编译器完成函数派送决定。这对于撰写模板很有帮助。例如，当我们准备对一个“元素型别”未知的数组执行 copy 操作时，如果我们能实现知道其元素是否有一个 trivial copy constructor，便能帮助我们决定是否可以使用快速的 memcpy() 或 memmove()。

2.2.1 部分 _type_traits 定义

默认自定义类型均为 non-POD 类型

1
2
3
4
5
6
7
8
template <class T>
struct _type_traits {
    using has_trivial_default_constructor = _false_type;
    using has_trivial_copy_constructor = _false_type;
    using has_trivial_assignment_operator = _false_type;
    using has_trivial_destructor = _false_type;
    using is_POD_type = _false_type;
};

针对 C++基本型别：bool, char, signed char, unsigned char, short, unsigned short, int unsigned int, long, unsigned long, float, double, long double 提供了特化版本，且每一个成员的值都是 __true_type，表示这些型别都可以采用最快速方式来进行拷贝赋值等操作。

1
2
3
4
5
6
7
8
template <>
struct _type_traits<bool> {  //  bool 可以替换为 char....
    using has_trivial_default_constructor = _true_type;
    using has_trivial_copy_constructor = _true_type;
    using has_trivial_assignment_operator = _true_type;
    using has_trivial_destructor = _true_type;
    using is_POD_type = _true_type;
};

针对原生指针设计 __type_traits 偏特化版本，原生指针亦可被视为一种标量型别

1
2
3
4
5
6
7
8
template <class T>
struct _type_traits<const T *> {
    using has_trivial_default_constructor = _true_type;
    using has_trivial_copy_constructor = _true_type;
    using has_trivial_assignment_operator = _true_type;
    using has_trivial_destructor = _true_type;
    using is_POD_type = _true_type;
};

《STL源码剖析》 – P103 - P111

C++ trivial、non-trivial及POD类型

迭代器配接器内容见： STL_Adapter

3.参考资料

《STL源码剖析》

《Effective C++ 3rd》

C++函数调用时的决议：名字查找，重载决议，可访问性检测

C++ trivial、non-trivial及POD类型

侯捷C新标准-C11/14_10 Alias Template

侯捷C新标准-C11/14_11 template template parameter

STL_Adapter

MiniSTL / Iterator 部分



----------- 本文结束 -----------




0%