SGL STL源码剖析——迭代器
迭代器
在我们使用STL容器的时候，迭代器是非常常见的，STL将容器和算法分开，彼此独立，然后通过迭代器相互关联。迭代器不是脱离容器存在的，每一种STL容器都提供专属迭代器，比如我们经常使用的find算法，
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> array = {1, 2, 3, 4, 5, 6};
vector<int>::iterator iter = find(array.begin(), array.end(), 3);
if(iter != array.end())
{
cout << "success"<<endl;
}
return 0;
}
算法要使用迭代器，而迭代器依附于容器，换句话说，迭代器要通过容器来定义。原书中有讨论将迭代器独立的实现，但是这种实现会暴露容器的细节，并不合适。这里我们不多看，直接看源码中迭代器的实现方式。
迭代器的型别
如前面所述，迭代器依赖于容器，在算法中可能要获取迭代器的型别才能实现细节。但是C++并不支持返回类型，比如sizeof可以返回类型的大小，typeid也只是获得型别名称，但是这个名称不能直接拿来做变量声明。所以我们第一个要弄懂的就是如果进行类型推断。
做法其实很简单，利用模板的参数推导机制。
我们在写函数模板的时候是不知道类型的，比如，
template<class I, class T>
void func_detail(I iter, T t)
{
T tmp;
}
template<class I>
void func(I iter)
{
func_detail(iter, *iter);
}
int main()
{
int i;
func(&i);
}
这里的模板函数func，使用了模板参数I iter。注意这里我们只知道迭代器的类型是I，但是我们并不知道迭代器所指对象的型别，所以我们再封装一个func_detail，把T t作为模板参数，然后传入解引用的迭代器，这样编译器就会推断出类型T。
Traits的作用
前面说了利用模板参数进行类型推导，我们推断的是迭代器所指对象的类型，称为value type。如果说我们要用value type作为函数返回值，那么前面的做法就不行了。这时候我们要用到内嵌类型，这在所有的容器中都用定义，
template<class T>
struct MyIter
{
typedef T value_type; //用这个内嵌类型把T的类型暴露出去
T* ptr;
MyIter(T* p = 0):ptr(p){}
T& operator* () const{return *ptr;}
};
template<class I>
typename I::value_type func(I iter)
{
return *iter;
}
int main()
{
MyIter<int> iter(new int (8));
cout << func(iter) <<endl;
}
可以看到，func这个函数要返回迭代器所指对象的类型，所以我们用了一个内嵌类型，因为T是一个模板参数，所以必须要用typename告诉编译器这是一个类型，否则编译不过。
上面这个中做法有什么缺陷呢，如上像上面的那个例子一样，要传入&i作为迭代器参数，那就不行了，&i是int型指针，是一个原生指针，无法为它定义内嵌型别。为此我们需要针对原生指针这个特殊情况作特化处理，这就是template partial specialization
所谓偏特化就是针对部分模板参数进行特化，
template<typename T>
class C{ ... }
// 针对模板参数的特化版本T*
template<typename T>
class C<T*>{ ... }
这样就相当于我们定义了两个模板，如果实例化传入的是原生指针，那就走到下面这个定义，这就是特化。
那这样有什么用呢，其实是为了引出下面这个封装的traits，
template<class I>
struct iterator_traits
{
typedef typename I::value_type value_type;
};
这个模板，如果I是一个class type，有自己的value_type，traits就会萃取这个value_type，如果没有咋办呢，那就再定义一个特化版本的模板，
template<class T>
struct iterator_traits<T*>
{
typedef T value_type;
};
这个特化的版本接受原生指针，比如int *，那它的value_type就是int，这样的话traits也能萃取出value_type。
这样的话，前面那个func就可以写成，
template<class I>
typename iterator_traits<I>::value_type func(I iter)
{
return *iter;
}
这时候我们还漏了一种情况，就是const指针，即指向常数熟对象的指针，由于要作为返回值类型，那肯定不能萃取出一个const的value_type，所以要再设计一个特化版本，
template<class T>
struct iterator_traits<const T*>
{
typedef T value_type;
};
好了，到这里我们就完全明白了iterator_traits这个类型萃取的实现原理了，每一个STL容器都会定义内嵌类型以便traits能正确运作。与迭代器相关的类型不止有所指向对象类型，一共有五种：value_type, difference_type, pointer, reference, iterator catagoly，我们可以先看下vector这个容器的定义，
template <class T, class Alloc = alloc>
class vector
{
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t& size_type;
typedef ptrdiff_t difference_type;
所以，traints要把这5中特性都提取出来，
template<class I>
struct iterator_traits
{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
如前面所述，针对原生指针和const指针，必须要有实现特化版本，
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;
};
迭代器相应的五种型别
value_type
value_type就是迭代器所指对象的类型，前面已经说过，每个STL容器都定义了自己的内嵌类型。
difference_type
difference_type表示两个迭代器之间的距离，比如count算法使用的返回值类型就是difference_type，
template<class I, class T>
typename iterator_traits<I>::difference_type
count(I first, I last, const T& value)
{
typename iterator_traits<I>::difference_type n = 0;
for( ; first != last; ++first)
if(*first == value)
++n;
return n;
}
difference_type的特化版本直接使用ptrdiff_t实现。
reference_type
reference_type就是引用类型
point_type
指针类型
iterator_category
这个类型比较复杂点儿，先来看一下迭代器的分类，
Input Iterator: 只读，迭代器所指的对象不允许外界改变。
Output Iterator: 只写
Forward Iterator: 允许写入型算法在此种迭代器所形成的区间上进行读写操作
Bidirectional Iterator: 可双向移动
Random Access Iterator: 前面几种迭代器只支持++和–的操作，这种则支持算法运算如p + n
上面这五种迭代器除了前面两个并列，剩下的依次从属。
我们举一个例子，看看Random Access Iterato究竟有什么用，
//接受Input Iterator
template<class InputIterator, class Distance>
void advance_II(InputIterator& i, Distance n)
{
while(n--) ++i;
};
template<class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator& i, Distance n)
{
if(n >= 0)
while (n--) ++i;
else
while (n++) --i;
};
template<class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i, Distance n)
{
i += n;
};
//在运行时决定调用哪个版本
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
advance_II(i, n);
}
为了应对多种迭代器类型，我们需要实现多个函数，并且封装一个统一的转调用接口。那么能不能通过重载实现呢，当然不行，因为上面的多个版本都是两个模板参数，模板参数本身都是表示未定的类型，那当然不能重载了。为此，我们需要再追加一个参数。
自然的，我们会想到利用前面说的traits萃取出迭代器的种类。
先定义处5中迭代器类型，
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 {};
继承关系和前面所说的5中迭代器从属关系完全一致。
然后我们先实现多个迭代器类型的内部转调用版本，
template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
while (__n--) ++__i;
}
template <class _ForwardIterator, class _Distance>
inline void __advance(_ForwardIterator& __i, _Distance __n,
_forwardIterator_iterator_tag) {
//转调用
__advance(__i, __n, input_iterator_tag());
}
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
if (__n >= 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag) {
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__i += __n;
}
注意上面每个_advance()的最后一个参数都只是声明类型，不需要参数，因为只是用来重载，函数中并不需要该参数。
然后满在封装一个对外的接口，
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
__STL_REQUIRES(_InputIterator, _InputIterator);
__advance(__i, __n, iterator_category(__i));
}
到这里我们基本上就明白了iterator_category是要干什么，没错，就是根据我们传入的模板参数_InputIterator& __i 返回一个对应的迭代器类型，
template <class _Tp, class _Distance>
inline input_iterator_tag
iterator_category(const input_iterator<_Tp, _Distance>&)
{ return input_iterator_tag(); }
inline output_iterator_tag iterator_category(const output_iterator&)
{ return output_iterator_tag(); }
template <class _Tp, class _Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<_Tp, _Distance>&)
{ return forward_iterator_tag(); }
template <class _Tp, class _Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
{ return bidirectional_iterator_tag(); }
template <class _Tp, class _Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<_Tp, _Distance>&)
{ return random_access_iterator_tag(); }
template <class _Tp>
inline random_access_iterator_tag iterator_category(const _Tp*)
{ return random_access_iterator_tag(); }
iterator_category进行了重载，根据我们传入的_InputIterator& __i的不同，返回不同的_tag对象。等一下，这和书上说的不一样啊，这里好像不需要萃取了，直接根据重载函数就能返回对应对象了。说实话，这里我没看懂。看代码的话，还有一个实现，
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return __iterator_category(__i); }
template <class _Iter>
// 这里其实也是用了模板参数类型推断的方式
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
貌似这个才和树上说的对应，这里根据传入的迭代器类型去实例化traits，这就是iterator_category的作用。这要容器中定义了iterator_category，比如把random_access_iterator_tag typedef为iterator_category，那么上面typedef typename iterator_traits<_Iter>::iterator_category _Category其实就相当于拿到了类名random_access_iterator_tag ，然后_Category()构造就返回了这个类型的对象。
template<class I>
struct iterator_traits
{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
另外注意命名，STL算法规则：以算法所能接受的最低阶迭代器类型，来为其迭代器型别参数命名。
利用迭代器类型的继承关系，也可以消除转调用。如果一个迭代器符合多个类型，那就以最强类型作为归属，也就是子类型。
综上，我们知道了对于迭代器来说，它要解决的问题就是设计推导相应的型别，而迭代器本身是由容器去定义的。
源码部分，我们把这几个萃取放一起来看
// 迭代器的类别
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
//迭代器的difference_type
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)
{
return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}
// 决定某个迭代器的value_type
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}
__type_traits
前面我们学习了iterator_traits这样的traits编程技巧，SGI中额外拓展了__type_traits，这在上一节的空间配置器中其实已经用到过，接下来我们详细来看。iterator_traits是负责萃取迭代器的特性，而__type_traits则是负责萃取型别的特性。比如空间配置器在destroy中使用的型别是否具有non-trivial 的析构函数，其他类似的还有默认构造函数、复制构造函数、拷贝运算符。为什么要这么区分呢，主要是为了效率问题，对于不具备的类型，我们可以通过memcpy这些内存操作提高效率。其实很好理解，比如如果是类中进行了new或者malloc的操作，那自然不能简单拷贝或者析构了。
这个实现其实非常暴力，
首先定义了两个type，一个true和一个false，和前面的iterator_traits一样，我们要用类型做参数推导，所以不能简单的使用bool值
struct __true_type {};
struct __false_type {};
然后是__type_traits的定义，
template <class _Tp>
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;
};
然后针对特化版本，定义值，比如bool类型
__STL_TEMPLATE_NULL struct __type_traits<bool> {
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;
};
举个例子，uninitialized_fill_n()这个函数.
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x)
{
//先利用__VALUE_TYPE萃取出迭代器所指对象类型
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}
template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, _Tp1*)
{
//利用模板参数推断得到类型_Tp1，然后实例化__type_traits得到_Is_POD
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
__uninitialized_fill_aux(__first, __last, __x, _Is_POD());
}
//根据_Is_POD()走到不同的分支
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __true_type)
{
return fill_n(__first, __n, __x);
}
template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __false_type)
{
_ForwardIter __cur = __first;
__STL_TRY {
for ( ; __n > 0; --__n, ++__cur)
_Construct(&*__cur, __x);
return __cur;
}
__STL_UNWIND(_Destroy(__first, __cur));
}
好了，迭代器的学习就到这里了。回顾一下，主要是模板参数类型的推断、traits编程萃取的实现方式特别是iterator_category的定义，最后是__type_traits。