STL学习笔记（2）迭代器（iterators）概念与traits编程技法

0：

STL思想：将数据容器(containers)和算法(algorithms)分开，再撮合在一起。
迭代器(iterator,扮演粘胶角色 )：提供一种方法，使之能够依序寻访某个聚合物（容器）所含的各个元素，而又无需暴漏该聚合物的内部表述方式。

1. 迭代器(iterator)是一种smart pointer(智能指针)

所以迭代器最重要的工作是对 operator*和对operator->进行重载。
为了完成迭代的作用还要对前置、后置的++还有部分的–进行重载。

举例，我们先对一个链表进行简单实现：

// file : mylist.h
#ifndef MYLIST_H
#define MYLIST_H
#include <iostream>
using namespace std;

template <typename T>
class List {//链表
public:
	void insert_front(T value);
	void insert_end(T value);
	void display(ostream &os = cout) const;
	// ...
private:
	ListItem<T> *_end;
	ListItem<T> *_front;
	long _size;
};


template<typename T>
class ListItem {//节点
public:
	T value() const { return _value; }
	ListItem* next() const { return _next; }
	bool operator!=(const ListItem<T>& item, T n) {
		return item.value() != n;
	}
	// ...
private:
	T _value;
	ListItem *_next;
};

#endif

然后我们为这个链表设计一个迭代器雏形：

// file : "mylist_iter.h"
#ifndef MYLIST_ITER_H
#define MYLIST_ITER_H

#include "mylist.h"
template<class Item>
struct ListIter {//只为链表服务的节点，重点是++
	Item* ptr;

	ListIter(Item *p = 0) :ptr(p) {}

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

	ListIter& operator++() {//前置
		ptr = ptr->next();
		return *this;
	}
	ListIter operator++(int){//后置
		ListIter temp = *this;
		++*this;
		return temp;
	}

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

这样我们就可以通过写好的迭代器雏形黏合List容器和find()算法。

ListIter<ListItem<int> > begin( mylist.front() );
ListIter<ListItem<int> > end; //default 0,null
ListIter<ListItem<int> > iter; //default 0,null
iter = find(begin, end, 3);
if(iter == end)
	cout<< "not found" << endl;

2 迭代器与trait，相应类型与萃取

迭代器所指对象的类别称为迭代器的value type , 是迭代器的相应型别( associated types ) 的其中之一。
常用的相应型别有五种：

value type ：所指对象的类型
difference type ：迭代器距离类型原生指针是ptrdiff_t
pointer ：指向迭代器所指植物的指针
reference ：所指对象的类型的引用
iterator category ：
获得相应型别的方式是使用声明内嵌型别（ typename I::value_type）与特性萃取器（trait），同时利用偏特化得到原生指针版本。
举个简单的使用例子，我们先定义一个迭代器和萃取器。

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>
struct iterator_traits{
	typedef typename I::value_type value_type;
}

这样我们就可以方便的时候迭代器所指类型了

template <class I>
typename iterator_traits<I>::value_type  //这一行都是返回值类型
func(I ite){
	return *ite
}

其实我们可以发现，在本例中不用萃取器，将typename iterator_traits<I>::value_type改为typename I::value_type也是可以使用的，但是原生指针类型是没有定义value_type的，也就是说这样将无法适用于任何情况，比如const int*和int*。
为了完成这一目的，我们必须使用一层间接性的萃取器并对萃取器进行偏特化。

template <class I>
struct iterator_traits{ //全特化型，适合于所有自定义类型
	//迭代器中必须定义这些相应类别
	typedef typename I::value_type value_type;
	typedef typename I::iterator_category iterator_category;
	typedef typename I::difference_type difference_type;
	typedef typename I::pointer pointer;
	typedef typename I::reference reference;
}

template <class I>
struct iterator_traits<I*>{//原生pointer的偏特化版本
	typedef I value_type;
	typedef ptrdiff_t difference_type;
	typedef I* pointer;
	typedef I& reference;
	typedef random_access_iterator_tag iterator_category;
} 

template <class I>
struct iterator_traits<const I*>{//原生pointer-to-const的偏特化版本
	typedef I value_type;
	typedef ptrdiff_t difference_type;
	typedef const I* pointer;
	typedef const I& reference;
	typedef random_access_iterator_tag iterator_category;
}

重点再解释一下关于迭代器的第五个相应型别：iterator_category,表示的迭代器根据其移动特性和实施操作而被分成的五种类型：

Input_Iterator :　所指对象不允许外界改变，即只读。只支持operator++；
Ｏutput_Iterator : z只写。只支持operator++；
Forward_Iterator : 允许“写入型算法”在此种迭代器区间上读写。只支持operator++；
Bidirectional_Iterator : 支持双向移动，支持operator++和operator–；
Random_Access_Iterator :　支持所有指针算术能力，可进行随机访问，随意移动指定的步数包括operator++、operator–、p+n、p-n、p[n]、p1-p2、p1<p2等。

迭代器之间的分类从属和概念强化关系可看下图：

我们定义了5个class代表这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  {  };

值得强调的是，对于一个迭代器来说，其类型应该是该迭代器所属的各种类型之中最强化的一个 ; 而对于STL算法来说，其迭代器参数类型应该用算法所能接受的最低阶迭代器类型来为其型别参数命名（因为有继承、多态，在没有高阶参数重载时，低阶仍可以调用）。

假如编写advance(p, n)函数，它表示指定迭代器p移动n次。我们需要先编写不同迭代器p对应的重载函数__advance(p, n, tag() ),其调用的__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(ForwardIterator& i,Distance n, Forward_iterator_tag){
	__advance(i, n, input_iterator_tag() );
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& 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
}

然后我们就可以完成对外开放的上层控制接口advance

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

STL学习笔记（2）迭代器（iterators）概念与traits编程技法

0：

1. 迭代器(iterator)是一种smart pointer(智能指针)

2 迭代器与trait，相应类型 与 萃取

2 迭代器与trait，相应类型与萃取