0%

iterator traits

Iterator Traits作用与规范

为了能获取迭代器所指之物的类型、迭代器类型等信息,STL标准规定任何迭代器都应提供五个内嵌相应型别。

五个型别为:

  1. value type 迭代器所指对象型别;
  2. difference type 两个迭代器间的距离;
  3. reference type 引用;
  4. pointer type 指针;
  5. iterator_category 迭代器类型.

迭代器类型:

  1. Input Iterator 只读;
  2. Output Iterator 唯写;
  3. Forward Iterator 允许写入型算法( 如replace() )进行读写操作;
  4. Bidirectional Iterator 可以双向移动;
  5. 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
//std::iterator与此作用相同
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
//以value_type 为返回类型
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());
}
//模板参数命名为InputIterator是由于STL命名规范

traits技术主要用于增强C++未能提供的关于型别认证方面的能力


参考:

  • Effective C++ Item 47: 使用traits classes表现类型信息
  • STL源码剖析 第三章 迭代器概念与 traits 编程技法