STL的迭代器和类型萃取

今天就可以把STL库中迭代器的实现，和类型萃取好好整理一下了

迭代器的设计思维是STL的关键所在，在STL的实际运用和泛型思维，迭代器都扮演着十分重要的角色，STL力求把数据容器和算法的概念分开来，于是就有了STL的两大部分，容器（container）和泛型算法（algorithms），泛型算法有很多参数都是迭代器。

举一个栗子！泛型算法find（）的实现！

1 template<class InputIterator, class T>
2 InputIterator find(InputIterator first, InputIterator last , const T& value)
3 {
4     while(*first != *last && *first != value)
5     {
6         ++first;
7     }
8     return first;
9 }

接受两个输入迭代器的参数

• STL把迭代器分为5个类别
  • trivial迭代器(Trivial Iterator)：只是一个概念，用以区分所有迭代器的定义
  • 输入迭代器(Input iterator)：提供只读操作，可读取其指向元素的值，但不可以改变该元素的值（还包括trivial迭代器中的所有操作（可能是用继承？））
  • 输出迭代器(Output Iterator)：提供只写操作，可改变
  • 前进迭代器(Forward Iterator)：可以改变所指向元素的值，但不可以读取
  • 双向迭代器(Bidirectional Iterator)：可以双向移动
  • 随机访问迭代器(Random Iterator)：韩乾各种指针算数能力，可以像访问顺序表一样随机访问

之前发布的智能指针也算是迭代器的一种，原生的指针当然也可以说是迭代器，只是这么说有些狭隘了迭代器的定义，因为自定义类型的指针功能不够完善，需要重载一些运算符之类的，为什么智能指针也不能直接用作迭代器呢？因为无法获得智能指针所指向的类型！

为什么这么说？因为有的时候我们可能想要使用智能指针所指向的类型去创建一些变量，不好弄，即使是使用type_id也只是获得名字，并不能用来创建变量，有种方法可以用的

 1 template<class T,class U>
 2  
 3 void Fun_impl(T t ,U u)
 4 
 5 {
 6 
 7                  U tmp;//we got the type
 8 
 9 }
10 template<class T>
11 
12 void Fun(T t)
13 
14 {
15 
16                  return Fun_impl(t ,*t);
17 
18 }

这么做就可以获得所指向的类型（并且创建了想要的变量）了，但是当我们需要一个这样的返回值的时候应该怎么办嘛，也许还是上面这种方法？看似是那么的完美，但是编译之后就无情的击碎了你的希望，编译是不通过的

但是我们可以通过内嵌型别声明来获取他们的类型（通过typeid是不行的，因为typeid只能获得类型的名称，并不能用这个名称来声明变量）

这种方法显然是可以的，但是有个隐晦的陷阱，因为不是所有传过来的都是迭代器，万一传过来的就是一个原生指针，原生指针就没有内嵌类型（当然没有，你认为一个int*内部会有内嵌类型么，话说int*有什么内部么）！！！！这就要用到偏特化的知识

那什么是偏特化呢？使用模板的时候，模版参数设定为多个template<class T, class U>模板是可以特定的

 1 template<class T， class U>
 2 class class1
 3 {
 4     T a;
 5     U b;
 6 };
 7 template<class T>
 8 class class1<int>
 9 {
10     T a;
11     U b;
12 };

上述代码中对U进行了特化，嗯！简单易懂，如果T也特化一下，就是全特化了，偏特化就是没有全都特化！

但是还有一个问题，当传过来的的指针是一种指向常值的指针（pointers to const）const int *ptr的时候，，我们很显然获得的类型就是const int，这有些不对劲，因为我们得到的类型拿来声明临时变量是没有办法使用的，就因为他指向了常值，很简单，再拿取偏特化一下就可以了（就是在上图中<T*>处改成<const T*>）

traits就扮演了一个类型萃取机的角色，用来萃取出迭代器所指向的类型（类型萃取？！）

为什么要有这么多的迭代器呢？你看容器人手一个！因为迭代器中有operator++的实现，每个容器存储的方式也不尽相同，vector是顺序存储，list是链式存储，operator++内部实现肯定不一样的，但是又想泛型编程，继承咯，封装咯。。。

• 最常使用到的迭代器的相应类别有5种：value_type,difference_type,pointer,reference,iterator_category
• • value_type就是迭代器所指向的对象的型别，每个迭代器都应该定义有自己的value_type内嵌型别
  • difference_type用来表示两个迭代器之间的距离，因此也可以表示一个容器的最大容量
  • referecne引用？左值，因为有需要const iterator的情况出现，这时候需要一个不能改变所指向对象的迭代器；在C++中，函数如果要传回左值，都是以by reference的方式进行
    
  • pointer_type就是简单的迭代器所指向对象的地址，就是图中第二个
  • iterator_category就是之前用的那个类型萃取，萃取出迭代器的名称，作为函数参数，激活函数重载机制，就是利用traits实现的

那么我接下来就讲讲iterator_category的相关吧

iterator_category干啥的？对下图中五种迭代器进行分类标识

这张图中的箭头并不是代表继承关系，而是概念强化关系，就是说下层一定是个上层，但上层绝不是个下层，就跟正方形是矩形的一种特殊一样，但是矩形就不是正方形

1 struct input_iterator_tag {};
2 struct output_iterator_tag {};
3 struct forward_iterator_tag:public input_iterator_tag {};
4 struct bidirectional_iterator_tag :public forward_iterator_tag {};
5 struct random_access_iterator_tag :public bidirectional_iterator_tag {};

这是五种空壳结构体，没其他用处就是用来标识迭代器类型，用来激活函数重载机制（因为泛型算法中要求的参数都会只给最上层的类型，这样调用时，下层迭代器来了也接受）

为什么会有继承？泛型算法是支持上层迭代器作为参数传入底层迭代器的形参的！就是在这里用的，因为迭代器本身没有继承，所以用标识名继承来激活重载机制

例如advance(iterator ,n)泛型函数，它的作用是将传过来的迭代器往后走n个，每种迭代器的实现肯定不一样的，像是forward_iterator只能一个一个走，走n次，bidirectional_iterator也一样，random_access_iterator就可以一下走n个，如果写成一个，肯定会影响random_access_iterator的效率，所以分开写，那么我怎么知道改调用哪个函数呢？因为我想泛型编程（就是我懒，我想省事）肯定就想只写一个函数名，传个参数，让程序帮我选择调用哪个函数（我的天！这不就是函数重载么）,但是程序需要知道我传的参数是哪种类型的迭代器（就是类型萃取呢！！！）把类型从迭代器中萃取出来！（没弄全，其他的类似）

参数列表中最后一个就是刚才建立的那五个空壳结构体！！调用_advance的时候最后一个参数给迭代器的iterator_category就行了，对！没错就这么用！让程序自己判断用哪个函数！！

具体实现：调用

1 template <class InputIterator ,class Distance>
2 inline void advance(InputIterator& i，Distance n)
3 {
4     _advance(i, n, iterator_traits<InputIterator>::iterator_category());
5 }

1 template<class I>
2 struct iterator_traits 
3 {
　　　 ......　
4     typedef typename I::iterator_category iterator_category;
5 };