iterator与iterator

 

   跟据侯捷的《STL源码剖析》一书中提到的《Design Patterns》一书中关于iterator模式定义：提供一种方法，使之能够依序寻访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表达方式。

  当然，STL的中心思想在于：将数据容器和算法分开，彼此单独设计，最后再以一帖胶着剂将他们撮合在一起。

  迭代器可以看作是一种smart pointer，故要进行内容提领和成员访问，关键的工作就是对operator*和operator->进行重载

//忽略模板类定义T &operator*()const {return *pointee;} //其中T作为模板参数T* operator->() const{return pointee;} //pointee作为已定义成员

  当然iterator的设计中有一条关键的地方就是封装和隐藏，在此不提。

  为了引出STL设计的关键部分——Traits,需提到一个“相应型别”，也就是迭代其所指之物的类型。

  在c++中只有sizeof()和RTTI中的typeid()，前者只能判断出类型大小，无法进行类型确定，后者由于得到的只是一种别名（vs环境下为全程，MinGW下只是开头字母例如“int”中的‘i’。）况且后者属于运行期判断，不仅需要virutal而且判断期靠后因此不能拿来使用。

  我们在这里需要的并不是输出一个类型的名称，而是在调用过程中间接使用，将其隐藏起来。因此使用模板的类型推断是个不错的做法。

  迭代器相应型别最常用的有五种，分别是value_type,difference_type,reference,pointer,iterator_category。

  这里我们为了下面的Iterator_Traits技术需要提到一下模板偏特化问题。

例如：

templatestruct test{typedef T value_type;T *pointer;};template //偏特化struct test{typedef T value_type;｝　　　　

 偏特化的定义：针对任何template参数更进一步的条件限制所设计出来的一个特化版本。

 我们需要考虑的偏特化情形有如下情况：

 1.原始指针

 2 .const T * 

 之所以进行以下两种特化，主要愿意是1.原始指针无法进行内置型别的定义，也就是说无法进行typedef操作，故对以后的过滤会造成很大的麻烦，而且原始指针不能够被忽略。2.对于const T*来说，不能够被轻易修改，而且如果不另外考虑，也会造成不必要的麻烦。

可对照一下代码

//原模板templatestruct test{ typedef T value_type；};

//原始指针特化templatestruct test{typedef T value_type;};

//const pointertemplatestruct test{typedef T value_type;};

  这样，我们不管是调用哪个，都会有一个value_type，而这个value_type到底是何方神圣，已经被我们隐藏起来了。

  我们可以依照上述例子描述difference_type,pointer,reference。但是difference_type可以typedef库中的ptrdiff_t，来实现。

  至此，我们只剩下了iterator_category这一个类型了。

  iterator_category作为一个指针移动的特性和实行操作，我们有如下五类：

 Input Iterator　　Output Interator　　Forward Iterator　　Bidirectional Iterator　　Random Access Iterator

其中 input 和output这两种属于访问权限修饰，其他的三种依次深入，我们可以从下面代码中看出

struct input_iterator{}; //只读struct output_iterator{};　　//只写struct forward_iterator:public input_iterator{};　　　　//写入型，单项型操作struct bidirectional_iterator:public forward_iterator{}; //可双向移动struct random_access_iterator:public bidirectional_iterator{}; //可进行跳跃访问，涵盖所有指针的运算能力

　　c++中的多态性中有一个重载的概念，也就是说有如下例子

#include
using namespace std;
class base{//empty};class deriver:public base{//empty};void test(base &){//empty;}
int main()
{
base b;
deriver d;
test(b); //ok
test(d); //ok
}

　这样，我们就可以写更少的函数来实现我们需要的所有方法

  好，为了使上述居多的描述更加清晰可见，思路更加清晰，上一大段代码进行分析

  

#includeusing namespace std;struct input_iterator{};struct output_iterator{};struct forward_iterator:public input_iterator{};struct bidirectional_iterator:forward_iterator{};struct random_access_iterator:bidirectional_iterator{};templatestruct iterator{ typedef Category iterator_category; typedef T value_type; typedef Pointer pointer; typedef Reference reference; typedef Distance difference_type;};templatestruct Iterator_traitss{ typedef typename Iterator::iterator_catergory iterator_category; typedef typename Iterator::value_type value_type; typedef typename Iterator::pointer pointer; typedef typename Iterator::reference 　　　　　reference; typedef typename Iterator::difference_type difference_type;};templatestruct iterator_traitss{ typedef random_access_iterator 　　　　　　　　　　　　　　iterator_category; typedef T value_type; typedef ptrdiff_t 　　　　difference_type; typedef T* pointer; typedef T& reference;};templatestruct iterator_traitss{ typedef random_access_iterator 　　　　　　　　　iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& reference;};templateinline typename iterator_traits::iterator_category iterator_category(const Iterator&){ typedef typename iterator_traitss::iterator_category category; return category();}int main(){}

　　

   通过上述代码我们可以清晰看到，有一个iterator类模板，我们在其中的模板参数除了第一个参数外，其他的都有默认值，这个和我们现在使用的vector等其中的Iterator是一致的 。

  有了iterator模板后，我们需要一个强有劲的过滤器，那就是iterator_traits，这个可以将模板参数不管是什么样的，统统封装成统一的typedef，例如 value_type的形成。

  这样我们就可以很方便的进行下面的操作。请注意在iterator_traits中T*的特化还有const T*的特化那里，iterator_category的原名是random_access_iterator.

  总结：

     我们可以通过typedef机制，隐藏，集中一类特性。

     我们可以通过模板参数推导机制，针对同一别名的不同类型进行不同操作。为了效率因素，进行编译期多态而非运行期多态。