STL下的iterator traits_综合

文章目录

前言
迭代器相应型别（associated types）
模板特化
value_type
difference_type
reference
pointer
iterator_category
- advanced()为例
- 为什么代表迭代器类型的class使用继承
std::iterator 的保证
完整代码重列

前言

迭代器就是所谓泛型指针，《Design Patterns》一书中将迭代器定义为：提供一种方法，使之能依序遍历某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。面向对象设计推崇将算法封装在容器里，而STL采用了泛型思维，将容器和算法分开，彼此独立设计，然后在二者之间架起桥梁。迭代器就是这座桥。
如果你熟悉各种容器和迭代器，你会发现一个问题，似乎迭代器依附于算法——这就意味着迭代器的设计需要提前知道容器的类型。实际上确实是这样，为了保证容器的封装性，我们不妨把迭代器的设计交给容器的设计者来搞。

迭代器相应型别（associated types）

既然算法是为了作用于容器，那么就应该知道容器的某些信息以便于自身完成某些动作。但是与算法直接接触的是迭代器，所以迭代器应该提供自己的某些信息来让算法完成动作。
考虑这样一个问题，如何在一个算法中定义一个迭代器所指对象类型的变量呢？这似乎有点难办，C++98(现在似乎可以)并没有提供typeof()这样的运算符。
解决方法是利用模板的参数推导。

template<class I, class T>
void _Fun(I _iterator, T){
    T tmp;  // 这样就定义了一个 *_iterator类型的变量， 这里为int//... 这里做原来Fun应该做的动作
}
template<class I>
void Fun(I _iterator){
    _Fun(_iterator, *_iterator);  // *_iterator 的类型就是迭代器所指对象的类型 ,这里为int
}int i = 0;
Fun(&i);

算法Fun对外放出的接口接受一个迭代器，然后调用子函数_Fun的同时传入一个*iterator类型的对象，在子函数中推导出类型T，这就解决了问题。
我们把迭代器所指对象的型别叫做value type，根据经验，常用的迭代器相应型别有5种，接下来为大家逐一介绍。
我们接着来考虑value type的问题。这样难道就可以了吗？但似乎不够全面，万一返回值的类型是value type怎么办？

template<class I>
value_type Fun(I _iterator){
     //像这样，怎么办？return *_iterator; // 返回一个迭代器所指对象的类型
}

模板的参数推导并不能帮助我们推导出返回值的类型，那么怎么办呢？我们可以内嵌型别声明。

#include<iostream>
using namespace std;template<class T>
struct Iter {
    //using value_type = T; C++11的做法typedef T value_type; // 内嵌型别声明T* _ptr; // 迭代器成员变量Iter(T* ptr = nullptr): _ptr(ptr){
    } value_type& operator*() {
     return *_ptr; } 
};template<class I>
typename I::value_type Fun(I _iterator) {
     // 这行必须使用typenamereturn *_iterator;
}int main() {
    int* p = new int(10);cout << Fun(Iter<int>(p));delete p;return 0;
}

最后结果是10.我们使用内嵌类型声明，在迭代器这个类里面先搞定value_type,.然后在算法中就可以直接用域作用符拿到value_type。在Fun函数的返回值中使用了typename，这是为了告诉编译器value_type是一种类型，而非变量或者函数，具体用法请看typename用法
此处不做具体讲解。在C++11中，using关键字可以完全取代typedef，而VS下的STL源码已经使用了using，此处我仍然使用typedef。关于using的新用法可移步这篇博客：C++11 using的各种使用，在此不做讲解。
内嵌声明是个很妙的做法，然而这样就行了吗？有没有什么瑕疵吗？没错， 就是迭代器必须是一个class！如果迭代器不是class，而是一个原生指针怎么办？要知道原生指针天然的是迭代器。如果我们设计的算法不能支持原生指针，那么这太愚蠢了！
这使得我们提出这样一个问题：是否有一种方法能够解决泛化中的某些特化版本呢？
是的，模板特化(template partial specialization)可以完美的解决这个问题。

模板特化

模板特化是指我们可以对一个或是几个模板参数做特殊处理，制造出一个特殊版本，防止这篇博客过于冗余，具体的讲解可以移步我的另外一篇博客。C++模板
有了模板特化之后，我们就可以专门给原生指针特化一个版本出来。

template<class T>
struct iterator_traits{
     // 这个类用于萃取迭代器的特性(trait)typedef typename T::value_type value_type;// ...
};
template<T>
struct iterator_traits<T*>{
     // 如果是指针则进入这个特化版本typedef T value_type;// ...
};

我们可以到，如果迭代器是一个类，则iterator_traits（萃取机，或者叫榨汁机）这个类会进入泛化版本去帮你找到value_type,如果是原生指针，就进入关于原生指针的特化版本找到value_type。上面的Fun函数可以做如下改写

template<class I>
typename iterator_traits<I>::value_type Fun(I _iterator) {
     // 这行必须使用typenamereturn *_iterator;}

这样已经很好了，解决了原生指针无法萃取出value_type的问题，但是考虑这样的萃取，

iterator_traits<const T*>::value_type

我们获得的是value_type是const T，而非T，这是我们想要的吗？如果是const的那就无法修改，一个无法修改的变量有什么用呢？所以我们应该设法令const T*的value_type也是T，这也很好解决，再来一个特化版本就行，

template<class T>
struct iterator_traits<const T*>{
     //即使是const指针，value_type也是可修改的typedef T value_type;//...
};

iterator_traits

traits扮演的角色就是一个萃取机，将迭代器的特性萃取出来，所有的STL迭代器都必须用内嵌型别的方法给出对应的迭代器型别以供不时只需。如果你想融入STL大家族，你就要遵守STL的规则。上文已经说过迭代器相应的型别大抵有5种，下面为大家介绍。

value_type

value_type就是迭代器指向的对象的类型，具体说明上文已经给出，不再赘述。

difference_type

difference_type用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。STL中提供了count算法，返回值的类型就必须是difference_type。

//count函数在[begin(), end())中寻找迭代器所指对象等于val的个数并返回
template <class InputIterator, class T>typename iterator_traits<InputIterator>::difference_type  //函数的返回值count (InputIterator first, InputIterator last, const T& val){
    typename iterator_traits<InputIterator>::difference_type ret = 0;while (first!=last) {
    if (*first == val) ++ret;++first;}return ret;
}

但是一个疑问自然而然的抛出：count算法中的ret既然是表示个数，为什么不直接使用int？（这点我也不明白）
对于原生指针和const指针的特化版本，SGL使用C++内建的ptrdiff_t（定义在头文件中）作为原生指针的difference_type.

template<class I>
struct iterator_traits{
    typedef I::difference_type difference_type;//... 
};
template<class T>
struct iterator_traits<T*>{
     //原生指针的特化typedef ptrdiff_t difference_type;//...
};
template<class T>
struct iterator_traits<const T*>{
     // const 指针的特化typedef ptrdiff_t difference_type;//...
};

任何时候你需要迭代器的difference_type时，你可以这样写

typename iterator_traits<I>::difference_type

reference

引用类型，定义的是迭代器所指对象的引用。如果迭代器是const的，那么引用型别也应该是const的。
与下一种型别一并展示。

pointer

pointer表示传回一个左值，表示迭代器所指对象的地址。如果迭代器是const的，那么指针型别也应该是const的。

template<class I>
struct iterator_traits{
    typedef I::reference reference;typedef I::pointer pointer;//... 
};
template<class T>
struct iterator_traits<T*>{
     //原生指针的特化typedef T& reference;typedef T* pointer;//...
};
template<class T>
struct iterator_traits<const T*>{
     // const 指针的特化typedef const T& reference;typedef const T* pointer;//...
};

iterator_category

迭代器的相应型别之迭代器类型，要想知道迭代器的这个相应型别的作用，首先应该讨论迭代器的分类。
根据移动特性与施行操作，迭代器可以分为5类：

Input iterator （这种迭代器很少见。。。）
这种迭代器所指的对象，不允许外界改变。只读（read only）。
Output iterator （这种迭代器我没见过。。。）
只写
Forward iterator
允许“写入型”算法在此迭代器所形成的区间上进行读写操作。其实也就是我们常说的单向迭代器。
Bidirectional iterator
双向迭代器
Random Access iterator
随机迭代器，支持随机访问。
这些迭代器的关系不是C++的继承关系，而是所谓concept和refinement的关系——即下面的迭代器的功能是上面迭代器的拓展。

设计算法的时候，如果能知道迭代器的类型，在同一种算法里根据不同的迭代器类型设计不同的处理方式，就可能提高效率。假设有个算法接受Forward iterator，你传给它Random Access iterator，它也能接受，因为Random Access iterator本身就是一个Forward iterator。但是这并不意味这效率最好！

advanced()为例

我们用advanced()这个函数举例子。这个函数有两个参数，迭代器p和数值n。函数内部将p叠加n次。也就是p前进n个距离。以下给出三个版本，一份是Input Iterator，一份是Bidirectional iterator，一份供Random Access iterator使用。

template <class InputIterator, class Distance>void advance_II (InputIterator& it, Distance n){
    while(n--) ++it; // 单向迭代器，只能++}template <class BidirectionalIterator, class Distance>void advance_BI (BidirectionalIterator& it, Distance n){
    if(n >= 0){
    while(n--) ++it; // n > 0, 向前走}else{
    while(n++) --it; // n < 0, 向后走}}template <class RandomAccessIterator, class Distance>void advance_II (RandomAccessIterator& it, Distance n){
    it += n; //随机迭代器，直接跳跃}

当你使用advance时，你应该用哪份代码呢？如果你使用前两种，那么Random Access iterator迭代器传过来，原本O(1)的时间复杂度变成了O(N)的时间复杂度。如果你使用第三种，那么前两种迭代器传过来就无法实现——因为前两者都不支持+=操作。我们需要让三者合一，然后让编译器来分配最好方法。实际上在C++中，我们经常将某些代码合并。下面是一种实现：

template<class InputIterator, class Distance>
void advance(InputIterator& it, Distance n){
    if(is_random_access_iterator(it)){
     // 这个函数没有设计，表示如果是随机迭代器返回trueadvance_RI(it, n);}else if(is_bidirectional_iterator(it)){
     //这个函数也没有设计，假设如果是双向迭代器，返回trueadvance_BI(it, n);}else{
    advance_II(it, n);}
}

但是这有一个问题：只有在代码运行起来的时候才能知道应该使用哪个版本。有没有一种方法，能够在编译的时候就解决使用哪个版本呢？我们利用函数重载来实现这个目标。
要想实现函数重载，我们需要第三个确定类型的参数——三个版本的advance前两个参数都是模板参数，无法形成函数重载。
那么，第三个参数如何选取呢？没错，如果traits能够直接萃取出迭代器的类型，把它作为第三个参数，岂不妙哉？首先，这个相应型别一定得是一个class type，不能是数值号码之类的东西，因为编译器需要这个进行函数重载。下面是5种classes，代表迭代器的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个类由于只是用来标识迭代器的分类，所以不需要任何成员。至于为什么需要继承，下面再说。
于是advance的代码可做如下修改：

template <class InputIterator, class Distance>inline void _advance (InputIterator& it, Distance n, input_iterator_tag){
    while(n--) ++it; // 单向迭代器，只能++}template <class ForwardIterator, class Distance>inline void _advance (ForwardIterator& it, Distance n, Forward_iterator_tag){
    _advance (it, n, input_iterator_tag()); //调用input_iterator版本}template <class BidirectionalIterator, class Distance>inline void _advance (BidirectionalIterator& it, Distance n, bidirectional_iterator_tag){
    if(n >= 0){
    while(n--) ++it; // n > 0, 向前走}else{
    while(n++) --it; // n < 0, 向后走}}template <class RandomAccessIterator, class Distance>inline void _advance (RandomAccessIterator& it, Distance n, random_access_iterator_tag){
    it += n; //随机迭代器，直接跳跃}

以上就是advance的四个子函数。这四个子函数的第三个参数类型没有给出参数，因为我们只需要它来进行函数重载，并不需要这个类型在函数体内起作用。现在要做的就是再封装一层接口去调用这些子函数。但是我们需要迭代器的类型，这自然交给萃取机去搞定。

template <class InputIterator, class Distance>
inline void advance_II (InputIterator& it, Distance n){
    _advance(it, n, iterator_traits<InputIterator>::iterator_category());}

我们用iterator_traits萃取出迭代器的类型，在类型的后面加上一对()表示一个匿名对象。根据这个对象，编译器决定调用哪个版本的_advance。
讲到这，我们应该再添加一种类型型别， iterator_category.

template<I>
struct iterator_traits{
    typedef typename I::iterator_category iterator_category;//...
};template<T>
struct iterator_traits<T*>{
     //原生指针是随机迭代器typedef random_access_iterator_tag iterator_category;//...
};
template<T>
struct iterator_traits<const T*>{
     // 指针是随机迭代器typedef random_access_iterator_tag iterator_category;//...
};

任何一个迭代器，它的类型应该是所有类型中最强化的那一个。例如：int* 是随机迭代器，也是双向和单向迭代器，我们分类的时候，应该把它分在随机迭代器一类。
但是你是否注意到STL算法的命名规则，例如advance对外的接口参数是InputIterator，算法以能接受的最低级的迭代器类型作为参数类型。

为什么代表迭代器类型的class使用继承

前面你是否注意这样的一部分，我将它拷贝了过来。

template <class InputIterator, class Distance>inline void _advance (InputIterator& it, Distance n, input_iterator_tag){
    while(n--) ++it; // 单向迭代器，只能++}template <class ForwardIterator, class Distance>inline void _advance (ForwardIterator& it, Distance n, Forward_iterator_tag){
    _advance (it, n, input_iterator_tag()); //调用input_iterator版本}

ForwardIterator版本的_advance实际上又去调用了InputIterator版本的_advance。这说明了将迭代器从input型增强到forward型对于这个算法的写法没有任何帮助。虽然我们复用了代码，但是好像还有点累赘。我们看下面的栗子：

// 测试继承对于传递调用
#include <iostream>
using namespace std;
struct GrandFather{
     }; // 这个可以表示input_iterator
struct Father : public GrandFather {
     }; // 表示 forward_iterator
struct Son : public Father {
     }; // 表示 bidirectional_iteratortemplate<class T>
void Fun(const T& t, GrandFather) {
     cout << "GrandFather" << endl; }template<class T>
void Fun(const T&, Son) {
     cout << "Son" << endl; }int main(int argc, char const* argv[]) {
    int* p;Fun(p, GrandFather()); //调用第三个参数为GrandFather的FunFun(p, Father()); //传递调用 GrandFatherFun(p, Son()); //类型完全符合Son，不会脑抽去调用父类的Fun。return 0;
}

最终结果是GrandFather，GrandFather，Son。我没有写关于Father参数的重载。但是第二次调用Fun函数仍然成功。因为编译器没有找到关于Father的Fun函数，于是就传递调用了GrandFather版本的。另外，如果参数完全符合，也不会脑子抽了去调用父类的。由于迭代器之间存在继承关系，所以"传递调用(forwarding)"这一行为模式自然也存在，换句话说，当传递过来的迭代器类型没有匹配时，编译器回去查找继承过来的父类，看能否匹配，而这完全不需要我们自己去完成调用。所以forward iterator版本的_advance根本不需要写。

std::iterator 的保证

每一个自已实现的iterator都应该拥有上面5种迭代器相关型别。这是STL库的规定。但是谁也不能保证一定不会忘记写，毕竟5种还是比较多的(雀氏多)，而且它们的名字都一样，引起大量代码重复。如果有人帮我们写好那就不错了。没想到吧，STL连这一层都想到了，它专门提供了一个类，如果每个新的迭代器都能继承这个类，那么就万无一失了。

template< class Category,class T,class Difference_type = ptrdiff_t,class Pointer = T*;class Reference = T&;
struct iterator{
    
typedef Category 	        iterator_category;
typedef T	                value_type;
typedef Difference_type     difference_type;
typedef Pointer             pointer;
typedef Reference           reference;
};

这个类没有成员，只是单纯的typedef，所以继承它不会有多余的开销。而且后三个模板参数都有缺省值，不需要传，只需要传入前两个参数即可。
也就是说，我们设计的迭代器类可以这样搞，

template<class T>
struct MyIterator : public iterator<myIterator_category, T> {
    // ...
}

完整代码重列

前面为了讲述，将代码分开表述，下面给出完整代码，只做少数讲解。

// 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 {
     };//为避免遗漏 和 减少不必要的重复 ，新的迭代器最好继承这个类
template< class Category,class T,class Difference_type = ptrdiff_t,class Pointer = T*;class Reference = T&;
struct iterator{
    
typedef Category 	        iterator_category;
typedef T	                value_type;
typedef Difference_type     difference_type;
typedef Pointer             pointer;
typedef Reference           reference;
};// traits 的完整代码
template<class Iterator>
struct iterator_traits{
    
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type        value_type;
typedef typename Iterator::difference_type   difference_type;
typedef typename Iterator::pointer           pointer;
typedef typename Iterator::reference         reference;
};
// 原生指针设计的特化版本
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指针的特化
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 cosnt T*                    pointer;
typedef const T&                    reference;
};

本文主要参考：
侯捷老师《STL源码剖析》。
(全文完)