Cybay
0%

iterator traits

发表于 分类于 Valine：
在迭代器中使用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 编程技法