Iterator Traits作用与规范
为了能获取迭代器所指之物的类型、迭代器类型等信息,STL标准规定任何迭代器都应提供五个内嵌相应型别。
五个型别为:
- value type 迭代器所指对象型别;
- difference type 两个迭代器间的距离;
- reference type 引用;
- pointer type 指针;
- iterator_category 迭代器类型.
迭代器类型:
- Input Iterator 只读;
- Output Iterator 唯写;
- Forward Iterator 允许写入型算法( 如replace() )进行读写操作;
- Bidirectional Iterator 可以双向移动;
- Random Access Iterator 前三种迭代器仅支持operator++,第四种还支持operator–。此类型迭代器支持所有指针算数能力,如p + n, p - n, p[n], p1 - p2, p1 > p2.
STL提供了类似于以下的iterator class,设计新的迭代器时继承它就符合规范
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&> struct iterator { typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; };
|
如上篇中的list iterator,应写为
1 2 3 4
| template <class Item> class ListIter: public std::iterator<std::forward_iterator_tag, Item> {...}
|
编写iterator_traits
以value_type为例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| template <class I> struct iterator_traits { typedef typename I::value_type value_type; };
template <class T> struct iterator_traits<T*> { typedef T value_type; };
template <class T> struct iterator_traits<const T*> { typedef T value_type; };
|
如果要使用迭代器所指对象的类型,可以这样做
1 2 3 4
| template <class I> typename iterator_traits<I>::value_type func(I iter) { return *iter; }
|
iterator_traits应用
再举一iterator_category例说明traits的应用
advance()函数
1 2
| template <class InputIterator, class Distance> inline void advance(InputIterator &i, Distance n);
|
advance()函数接受一个迭代器p和一个数值n,将p前进n距离。由于五种迭代器性质不同,advance()函数在接收不同迭代器时应采取不同的方法来达到更好的效果,因此需要获得迭代器类型
标记型别
1 2 3 4 5 6
| 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 { };
|
编写重载函数
我们想要类似以下效果
1 2 3 4 5 6 7
| template <class InputIterator, class Distance> inline void advance(InputIterator &i, Distance n) { if(typeid(typename iterator_traits<InputIterator>::iterator_category) == typeid(random_access_iterator_tag)) }
|
但这样不仅无法通过编译,而且将可以在编译器完成的工作延后到运行期
正确的做法是使用一组重载函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| template <class InputIterator, class Distance> inline void __advance(InputIterator &i, Distance n, input_iterator_tag) { while(n--) ++i; }
template <class InputIterator, class Distance> inline void __advance(InputIterator &i, Distance n, bidirectional_iterator_tag) { if(n >= 0) while(n--) ++i; else while(n++) --i; }
template <class InputIterator, class Distance> inline void __advance(InputIterator &i, Distance n, random_access_iterator_tag) { i += n; }
|
forward型迭代器移动方式与input相同,由于继承关系,forward迭代器会转到执行input的重载函数,因此可缺省。
最后,让advance函数转调用
1 2 3 4 5 6
| template <class InputIterator, class Distance> inline void advance(InputIterator &i, Distance n) { __advance(i, n, typename iterator_traits<InputIterator>::iterator_category()); }
|
traits技术主要用于增强C++未能提供的关于型别认证方面的能力
参考:
- Effective C++ Item 47: 使用traits classes表现类型信息
- STL源码剖析 第三章 迭代器概念与 traits 编程技法