开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 第三章迭代器（iterators）概念与traits编程技法 -> 正文阅读

[C++知识库]第三章迭代器（iterators）概念与traits编程技法

迭代器(iterators)是一种抽象的设计概念，其中iterator模式定义如下：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

3.1 迭代器设计思想——STL关键所在

不论是泛型思维或STL的实际运用，迭代器(iterators)都扮演着重要的角色。
STL的中心思想在于：将数据容器(containers)和算法(algorithms)分开，彼此
独立设计，最后再以帖胶着剂将它们撮合在起。
容器和算法的泛型化，从技术角度来看并不困难，C++的class templates和function templates可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。
以下是容器、算法、迭代器(iterator,扮演粘胶角色）的合作展示。以算法find()为例，它接受两个迭代器和个“搜寻目标":

//来自SGI <stl_algo.h> 
template <class InputIterator,class T>
InputIterator find(InputIterator first,InputIterator last,const T& value){
    while(first != last && *fist != value)
        ++first;
    return first;
}

只要给予不同的迭代器，find()便能够对不同的容器进行查找操作：

#include <iostream>
#include<vector>
#include<list>
#include<deque>
#include<algorithm>
using namespace std;

int main()
{
    const int arraySize = 7;
    int ia[arraySize] = {0,1,2,3,4,5,6};

    vector<int> ivect(ia,ia+arraySize);
    list<int> ilist(ia,ia+arraySize);
    deque<int> ideque(ia,ia+arraySize);

    vector<int>::iterator it1 = find(ivect.begin(),ivect.end(),4);
    if(it1 == ivect.end())
        cout<<"4 not found."<<endl;
    else
        cout<<"4 found."<<*it1<<endl;

    list<int>::iterator it2 = find(ilist.begin(),ilist.end(),6);
    if(it2 == ilist.end())
        cout<<"6 not found."<<endl;
              else
              cout<<"6 found"<<*it2<<endl;

    deque<int>::iterator it3=find(ideque.begin(),ideque.end(),8);
    if(it3 == ideque.end())
        cout<<"8 not found."<<endl;
    else
        cout<<"8 found."<<*it3<<endl;
}

在这里插入图片描述

3.2 迭代器（iterators）是一种smart pointe

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最重要的便是内容提领(dereference)和成员访问(member access) , 因此，迭代器最重要的编程工作就是对operator*和operator->进行重载(overloading)工作。
C++标准程序库有一个auto_ptr这是一个用来包装原生指针(native pointer)的对象，声名狼藉的内存漏洞(memory leak)问题可藉此获得解决。

auto_ptr用法如下，和原生指针一模一样：

void func()
{
    auto_ptr<string> ps(new string("jjhou"));
    cout<<*ps<<endl;//输出:jjhou
    cout<<ps->size()<<endl;//输出:5
    //离开前不需 delete， auto_ptr 会自动释放内存
}

函数第一行的意思是，以算式new动态配置一个初值为 ''jjhou" 的string对象，并将所得结果（一个原生指针）作为auto_ptr对象的初值。注意， auto_ptr角括号内放的是 “原生指针所指对象” 的型别，而不是原生指针的型别。

auto_ptr 的源代码在头文件中，auto_ptr的行为如下：

template<class T>
class auto_ptr {
public:
explicit auto_ptr(T *p = 0): pointee(p) {}
template<class U>
auto_ptr(auto_ptr<U>& rhs): pointee(rhs.release()) {}
_auto_ptr() { delete pointee; }

template<class U>
auto_ptr<T>& operator=(auto_ptr<U>& rhs) {

    if(this !=&rhs) reset(rhs.release());
    return *this;
}
T& operator* () const { return *pointee; }
T* operator->()const { return pointee; }
T* get() const{ return pointee;}
//...
private:
T *pointee;
};

有了模仿对象，设计list迭代器,list节点的结构如下：

template <typename T>
class List
{
    void insert_front(T value);
    void insert_end(T value);
    void display(std::operator &os = std::cout)const;
    //...
private:
    ListItem<T>* _endl;
    ListItem<T>* _front;
    long _size;
};

template<typename T>
class LisItem
{
public:
    T value()const {return _value;}
    ListItem* next() const {return _next;}
    //...
   private:
    T _value;
    ListItem* _next;//单向链表
};

如何将这个List套用到先前所说的find()呢？我们需要为它设计一个行为类似指针的外衣，也就是个迭代器。
当我们提领这一迭代器时，传回的应该是个ListItem对象；
为了让该迭代器适用千任何型态的节点，而不只限于Listrtem, 我们可以将它设计为一个class template:

template <class Item> // Item可以是单向链表节点或双向链表节点。
struct ListIter
{
    Item* ptr;
    ListIter(Item* p = 0):ptr(p){}//默认构造
    
    //不必实现copy ctor, 因为编译器提供的缺省行为己足够
   //不必实现operator=, 因为编译器提供的缺省行为己足够
    
    Item& operator* () const{ return *ptr; } 
    Item* operator->() const { return ptr; }
   
    
 //(1) pre-increment operator 
Listiter& operator++()
{
        ptr = ptr->next (); 
        return *this;
}

   
//(2) post-increment operator 
Listiter operator++(int)
{ Listiter tmp = *this; 
    ++*this; 
    return tmp;
}

bool operator==(const Listiter& i) const 

{ 
    return ptr == i.ptr;
} 

bool operator !=(const ListIter& i) const
{ 
        return ptr != i.ptr; 
}
        
};

现在我们可以将List和find()藉由Listiter粘合起来：

void main()
{
    List<int> mylist;
    for(int i=0;i<5;++i)
    {
        mylist.insert_front(i); 
        mylist.insert_end(i+2); 
    }
    mylist.display();
    
    Listiter<Listitem<int> > begin(mylist.front());
    ListIter<Listitem<int> > end; // default O, null 
    Listiter<Listitem<int> > iter; // default O, null
    
    iter = find(begin, end, 3); 
    if (iter == end)       
    cout << "not found" << endl; 
    else 
    cout << "found. " << iter->value()<< endl; 
    //执行结果：found. 3 
    
    iter=find(begin,end, 7);   
    if (iter == end)        
    cout << "no七found"<< endl; 
    else 
    cout << "found. " << iter->value() << endl; 
    //订执行结果：not found 
}

注意，由于find()函数内以＊iter!= value来检查元素值是否吻合，而本例之中value的型别是int,iter的型别是Listitem,两者之间并无可供使用的operator!=,所以必须另外写一个全局的operator!=重载函数，并以int和Listrtem作为它的两个参数型别：

template <typename T>
bool operator!=(const ListItem<T>& item,T n)
{return item.value() !=n;}

上面为了完成一个针对List而设计的迭代器，避免不了暴露了太多List实现细节：

在main()之中为了制作begin和end两个迭代器，暴露了Listitem;
在Listrter class之中为了达成operator++的目的，暴露了Listrtem的操作函数next（）。

如果不是为了迭代器，Listrtem 应该完全隐藏。换句话说，要设计出Listiter, 首先必须对List 的实现细节有非常丰富的了解。
既然无可避免，就把迭代器的开发工作交给 List的设计者好了，所有实现细节反而得以封装起来不被使用者看到。这正是为什么每一种STL容器都提供有专属迭代器的缘故。

3.3 迭代器相应型别（associated types）

上面的Listrter提供了一个迭代器雏形。我们会发现，在算法中运用迭代器时，很可能会用到其相应型别(associatedtype)。
什么是相应型别？迭代器所指之物的型别便是其一。
假设算法中有必要声明一个变量，以＂迭代器所指对象的型别”为型别，如何是好？毕竟C++只支持sizeof(),并未支持typeof () ! 即便动用RTII性质中的typeid(), 获得的也只是型别名称，不能拿来做变董声明之用。

解决方法：利用functiontemplate的参数推导(argumentdeducation)机制。例如：

template <class T,class T>
void func_imp1(I iter,T t)
{
 
    T tmp;//这里解决了问题，T就是迭代器所指之物的型别，本例为int
    //...这里做原本func()应该做的全部工作
};

template<class T>
inline void func(I iter)
{
    func_imp1(iter,*iter);//func的工作全部移往func_imp1
}


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

以func()为对外接口，却把实际操作全部置与func_imp1()之中。由于func_imp1()是一个function template, 一旦被调用，编译器会自动进行template 参数推导。于是导出型别T,顺利解决了问题。

迭代器相应型别不只是“迭代器所指对象的型别”一种而已，最常用的相应型别有五种，但不是任何情况如何一种都可以利用上述的template参数推导机制来取得。

3.4 Traits编程技法——STL源代码门钥

迭代器所指对象的型别，称为迭代器的value type。
上面的参数型别推导技巧虽然可用于value type ，却非全面可用：万一value type必须用于函数的传回值，就束手无策了。
函数的“template参数推导机制”推而导之的只是参数，无法推导函数的返回值型别。

需要其他方法解决，比如:声明内嵌型别是个好主意：

template <class T>
struct MyIter{
    typedef T value_type;//内嵌型别声明
    T* ptr;
    MyIter(T* p=0):ptr(p){}
    T& operator*() const {return *ptr;}
    //...
};

template <class I>
typename I::value_type;//func的返回值型别
func(I ite)
{return *ite;}

//...
MyIter<int> ite(new int(8));
cout<<func(ite);//输出8
};

注意，func()的回返型别必须加上关键词typenarne,因为T是一个template参数，在它被编译器具现化之前，编译器对T一无所悉，换句话说，编译器此时并不知道Myiter<T>:: value_type代表的是一个型别或是一个member function或是一个data member。关键字typename的用意在于告诉编译器这是一个型别，才能顺利通过编译。
看起来不错。但是有个隐晦的陷阱：并不是所有迭代器都是class type。原生指针就不是！如果不是class type, 就无法为它定义内嵌型别。但STL(以及整个泛型思维）绝对必须接受原生指针作为种迭代器，所以上面这样还不够。
有没有办法可以让上述的一般化概念针对特定情况（例如针对原生指针）做特殊化处理呢？

templatepartial specialization可以做到。

Partial Specialization （偏特化）的意义

意义是：如果class template拥有个以上的 template参数，我们可以针对其中某个（或数个，但非全部）template参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些template参数赋予明确的指定）。

假设class template如下：

template<typename U, typename V, typename T> class C { ... };

partial specialization的字面意义容易误导我们以为，所谓“偏特化版”一定是对template参数U或V或T(或某种组合）指定某个参数值。其实不然，对于partial specialization的意义说得十分得体：”所谓partial specialization的意思是提供另一份template定义式，而其本身仍为templatized"。
《泛型思维》一书对partialspecialization的定义是：“针对（任何）template参数更进—步的条件限制所设计出来的一个特化版本”。

由此，面对以下这个class template:

template <typename T>
class C{...};//这个泛化版本允许（接受）T为如何型别

下面的partial specialization的形式难以让人接受：

template <typename>
class C<T*>{...};//这个特化版本适用于“T为原生指针”的情况
//“T为原生指针"便是“T为如何型别”的一个更进一步的条件限制

这样便可以解决前述“内嵌型别“未能解决的问题。
先前的问题是，原生指针并非class,因此无法为它们定义内嵌型别。现在，我们可以针对“迭代器之template参数为指针”者，设计特化版的迭代器。

下面的是关键，下面这个class template专门用来“萃取“ 迭代器的特性，而value type正是迭代器的特性之一：

template <class T>
struct iterator_traits{//traits意为“特性”
typedef typename I::value_type  value_type;
};

traits意义是，如果I定义有自己的value type, 那么通过这个traits的作用，萃取出来的value_type就是I::value_type。
换句话说，如果I定义有自己的value type, 先前那个func()可以改写成这样：

template <class I>
typename iterator_traits<I>::value_type//这一整行是函数回返型别
func (I ite)
{
return *ite;
}

除了多一层间接性，traits又拥有特化版本。现在，我们令iterator_traites拥有一个 partial specializations如下：

template <class T>
struct iterator_traits<T*>{//偏特化版-迭代器是个原生指针
typedef T value_type;
};

于是，原生指针int*，虽然不是一种class type ,亦可通过traits取其value type，这就解决了先前的问题。

但是针对“指向常数对象的指针(pointer-to-const）"'下面这个式子得到什么结果：

iterator_traits<const int*>::value_type

获得的是const int而非int。这不是我们想要的，我们希望利用这种机制来声明一个暂时变量，使其型别与迭代器的value type相同，而现在，声明一个无法赋值（因const之故）的暂时变量，没什么用！
因此，如果迭代器是个 pointer-to-const, 我们应该设法令其value type为一个non-const型别。没问题只要另外设计一个特化版本，就能解决这个问题：

template <class T>
struct iterator_traits<const T*>{//偏特化:当迭代器是个point-to-const时，
typedef T value_type;
};

现在，不论面对的是迭代器Myiter,或是原生指针int或const int都可以通过traits取出正确的（我们所期望的）value type。
下图说明了traits所扮演的“特性萃取机”角色，萃取各个迭代器的特性。迭代器特性指的是迭代器的相应型别(associatedtypes)。
当然，若要这个“特性萃取机"traits能够有效运作，每一个迭代器必须遵循约定，自行以内嵌型别定义(nestedtypedef)的方式定义出相应型别(associatedtypes)。
这是一个约定，谁不遵守这个约定，谁就不能兼容于STL。
在这里插入图片描述，最常用到的迭代器相应型别有五种：value _type, difference type，pointer，reference,iterator catagoly。如果开发的容器能与STL交融，一定要为容器的迭代器定义这五种相应型别。“特性萃取机"traits会很忠实地将原汁原味梓取出来：

ternplate <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;
};

iterator_traits必须针对传入之型别为pointer及pointer-to-const者，设计特化版。

4.1 迭代器相应型别之一：value type

所谓value type, 是指迭代器所指对象的型别。任何一个打算与STL算法有完美搭配的class,都应该定义自己的valuetype内嵌型别，做法就像上节所述。

4.2 迭代器相应型别之二：difference type

difference type用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。
如果一个泛型算法提供计数功能，例如STL的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, traits的如下两个（针对原生指针而写的）特化版本，以C++内建的ptrdiff-t(定义于头文件）作为原生指针的difference 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;
};

//针对原生的pointer-to-const而设计的"偏特化"版

template<class T>
struct iterator_traits<const T*>{
    //...
    
    typedef ptrdiff_t difference_type;
    };

现在，任何时候当我们需要任何迭代器I的difference type , 可以这么写：

typename iterator_traits<I>::difference_type

4.3 迭代器相应型别之三： reference type

从 “迭代器所指之物的内容是否允许改变” 的角度观之，迭代器分为两种：

”不允许改变所指对象之内容” 者，称为constant iterators, 例如cons t int* pic;
允许改变 ”所指对象之内容” 者，称为mutable iterators, 例如int* pi。

当我们对一个mutable iterators进行提领操作时，获得的不应该是一个右值(rvalue) , 应该是一个左值(lvalue) , 因为右值不允许赋值操作(assignment) , 左值才允许：

int* pi = new int(5);
const int* pci = new int(9);
*pi = 7;//对mutable iterator进行提领操作时，获得的应该是个左值，允许赋值
*pic = 1; //这个操作不允许，因为pci是入constant iterator,提领pci所得结果，是个右值，不允许被赋值

在C++中，函数如果要传回左值，都是以by reference的方式进行，所以当 p是个mutable iterators时，如果其value type是T,那么*p的型别不应该是T, 应该是T&。
如果p是一个constant iterators, 其value type是T, 那么*p的型别不应该是const T, 而应该是const T&。
这里所讨论的 *p的型别，即所谓的reference type。

4.4 迭代器相应型别之四： pointer type

pointers和references在C++中有非常密切的关联。
如果 ”传回一个左值，令它代表p所指之物”是可能的。
那么“传回一个左值，令它代表p所指之物的地址”也一定可以。
也就是说，我们能够传回一个pointer,指向迭代器所指之物。

z这些相应性别在前面的ListIter class 种出现过：

Item& operator* () const { return *ptr; }
 Item* operator-> () const { return ptr; }

Item&便是Listrter的reference type, 而Item* 便是其pointer type。

把reference type和pointer type这两个相应型别加入traits内：

template <class>
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;
};

//针对原生的pointer-to-const而设计的"偏特化"
template<class T>
struct iterator_traits<const T*>{
    //...
    typedef const T* pointer;
    typedef const T&  reference;
};

4.5 迭代器相应型别之五： itera tor_ca tegory

最后一个（第五个）迭代器的相应型别会引发较大规模的写代码工程。在那之前，我必须先讨论迭代器的分类。根据移动特性与施行操作，迭代器被分为五类：

Input Iterator: 这种迭代器所指的对象，不允许外界改变。只读(read only)。
Output Iterator: 唯写(write only)。
Forward Iterator: 允许 “写入型算法（例如replace())在此种迭代器所形成的区间上进行读写操作。
Bidirectional Iterator: 可双向移动。某些算法需要逆向走访某个迭代器区间（例如逆向拷贝某范围内的元素），可以使用Bidirectional Iterators。
Random Access Iterator: 前四种迭代器都只供应一部分指针算术能力（前三种支持operator++, 第四种再加上operator–) , 第五种则涵盖所有指针算术能力，包括p+n, p-n, p[n], pl-p2, pl<p2。

这些迭代器的分类与从属关系，可以用下图表示。直线与箭头代表的并非C++的继承关系，而是所谓concept(概念）与refinement(强化）的关系：
在这里插入图片描述

设计算法时尽量针对图中的某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同情况下提供最大效率。
在研究STL的过程中，每一分每一秒我们都要谨记在心，效率是个重要课题。
假设有个算法可接受Forward Iterator, 你以RandomAccess Iterator喂给它，它当然也会接受，因为一个RandomAccess Iterator必然是一个Forward lteator。但并不是最佳。

advanced()为例

advance() （这是许多算法内部常用的一个函数），该函数有两个参数，迭代器p和数值n;函数内部将p累进n次（前进n距离）。
下面有三份定义，一份针对Input Iterator, 一份针对Bldirectional Iterator, 另一份针对 Random Access lterato。倒是没有针对Forward lterator而设计的版本，因为那和针对lnputtterator而设计的版本完全一致。

template<class InputIterator,class Distance> void advance_II(InputItterator&i, Distance n) 
{
//单向，逐一前进
while(n--)++i;//或写for(; n > O; --n, ++i);
}
template<class Bidirectionaliterator, class Distance>
void advance_BI(Bidirectionaliterator& i,Distance n)
{
//双向，逐一前进
if(n>=0)
while(n--) ++i;//或写for(; n > O; --n, ++i);
}
else
while(n++)--i;//或写for(; n < O; --n, ++i);
}

template <class RandomAccessIterator,class Distance> 
void advance_RAI(RandomAccessiterator& i,Distance n)
{
//双向，跳跃前进
i+=n;
}

当程序调用advance()时，应该选用（调用）哪一份函数定义呢？
如果选择advance_II(),对RandomAccess Iterator而言极度缺乏效率，原本O(1) 的操作竟成为O(N)。
如果选择advance_RAI() , 则它无法接受InputIterator。

我们需要将三者合一，下面是一种做法：

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(i,n);
}

但是像这样在执行时期才决定使用哪一个版本，会影响程序效率。
最好能够在编译期就选择正确的版本。重载函数机制可以达成这个目标。
前述三个advance_xx()都有两个函数参数，型别都未定（因为都是template 参数）。为了令其同名，形成重载函数，我们必须加上一个型别已确定的函数参数，使函数重载机制得以有效运作起来。

设计考虑如下：如果traits有能力萃取出迭代器的种类，我们便可利用这个＂迭代器类型”相应型别作为advanced()的第三参数。这个相应型别一定必须是一个class type，不能只是数值号码类的东西，因为编译器需仰赖它（一个型别）来进行重载决议。下面定义五个classs，代表五种迭代器类型：
II五个作为标记用的型别(tagtypes)

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{ } ;

这些classes只作为标记用，所以不需要任何成员。至于为什么运用继承机制，稍后再解释。现在重新设计__advance() (由于只在内部使用，所以函数名称加上特定的前导符），并加上第三参数，使它们形成重载：

template <class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,input_iterator_tag)
{
//单向，逐一前进
while(n--)++i;
}
//这是单纯的传递调用函数
template<class ForwardIterator,class Distance> 
inline void advance  ForwardItrator&i, Distncen n,forward_iterator_tag)
{
//单纯地进行传递调用(forwarding)
advance(i, n, input_iterator_tag{));
}

template<class BidiectionalIterator,class Distance> 
inline void _advance(Bidiectionaliterator&1, Distance n,bidirectional_iterator_tag)
{
//双向，逐一前进
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)
{
//双向，跳跃前进
i+=n;
}

注意上述语法，每个__advance()的最后一个参数都只声明型别，并未指定参数名称，因为它纯粹只是用来激活重载机制，函数之中根本不使用该参数。如果硬要加上参数名称也可以，画蛇添足罢了。

这时需要个对外开放的上层控制接口，调用上述各个重载的 _advance ()。
这一上层接口只需两个参数，当它准备将工作转给上述的 _advance ()时，才自行加上第三参数：迭代器类型。
因此，这个上层函数必须有能力从它所获得的迭代器中推导出其类型－这份工作自然是交给traits机制：

template <class Inputlterator, class Distance> 
inl ine void advance(InputIterator&i, Distancen) 
{
__advance(i,n,iterator_traits<InputIterator>::iterator_category());
}

注意上述语法iterator_traits<Iterator>::iterator_category()将产生一个暂时对象（道理就像int()会产生一个int暂时对象一样），其型别应一该隶属于前述五个迭代器类型之一。然后根据这个型别，编译器才决定调用哪个__advance()重载函数。

为了满足上述行为，traits必须再增加一个相应的型别：

template <class I> 
struct iterator_traits{
...
typedef typename I::iterator_category category;
};
//针对原生指针而设计的"偏特化"
template <class T>
struct iterator_traits<T*>{
...
//注意，原生指针是一种Rondom Access iterator
typedef random_access_iterator_tag iterator_category;
};

//针对原生的pointer-to-const而设计的 ＂偏特化版(partial specialization) "
 template <class T> 
struct iterator_traits<const T*> 
//注意， 原生的pointer-to-const是一种Random Access Iterator 
typedef random_access_iterator_tag iterator_category;
};

任何一个迭代器，其类型永远应该落在 “该迭代器所隶属之各种类型中，最强化的那个"。
例如，int＊既是Random Access Iterator, 又是Bidirectional Iterator, 同时也是Forward Iterator , 而且也是Input Iterator, 那么，其类型应该归属为 random_access_iterator_tag。

你是否注意到advance ()的template参数名称取得好像不怎么理想：

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

按说advanced()既然可以接受各种类型的迭代器，就不应将其型别参数命名为Input Iterator。这其实是STL算法的一个命名规则：以算法所能接受之最低阶迭代器类型，来为其迭代器型别参数命名。

消除“单纯传递调用的函数”
以class来定义迭代器的各种分类标签的好处：

可以促成重载机制的成功运作（使编译器得以正确执行重载决议，overloaded resolution)
通过继承，我们可以不必再写 “单纯只做传递调用” 的函数（例如前述的advance () Forvvardlterator版）。

为什么能够如此？考虑下面这个小例子，从其输出结果可以看出端倪：

在这里插入图片描述

#include <iostream> 
using namespace std; 
struct B {};// B 可比拟为InputIterator 
struct D1 : public B {};//D1可拟Forwarditerator
struct D2 : public D1{};//D2可比拟为BidirectionalIterator

template <class I>
func(I& p,B)
{cout<<“B version”<<endl;}

template <class I>
func(I& p,D2)
{cout<<“D2 version”<<endl;}

int main()
{
int* p; 
func(p,B());//参数与参数完全吻合。输出："B version"
func(p,D1());//参数与参数未能完全吻合；因继承关系而自动传递调用输出：“B version”

func(p,D2());//参数与参数完全吻合，输出：“D2 version”
}

distance(）为例
关于＂迭代器类型标签＂的应用，以下再举一例。distance()也是常用的个迭代器操作函数，用来计算两个迭代器之间的距离。针对不同的迭代器类型，它可以有不同的计算方式，带来不同的效率。整个设计模式和前述的advance()如出一辙：

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type 
__distance(InputIterator first,InputIterator last,input_iterator_tag)
{
    iterator_traits<InputIterator>::difference_type n =0 ;
    //逐一累计距离
    while(first !=last)
    {
        ++first;
        ++n;
    }
    return n;
}

template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator fist,RandomAccessIterator last,random_access_iterator_tag)
{
    //直接计算差距
    return last-fist;
}

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator fist,InputIterator last)
{
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first,last,category());
}

distance()可接受任何类型的迭代器；
template型别参数之所以命名为Input Iterator,是为了遵循STL算法的命名规则：以算法所能接受之最初级类型来为其迭代器型别参数命名。
此外也请注意，由于迭代器类型之间存在着继承关系，“传递调用(forwarding)"的行为模式因此自然存在。换句话说,当客端调用distance()并使用OutputIterators或Forward Iterators或BidirectionalIterators时，统统都会传递调用InputIterator版的那个__distance()函数。

3.5 std::iterator的保证

为了符合规范，任何迭代器都应该提供五个内嵌相应型别，以利于traits萃取，否则便是自别于整个STL架构，可能尤法与其它STL组件顺利搭配。
然而免挂一漏万，谁也不能保证不会有粗心大意的时候。如果能够将事情简化，就好多了。STL提供了一个iteratorsclass如下，如果每个新设计的迭代器都继承自它，就可保证符合STL所需之规范：

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 class不含任何成员，纯粹只是型别定义，所以继承它并不会招致任何额外负担。
由于后三个参数皆有默认值，故新的迭代器只需提供前两个参数即可。

先前3.2节土法炼钢的Listiter,如果改用正式规格，应该这么写：

template <class Item> 
struct ListIter: 
public std::iterator<std::forward_iterator_tag,Item>
{...}

总结：

设计适当的相应型别(associatedtypes) , 是迭代器的责任。
设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍历自己，并
执行迭代器该有的各种行为（前进、后退、取值、取用成员…)。
至于算法，完全可以独立千容器和迭代器之外自行发展，只要设计时以迭代器为对外接口就行。
traits编程技法大量运用于STL实现品中。它利用“内嵌型别”的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面的能力，弥补C++不为强型别(strongtyped l语言的遗憾。

3.6 iterator源代码完整重列

由于讨论次序的缘故，先前所列的源代码切割散落，有点凌乱。下面重新列出SGI STL<stl_iterator.h>头文件内与本章相关的程序代码。该头文件还有其他内容，是关于iostream iterator、inserter iterators以及reverse iterators的实现，将在后面讨论：

//节录自SGI STL <stl_itera七or.h>
//五种迭代器类型
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{};
//为避免写代码时挂－漏万， 自行开发的迭代器最好继承自下面这个std:: iterator
template <class Category, class T, class Distance = ptrd辽f_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;
};

// '榨汁机" traits
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_ca七egory;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
};

//针对原生指针(native pointer)而设计的七raits偏特化版 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;
};
//针对原生之pointer-to-const而设计的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;
};

//这个函数可以很方便地决定某个迭代器的类型(category)
template<class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category () ;
}

//这个函数可以很方便地决定某个迭代器的distance type
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const iterator){
    return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

//这个函数可以很方便地决定某个迭代器的value type
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&)
{
    return static_cast <typename iterator_traits<Iterator>::value_type*>(O);
}


//以下是整组distance 函数
template <class Inputterator>
inline iterator_traits<Inputiterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag){
    iterator_traits<Inputiterator>::difference_type n= 0;
    while(first !=last)
    {
        ++first;
        ++n;
    }
    return n;

}
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,random_access_iterator_tag){
            return last-first;
}


template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type 
distance(InputIterator first, InputIterator last){ 
    typedef typename
    iterator_traits<InputIterator>::iterator_category categroy;
    return __distance(first,last,category());
}


//以下是整组advance函数

template <class InputIterator,class distance>
inline void __advance(InputIterator& i,Distance n,input_iterator_tag){
    while(n--)++i;
}

template <class BidirectionalIterator,class Distance>
inline void __advance(BidirectionlIterator& i,Distance n,bidirectional_iterator_tag){
    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){
    i +=n;
}

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

3.7 SGI STL的私房菜：__type_traits

traits编程技法弥补了C++语言本身的不足。STL只对迭代器加以规范，制定出iterator_traits这样的东西。SGI把这种技法进一步扩大到迭代器以外，于是有了__type_traits。双底线前缀词意指这是SGI STL内部所用的东西，不在STL标准规范之内。
iterator_traits负责萃取迭代器的特性，_type_traits则负责萃取型别(type)的特性。
型别特性是指：这个型别是否具备non-trivial defalt ctor? 是否具备non-trivialcopy ctor? 是否具备non-trivialassignment operator? 是否具备non-trivialdtor?
如果是否定的，我们在对这个型别进行构造、析构、拷贝、赋值等操作时，就可以采用最有效率的措施（例如根本不调用身居高位，不谋实事的那些constructor,destructor) , 而采用内存直接处理操作如malloc()、memcpy()等等，获得最高效率。
定义于SGI<type_traits.h>中的__type_traits,提供了一种机制，允许针对不同的型别属性(typeattributes) , 在编译时期完成函数派送决定(function dispatch)。这对于撰写template很有帮助，例如，当我们准备对一个“元素型别未知”的数组执行copy操作时，如果我们能事先知道其元素型别是否有一个trivial copy constructor , 便能够帮助我们决定是否可使用快速的memcpy()或 memmove ()。

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

__type_traits<T>::has_trivial_default_constructor 
__type_traits<T>::has_trivial_copy_constructor 
__type_traits<T>::has—trivial_assignrnent_operator 
__type_traits<T>::has_trivial_destruetor
__type_traits<T>: :is_POD_type//POD:Plain Old Data

希望上述式子响应我们真”或假＂(以便我们决定采取什么策略), 但其结果不应该只是个bool值，应该是个有着真／假性质的“对象"，因为我们希望利用其响应结果来进行参数推导，而编译器只有面对class object形式的参数，才会做参数推导。为此，上述式子应该传回这样的东西：

struct _true_type { }; 
struct_false_type{ };

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

tempalte <class type>
struct _type_trits{
typedef __true_type    this_dummy_must_be_first;
/*不要移除这个成员。它通知”有能力自动将＿type_traits特化”
的编译器说，我们现在所看到的这个＿type_traitstemplate是特
殊的。这是为了确保万一编译器也使用一个名为_type_traits而其实与此处定义并无任何关联的template时，所有事情都仍将顺利运作
*/
}

/*以下条件应被遵守，因为编译器有可能自动为各型别产生专属的＿＿type—traits

特化版本：
你可以重新排列以下的成员次序
你可以移除以下任何成员
绝对不可以将以下成员重新命名而却没有改变编译器中的对应名称 －新加入的成员会被视为一般成员，除非你在编译器中加上适当支持＊／

typedef _false_type  has_tri vial_defaul t_constructor;
typedef_false_type  has_tri vial_copy _constructor; 
typedef _false_type  has_tri vial_assignment_operator;
typedef _false_type  has_七rivial_destructor;
typedef _false_type  is_POD_type; 
};

为什么SGI把所有内嵌型别都定义为__false_type呢？是的，SGI定义出最保守的值，然后（稍后可见）再针对每一个标量型别(scalartypes)设计适当的_type_traits特化版本，这样就解决了问题。

上述_type_traits可以接受任何型别的参数，五个typedefs将经由以下管道获得实值：

一般具现体(general instantiation) , 内含对所有型别都必定有效的保守值。上述各个has_trivial_xxx型别都被定义为_false_type,就是对所有型别都必定有效的保守值。
经过声明的特化版本，例如<type_traits.h>内对所有C++标量型别scalar types)提供了对应的特化声明。
某些编译器（如SiliconGraphics N32和N64编译器）会自动为所有别别提供适当的特化版本。（这真是了不起的技术。不过我对其精确程度存疑）。

以下便是<type_traits.h>对所有C++标量型别所定义的_type_traits 特化版本。这些定义对于内建有_types_traits支持能力的编译器（例如Silcon Graphics N32和N64)并无伤害，对于无该等支持能力的编译器而言，则属必要。
在这里插入图片描述

__types_traits在SGI STL中的应用很广。举几个例子：

①.uninitalized_fill_n()全局函数：

template <class Forwarditerator, class Size, class T> 
inline ForwardIterator uninitialized_fill_n (Forwarditerator first,Size n, const T& x) {
return _uninitialized_fill_n(first, n, x, value_type(first));
}

该函数以x为蓝本，自迭代器first开始构造n个元素。为求取最大效率，首先以value_type()萃取出迭代器first的value type, 再利用 _type_traits判断该型别是否为POD型别：

template<classForwardlterator, class Size, class T, class T1> 
inline Forwardlterator _uninitialized_fill_n (Forwardlterator first,Size n,const T&x,T1*){
typedef typename _type_traits<T1>::is_POD_type is_POD; return _uninitialized_fill_n_aux(first, n, x, is_POD());
}

以下就“是否为POD型别”采取最适当的措施：

//如果不是POD型别，就会派送(dispatch)到这里

 template<class Forwarditerator, class Size, class T> Forwarditerator 
 _uninitialized_fill_n_aux(Forwarditerator first,Size n,const T& x,__false_type){
 ForwardItrator cur = first; 
 //为求阅读顺畅简化， 以下将原本有的异常处理(exception handling)去除
  for (; n > O; --n, ++cur) 
construct(&*cur, x); 
return cur; 
}
//如果是POD型别， 就会派送(dispatch)到这里。 下两行是原文件所附注解
 //如果copy construction等同于assigrunent, 而且有trivial destructor, 
//以下就有效
template <class Forwarditerator, class Size, class T> 
inline Forwarditerator 
__uninitialized_fill_n_aux(Forwarditerator first, Size n, const T& x, __true_type){
return fill_n(first,n,x);
}
//以下是定义于<stl_algobase.h>中的巨ll_n()
template <class Outputiterator, class Size, class T> 
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
for(;n>0;--n;++first)
*fisrt = value;
return first;
}

②.负责对象析构的destroy ()全局函数

此函数在前面说明。

③.copy()全局函数（泛型算法之一）

这个函数有非常多的特化(specialization)与强化(refinement)版本，弹精竭虑，全都是为了效率考虑，希望在适当的情况下采用最“雷霆万钧＂的手段。最基本的想法是这样：

//拷贝一个数组， 其元素为任意型别， 视情况采用最有效率的拷贝手段
template <class T> inline void copy(T* source, T* destination,int n) {
copy(source,destination, n,typename_type_traits<T>::has_trivial_copy_consuctor());
}

//拷贝一个数组， 其元素型别拥有non-trivial copy constructors 
template <class T> void copy(T* source,T* destination, int n,
{...}

//拷贝一个数组，其元素型别拥有trivialcopy constructors 
//可借助memcpy()完成工作
template <class T> void copy(T* source,T* destination,int n,__true_type)
{...}

以上只是针对“函数参数为原生指针＂的情况而做的设计。第6章的copy()算法是个泛型版本，情况又复杂许多。详见6.4.3节。

请注意，<type_traits.h>并未像其它许多SGISTL头文件那样，有如下的声明：
在这里插入图片描述

如果你是SGI STL的用户，你可以在自己的程序中充分运用这个 __ype_traits。
自行定义了一个shape class, _type_traits会对它产生什么效应呢？
如果编译器够厉害（例如Silicon Graphics的N32和N64编译器），你会发现，_type_traits针对Shape萃取出来的每一个特性，其结果将取决于我的Shape是否有trivialdefalt ctor, 或trivialcopy ctor, 或trivialassignment operator, 或triviald tor而定。
对大部分缺乏这种特异功能的编译器而言，_type_traits针对Shape萃取出来的每一个特性都是_false_type,即使shape是个POD型别。

这样的结果当然过于保守，但是别无选择，除非我针对Shape,自行设计一个_type_traits特化版本，明白地告诉编译器以下事实（举例）：

tempalte<>struct __type_traits<Shape>{
typedef _true_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;
  };

究竟class什么时候该有自己的 non-trivial default constructor, non-trivial copy constructor, non-trivial assignment operator, non-trivial destructor呢？一个简单的判断准则是：如果class内含指针成员，且对它进行内存动态配置，那么这个class就需要实现出自己的non-trivial-xxx。
即使无法全面针对你自己定义的型别，设计_type_traits特化版本，尤论如何，至少，有了这个__type_traits之后，当我们设计新的泛型算法时，面对C++标量型别，便有足够的信息决定采用最有效的拷贝操作或赋值操作:因为每一个标量型别都有对应的_type_traits特化版本，其中每一个typedef 的值都是__true_type。