STL源码剖析(迭代器)

在STL中，容器跟算法是分开设计的，算法是通过迭代器来对容器进行操作的。

在算法运用迭代器的时候，可能会用到其相应的型别，例如返回值为容器中元素的型别，又或者说根据迭代器的类型来选择更好的算法等等。

为了实现这一点，还有为了兼容内置型别的迭代器(vector迭代器直接使用原生pointer)，STL使用了traits技法，用于提取迭代器的特性(相应的型别)。

1.首先在iterator中typedef相应的型别

 1 // 这是迭代器的基类 所有迭代器必须定义这5种型别
 2 template<class Category, class T, class Distance = ptrdiff_t,
 3 class Pointer = T*, class Reference = T&>
 4 struct iterator {
 5     typedef Category iterator_category;
 6     typedef T value_type;
 7     typedef Distance difference_type;
 8     typedef Pointer pointer;
 9     typedef Reference reference;
10 };

View Code

2.定义萃取器iter_traits

1 // 以迭代器为模板参数，用于萃取相应的型别
2 template <class Iterator>
3 struct iter_traits {
4     typedef typename Iterator::iterator_category iterator_category;
5     typedef typename Iterator::value_type value_type;
6     typedef typename Iterator::difference_type difference_type;
7     typedef typename Iterator::pointer pointer;
8     typedef typename Iterator::reference reference;
9 };

View Code

3.定义相应的偏特化版本(这就是为什么要使用iter_traits封装多一层)，因为内置型别的迭代器并不是class，不能定义相应的型别。

 1 // 原生指针的偏特化版
 2 template <class T>
 3 struct iter_traits<T*> {
 4     typedef typename random_access_iter_tag iterator_category;
 5     typedef typename T value_type;
 6     typedef typename ptrdiff_t difference_type;
 7     typedef typename T* pointer;
 8     typedef typename T& reference;
 9 };
10 
11 // 原生const的偏特化版
12 template <class T>
13 struct iter_traits<const T*> {
14     typedef typename random_access_iter_tag iterator_category;
15     typedef typename T value_type;
16     typedef typename ptrdiff_t difference_type;
17     typedef typename const T* pointer;
18     typedef typename const T& reference;
19 };

View Code

4.5种迭代器类型，只是一个标志，用于根据萃取出来的iterator_category来选择相应的算法。

1 struct input_iter_tag {};
2 struct output_iter_tag {};
3 struct forward_iter_tag : public input_iter_tag {};
4 struct bidirectional_iter_tag : public forward_iter_tag {};
5 struct random_access_iter_tag  : public bidirectional_iter_tag {};

View Code

下面是distance()的实现，展示了怎么使用traits萃取相应的型别。

 1 // input迭代器只支持operator++
 2 template<class InputIterator>
 3 inline typename iter_traits<InputIterator>::difference_type
 4 __distance(InputIterator first, InputIterator last, input_iter_tag)
 5 {
 6     iter_traits<InputIterator>::difference_type n = 0;
 7     while (first != last)
 8     {
 9         first++;
10         n++;
11     }
12     return n;
13 }
14 
15 // random access迭代器支持迭代器之间的加减法
16 template<class RandomAccessIterator>
17 inline typename iter_traits<RandomAccessIterator>::difference_type
18 __distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iter_tag)
19 {
20     return last - first;
21 }
22 
23 // 根据迭代器的iterator_category来调用适合的版本
24 template<class Iterator>
25 inline typename iter_traits<Iterator>::difference_type
26 distance(Iterator first, Iterator last)
27 {
28     return __distance(first, last, iter_traits<Iterator>::iterator_category());
29 }

View Code

STL的__type_traits也是使用traits技法，它可以萃取一个class是否有不重要的构造函数、是否为POD类型等等。

 1 // __type_traits也是运用traits技术
 2 struct __true_type {};
 3 struct __false_type {};
 4 
 5 template <class type>
 6 struct __type_traits {
 7     // 默认为false  可以实现自己的偏特化版本
 8     // 内置类型的偏特化版本定义在stl_config.h中  都是__true_type
 9     typedef __false_type    has_trivial_default_constructor;
10     typedef __false_type    has_trivial_copy_constructor;
11     typedef __false_type    has_trivial_assignment_operator;
12     typedef __false_type    has_trivial_destructor;
13     typedef __false_type    is_POD_type;
14 };

View Code

自定义的类型可以定义相应的偏特化版本，例如定义is_POD_type为__true_type，STL会在元素析构的时候只进行内存回收，而不调用析构函数以用来提高效率。

内存基本处理工具

STL定义了五个全局函数，作用于未初始化空间上，同样的它们也是使用了traits技法。

1.construct()跟destroy()，它们定义在stl_construct.h中

2.uninitialized_copy()、uninitialized_fill()、uninitialized_fill_n()，它们定义在stl_uninitialized中