如果一个迭代器要兼容stl，必须遵循约定，自行以内嵌型别定义的方式定义出相应型别。根据书中介绍，最常用到的迭代器型别有五种：value type,difference type, pointer, reference, iterator catagoly,如果你希望你开发的容器能与stl水乳交融，一定要为你的容器的迭代器定义这五种相应型别。
迭代器相应型别之一：value type
所谓value type 是指迭代器所指对象的型别。任何一个打算与stl算法有完美搭配的class， 都应该定义自己的value type内嵌型别。
迭代器型别之二：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)
{
typedef typename iterator_traits<I>::difference_type n = ;
for (;first != last; ++first)
if (*first == value)
++n;
return n;
}
针对相应型别difference type， 原生指针使用哪个类型呢？表示空间大小一般使用unsigned int，stl为原生指针定义的特化版本为：
//带内嵌类型的迭代器
template <class I>
struct iterator_traits
{
typedef typename I::difference_type difference_type;
};
//原生指针
template <class I>
struct iterator_traits<I*>
{
typedef ptrdiff_t difference_type;
};
//const 原生指针
template <class I>
struct iterator_traits<const I*>
{
typedef ptrdiff_t difference_type;
};
这样的话当我们任何时候需要使用迭代器的difference type,可以这么写：
typename iterator_traits<I>::difference_type
迭代器型别之三：reference type
在c++中，函数如果要传回左值，都是以by reference 的方式进行，所以如果p是一个迭代器，他的value type 是T，那么*p 应该是T&（即reference type）
迭代器的解引操作operator* 返回的就是reference type，为了能融合stl，我们的迭代器也必须要定义reference 内嵌型别
stl 为reference type设计了一般版本和偏特化版：
//一般带内嵌类型的迭代器
template <class I>
struct iterator_traits
{
typedef typename::I::reference reference;
};
//原生指针
template <class I>
struct iterator_traits<I*>
{
typedef I& reference;
};
//const 原生指针
template <class I>
struct iterator_traits<const I*>
{
typedef const I& reference;
};
迭代器型别之四：pointer type
即指针类型，也就是说我们可以返回一个指针，指向迭代器所指之物，STL设计如下：
//一般带内嵌类型的迭代器
template <class I>
struct iterator_traits
{
typedef typename::I::pointer pointer;
};
//原生指针
template <class I>
struct iterator_traits<I*>
{
typedef I* pointer;
};
//const 原生指针
template <class I>
struct iterator_traits<const I*>
{
typedef const I* pointer;
};
迭代器型别之五：iterator_category
讨论前必须先知道stl迭代器的分类：
input iterator：只读迭代器（++）
output iterator：只写迭代器（++）
forward iterator：可读写迭代器（++）
bidirectional iterator：可双向移动迭代器（++，--）
random access iterator：可随机访问迭代器（+n，-n）
设计算法时，如果可能，我们应该给入参迭代器提供明确的说明，如果算法需要input iterator 我们给个random access 的当然可以，但不是最贴切的。下面列出stl算法中使用各个iterator示例：
stl中使用 input iterator示例：
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
stl使用output iterator示例：
template <class OutputIterator, class Size, class T>
void fill_n (OutputIterator first, Size n, const T& val);
stl使用forward iterator示例：
template <class ForwardIterator, class T>
void replace (ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
stl使用bidirectional iterator示例：
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 move_backward (BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
stl使用random access iterator示例：
template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);
当我们在使用这些算法的时候，我们是直接使用iterator，并不明确指定自己传进去的是什么iterator
例如vector：
std::vector<int> myVector;
std::find(myVector.begin(), myVector.end(),);
这个begin和end返回的是什么类型的迭代器？
其实根据vector的数据结构我们可以推测是reandom access iterator，因为vector是连续内存结构，支持随机访问，stl对vector的begin函数返回值定义如下：
An iterator to the beginning of the sequence container. If the vector object is const-qualified, the function returns a const_iterator. Otherwise, it returns an iterator. Member types iterator and const_iterator are random access iterator types (pointing to an element and to a const element, respectively).
继续回到iterator_category上，假设我们要实现一个函数，入参为迭代器p和一个整形n，函数内将p累进n次，下面有三分定义：
//只读迭代器，只支持++
template <class InputIterator, class Distance>
void advance(InputIterator&p, Distance n)
{
while (n--) ++p;
} //双向迭代器，支持++、--
template <class BidirectionalIterator, class Distance>
void advance(BidirectionalIterator& p, Distance n)
{
if (n >= )
while (n--) ++p;
else
while (n++) --p;
} //随机访问迭代器，支持随机访问
template <class RandomAccessIterator, class Distance>
void advance(RandomAccessIterator& p, Distance n)
{
p += n;
}
现在当程序员要调用advance时，应该用哪个呢？如果你是一个vector，调用第二个定义，那么效率就下降了，如果我们把三个函数合并成一个，使用一个变量区分使用哪个函数，大概代码如下：
template <class InputIterator, class Distance>
void advance(InputIterator&p, Distance n, int type)
{
if (type===input)
...
else if (type==output)
...
else
...
}
这样做我们调用时还是要多传一个参数，但我们实际上并没有这样调用advance函数，stl利用重载实现：
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag{};
struct bidirectional_iterator_tag{};
struct random_access_iterator_tag{};
//为了表示是内部函数，我们以__开头
//只读迭代器，只支持++
template <class InputIterator, class Distance>
void __advance(InputIterator&p, Distance n, input_iterator_tag)
{
while (n--) ++p;
}
//双向迭代器，支持++、--
template <class BidirectionalIterator, class Distance>
void __advance(BidirectionalIterator& p, Distance n, bidirectional_iterator_tag)
{
if (n >= )
while (n--) ++p;
else
while (n++) --p;
}
//随机访问迭代器，支持随机访问
template <class BidirectionalIterator, class Distance>
void __advance(BidirectionalIterator& p, Distance n, random_access_iterator_tag)
{
p += n;
}
//对外统一接口：（这里有个疑问：统一接口中为什么入参是InputIterator? 既然设计的初衷是接受任何类型的迭代器，就不应该指定特定类型，我们甚至可以命名成T）
template <class InputIterator, class Distance>
void advance(InputIterator& p, Distance n)
{
__advance(p, n, iterator_traits<InputIterator>::iterator_category());
}
因此，为了满足上述行为，traits还要加一个型别：
//一般带内嵌类型的迭代器
template <class I>
struct iterator_traits
{
typedef typename::I::iterator_category iterator_category;
};
//原生指针,因为我们原生指针支持随机访问，所以要定义成random access
template <class I>
struct iterator_traits<I*>
{
typedef random_access_iterator_tag iterator_category;
};
//const 原生指针
template <class I>
struct iterator_traits<const I*>
{
typedef random_access_iterator_tag iterator_category;
};
这样我们的iterator就有了五种类型，我们的traits 也要萃取迭代器的这五种类型，这样才能完全融入stl，完整代码如下：
//自定义的迭代器必须定义的五种型别
template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator
{
typedef T value_type;
typedef Distance difference_type;
typedef Reference reference;
typedef Pointer pointer;
typedef Category iterator_category;
};
//把之前的五种合并在一个traits中
template <class Iterator>
struct iterator_traits
{
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename::Iterator::reference reference;
typedef typename::Iterator::pointer pointer;
typedef typename::Iterator::iterator_category iterator_category;
};
//原生指针偏特化版
template <class Iterator>
struct iterator_traits<T*>
{
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T& reference;
typedef T* pointer;
typedef random_access_iterator_tag iterator_category;
};
//const原生指针偏特化版
template <class Iterator>
struct iterator_traits<const T*>
{
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T& reference;
typedef const T* pointer;
typedef random_access_iterator_tag iterator_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&)
{
typedef typename iterator_traits<iterator>::difference_type difference;
return difference();
} //定义一个函数，获取迭代器的value_type
template <class Iterator>
inline typename::iterator_traits<Iterator>::value_type value_type(const Iterator&)
{
typedef typename iterator_traits<iterator>::value_type value;
return value();
}
//或者返回value_type*
template <class Iterator>
inline typename::iterator_traits<Iterator>::value_type* value_type(const Iterator&)
{
typedef typename iterator_traits<iterator>::value_type* value;
return value;
}