迭代器榨汁机
template<typename I>
struct iterator_traits{
typedef typename I::iterator_category
typedef typename I::value_type;
typedef typename I::difference_type;
typedef typename I::pointer;
typedef typename I::reference;
}
迭代器型别
迭代器型别之一：value_type
value_type 是指对象的型别，每一个打算与STL算法完美搭配的class，都应该定义自己的value_type内嵌型别。-
迭代器型别之二：difference_type
difference_type用来表示2个迭代器的距离，因此它可以用来表示容器的最大容量。通常STL中泛型算法提供的计数功能功能，例如STL中的count()。template <typename I, typename T> typename iterator_traits<I>::difference_type count( I first, I last, count T& value){ typename iterator_traits<I>::difference_type n = 0; for (; first != last; first++) if (*first == value) ++n; return n; } -
迭代器相应型别之三：reference_type
迭代器所指之物的内容是否允许改变， 迭代器分为2类，- 不允许改变“所指对象之内容者”称为constant iterators 例如 const int* pic。
- 允许改变“所指对象之内容者” 称为mutable iterators，例如int *pi。
提领constant iterators是一个右值。提领mutable iterators是一个左值。
-
迭代器相应型别之四：pointer type
reference_type 表示迭代器所指之物，那么pointer type则表示迭代器所指之物的地址。// 针对原生指针而设计的"偏特化版" template <typename T> struct iterator_traits<T*> { ...... typedef T* pointer; typedef T& reference; } // 针对原生的pointer-to-const而设计的"偏特化" template <typename T> struct iterator_traits<const T*> { ...... typedef T* pointer; typedef T& reference; } -
迭代器相应型别之五：Iterator_category
根据移动特性与施行操作迭代器被分为5类- Input Iterator：这种迭代器所指的对象，不允许外界改变，只读。
- Output Iterator：只写
- Forward Iterator：允许写入型算法在此种迭代器所形成的区间上进行读写操作。
- Bidirectional Iterator：可双向移动，某些算法需要逆向走访某个区间。
- Random AccessIterator：前4种迭代器只提供一部分指针算术能力，(前3种支持operator++，第4种支持operator--)，第5种则涵盖所有指针算术能力。
为什么需要区分这么多的迭代器种类？因为我们在设计算法时，应该针对某种强化的迭代器提供另一种定义，这样才能提供最大的效率。
任何一个迭代器，其类型应该落在"该迭代器所隶属的各种类型中，最强化的那个"，例如，int* 既是RandomAccess Iterator，又是Bidirectional Iterator，同时也是Forward Iterator，而且也是Input Iterator，那么其类型应该归属为random_access_iterator。
比如以advanced()为例.
template <typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n){
while(n--)
++i;
}
template <typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n){
if (n >= 0)
while(n--)
++i;
else
while(n++)
--i;
}
template <typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator& i, Distance n){
i += n;
}
template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n){
if (is_random_access_iterator(i)) // 有待实现。
advanced_RAI(i, n);
}
像在advanced中，通过判断不同迭代器类型来调用不同的函数。第一种方法是多态，但运行期才确定未免成本太高，同时胡乱继承多态也是把问题复杂化。第二种就是函数重载，我们可以事先标记不同迭代器类型，
并将其作为第3个参数传给advanced。
// 以下只做标记迭代器category之用
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 { };
template <typename InputIterator, typename Distance>
inline void advance(InputIterator &iter, Distance n){
typedef typename iterator_traits<InputIterator>::iterator_category category;
__advance(iter, n, category());
}
template <typename RandomAccessIterator, typename Distance>
void __advance(RandomAccessIterator iter, Distance n, random_access_iterator_tag){
iter += n;
}
template <typename InputIterator, typename Distance>
void __advance(InputIterator iter, Distance n, input_iterator_tag){
while(n--)
iter++;
}
template <typename BidirectionalIterator, typename Distance>
void __advance(BidirectionalIterator iter, Distance n, bidirectional_iterator_tag){
if (n >= 0)
while(n--)
iter++;
else
while(n++)
iter--;
}
__advanced中的第三个参数仅仅是激活重载。但我们还需要一个提供上层统一的接口，在这一层中通过traits机制，将迭代器类型推导出来。
