迭代器Iterator

23个设计模式中迭代器模式

定义：提供一种方法，使之能够依序寻访某个聚合物(容器)所含的各个元素，而又无需暴露该聚合物内保部表达式

迭代器设计

在泛型设计思维和STL运用中迭代器都是举足轻重的
STL中心思想：将数据容器containers 和 算法algorithm分开，彼此独立设计，最后在以一贴胶着剂将他们撮合到一起
设计中容器和算法的泛型化由class templates 、 function template 完成
良好的胶着剂就是迭代器

迭代器可以通俗的看成一种智慧指针smart pointer

迭代器是一种行为类似指针的对象·
指针行为最常见的是：内容提领(dereference) 和 成员访问(member access)
所以迭代器最重要的编程工作就是对operator* 和 operator-> 进行重载(overloading) 可以参照auto_ptr
迭代器设计时所针对的容器必须保证透明，使用者可以不了解封装细节，但是迭代器设计者必须详细了解容器设计细节，所以每种容器都用自己的迭代器

迭代器相应型别

常见的迭代器相应型别有5中，所指对象行别是其中之一
相应型别迭代器所指物的型别就是其中之一
C++ 只支持sizeof() 不支持typeof() 使用RTTI 性质中typeid 也只是得到名称不能当做变量声明使用，所以使用function template 的参数推导机制(argument deducation)
可以通过一次模板函数传参数完成类型推定，使用相同模板定义变量完成模板类型使用
template 参数推导技巧

template <class  I,class T>
void func_impl(I iter,T t)
{T tmp; // 完成 使用所指之物型别1
}template <class I>
inline void func(I iter)
{func_impl(iter,*iter);
}
int main()
{int i ;func(&i);
}

traits（特性） 编程技法

迭代器所指对象型别称为迭代器value type
参数推导有时并不能完成我们所需的全部功能，这是我们引入了内嵌型别
使用内嵌型别，以所指对象型别为例当想在调用函数中使用所指对象型别作为返回值时可以使用

template <class T>
struct MyIter{typedef T value_type; // 内嵌型别声明 value_type 在后面使用时称为内嵌型别T * ptr;}
template <class I>
typename I::value_type func(I ite) // typename  告诉编译器I::value_type 是类型别名
{return *ite;
}

使用注明 typename 因为 T 是template 参数，再被编译器具现化前，编译器对T 是不知道的，可以使用typename 告诉编译器这是一个型别
traits 编程技法大量在STL 中使用：
利用内嵌型别的编程技巧与编译器的temlate 参数推导功能，增强C++ 未能提供的关于型别认证的能力，弥补C++ 不是强型别语言的遗憾

模板特化

模板
模板的定义：模板就是实现代码重用机制的一种工具，它可以实现类型参数化，即把类型定义为参数， 从而实现了真正的代码可重用性。
模版可以分为两类，一个是 函数模版 ，另外一个是 类模版。
注意：函数模板是可以被重载的（类模板不能被重载），也就是说允许存在两个同名的函数模板，还可以对它们进行实例化，使它们具有相同的参数类型。

特化——给类模板提供重载的功能

函数模板能被重载，而类模板不可以，我们可以通过特化来实现相似的重载效果，从而可以透明地获得具有更高效率的代码。
但是重载只是效果：不能将特化和重载混为一谈，全特化和偏特化都没有引入一个全新的模板或者模板实例。它们只是对原来的泛型（或者非特化）模板中已经隐式声明的实例提供另一种定义。
特化也分为了两种，全特化和偏特化。

全特化

全特化是模板的一个唯一特例，指定的模板实参列表必须和相应的模板参数列表一一对应。
我们不能用一个非类型值来替换模类型参数。但是如果模板参数具有缺省模板实参，那么用来题还实参就是可选的。

template<>
class A<int, double>{ // 类型明确化，为全特化类}；

偏特化

偏特化感觉像是介于普通模板和全特化之间，只存在部分的类型明确化，而非将模板唯一化。
注意函数模板不能被偏特化。

template<typename T>
class A<T, double>{ // 部分类型明确化，为偏特化类}；

注意：迭代器不都是class type 类类型的，不是类类型就无法定义内嵌型别，但是STL 和泛型化要求需要接收原生指针作为迭代器，可以使用偏特化特殊处理
定义：如果类模板 拥有一个以上的模板参数，我们可以针对某个（或多个，但不是全部）参数进行特化工作

特性萃取 traits

内嵌型别无法解决原生类型为指针的类型提取，利用偏特化我们可以设计：迭代器template 参数为指针的 迭代器

template <class I>
struct iterator_traits{ // 特性萃取间接层typedef typename I::value_type value_type; // 使用I 的内嵌型别定义萃取
}
// 使得完成类似功能
template <class I>
typename iterator_traits<I>::value_type // 函数返回值类型
func(I ite)
{return *ite
}

间接层可以增减特化版本，简化代码

template <class T>
struct iterator_traits<T*>{ // 偏特化版——迭代器是个原生指针typedef T value_type; // 萃取得到 T 类型
}

提取类型可以增减，多种类型 提取int * 或者 const int *
通过特性萃取得到，萃取各个迭代器特性
迭代器必须遵守约定义内嵌型别定义方式定义出相应型别

常见的相应型别

常见的迭代器相应型别有：value type , differenece type , pointer, reference,iterator catagoly
内嵌定义及原类型

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

定义是再加入特性性萃取、 pointer 型别萃取 、pointer-to-const 型别萃取定义特化版本

template <class I>
struct iterator_traits{ // 特性萃取普通版本typedef typename I::iterator_category iterator_category;typedef typename I::value_type        value_type;typedef typename I::difference        difference;typedef typename I::pointer           pointer;typedef typename I::reference         reference;
};

value_type 型别

内嵌型别typedef typename I::value_type value_type;
迭代器所指对象型别，获取迭代器所指对象时使用
需要使用时typename iterator_traits<I>::value_type 值类型型别

difference type 型别

differencce type 表示两个迭代器之间的距离
对于连续空间的容器，也可以表示容器的最大容量
使用ptrdiff_t 在C++ 内部 定于 头文件 是原生指针的型别
实现：

// 内嵌型别定义
template <class Distance = ptrdiff_t>
iterator{class Distance = ptrdiff_t, // 指针减法者类型有符号整形
}
// 普通
template <class I>
struct iterator_traits{typedef typenanme 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*>{typedef ptrdiff_t difference_type 
};

使用：typename iterator_traits<I>::differenece_type

reference type

reference type 引用型别，传回左值
mutable iterator(可变迭代器)应该得到的是左值，右值不允许赋值操作

int * pi = new int(5);
const int * pci = new int(9);
*pi = 7; // 得到左值允许赋值
*pci = 1;// 操作不允许，得到的是右值

C++ 以引用的方式存回左值，如果指针p 是mutable iterators 时， *p 的型别应该是T&
内嵌定义

template <cReference = T&>
class iterator{typedef Reference  reference;
};

pointer type

pointer type 所指对像的地址，指向迭代器所指向之物

template <Pointer = T*>
class iterator{typedef  Pointer  pointer;
};

iterator_category

表示迭代器类型集合，决定使用那种迭代器，完成那种功能
根据迭代器移动与操作特性将迭代器分为五类：

1. input iterator 只读 移动类型++
2. output iterator 唯写 移动类型++
3. forward iterator 正向迭代器 移动类型++
4. bidirectional iterator 双向迭代器 移动类型++ –
5. random access iterator 随机存储迭代器 加入算数功能 +n -n [n] p1-p2 p1<p2
   标记迭代器

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

通过此变量决定iterator_category 迭代器变量
内嵌类型需要传入

template <class Category>
struct iterator_traits{typedef Category iterator_category;
};
template <class I>
struct iterator_traits{typedef typename I::iterator_category iterator_category;
}
// 使用
typename iterator_traits<InputIterator>::iterator_category category;
//做参数 category() 生成临时对象

具体使用

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

具体使用：

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

设计适当的响应型别是迭代器的责任。设计师当的迭代器。是容器的责任。为容器本身才知道该设计出怎样的迭代器遍历自己，并且执行迭代器该有各种行为。前进，后退，取值，取成员。
算法完全可以独立于容器和迭代器之外自行发展。只要设计时已迭代器为对外接口就行。

SGI STL __type_traits

__ 双下滑线表示只在STL 内部使用不在STL 标准中
iterator_traits 负责萃取迭代器的特性

__type_traits 则负责萃取型别的特性
关注型别的一些特殊：
是否有无意义的默认构造
是否有无意义的拷贝构造
是否偶无意义的赋值运算符重载
是否有无意义的析构
是否是POD 类型
值有两种 __false_type 和__true_type

即使无法全面针对自己定义的性别，设计__type_traits 特化版本，只要有了这个。当我们设计新的泛型算法时，面对C++的标量便有足够的信息决定采取最有效的拷贝或者复制操作。因为每一个标量都有对应的 __type_traits,其中每一个值都是__true_type