Extra Cookie

Yet Another Programmer's Blog

从 Concept 到 Iterator_traits

1
2
3
4
5
6
7
template <class Iterator, class T>
Iterator find(Iterator first, Iterator last, const T& value)
{
    while (first != last && *first != value)
        ++first;
    return first;
}

上面是 C++ 中一个普通的模板函数,调用的时候直接将特定类型变量当参数传入就行,这段程序运用了 Generic Programming(泛型编程/GP)。

GP 要求函数尽量一般化,假设参数可适用于任何范畴,那么函数 find 到底有多一般化?

输入条件,对于类型 Iterator,首先能够以 operator “*” 来操作提取其指向区域的值,并且可以用 operator “++” 来移至下一个 Iterator 对象…

为了表示输入条件,假定 Iterator 必须是一个 iterator,在这个地方 iterator 没有其他意思,只是我们定义出来的一个概念,用来指定一组描述某个类型的条件。

而这便是 GP 里面非常重要的 concept,当某一个类型满足所有这样的条件,我们便说它是该 concept 的一个 model,比如 char * 便是 iterator 的 model。不过需要注意,concept 不是类,变量,更不是 template 参数,事实上它不是任何可以能直接在 C++ 中呈现的东西。

我们可以想象 concept 为一组类型条件,如果说类型 T 是 concept C 的一个 model,那么 T 满足所有 C 的条件。也可以把 concept 想象成类型的集合,比如 iterator concept 就包含了 char *, int * 等类型,如果类型 T 是 concept C 的 model,则 T 属于 C 所代表的类型集合。

对于 find 函数,似乎我们需要定义 Iterator 为一个 concept,用来表示泛型指针,但是考虑到不同的算法只依赖泛型指针中很小的子集,将其划分为五个不同的 concept,Input Iterator(只读),Output Iterator(只写),Forward Iterator(读写),Bidirectional Iterator(双向移动),Random Access Iterator(随机读取),详细描述请点击。

每个 iterator 都有一个相关联的类型,即 iterator 指向某物的类型,称之为 value type。为什么需要这个类型呢?

因为在特定算法中,需要定义一些临时变量,类型为 iterator 指向的某物的类型,即 iterator 的 value type,我们该怎么做?

1
2
3
4
5
6
7
8
9
10
11
template <class Iterator, class T>
void implement(Iterator iter, T t)
{
    T temp;
}

template <class T>
void function(T iter)
{
    implement(iter, *iter);
}

function() 成为一个单独的传递函数,并将所有的工作委托给 implement() 函数。

这算是一个方法,如果我们只需要声明临时变量,虽然实现起来笨拙但可用,但如果需要用来声明函数返回值,便回天无力了。

1
2
3
4
5
6
template <class Type>
struct Iterator
{
    typedef Type value_type;
    Type *pointer;
};

第二种方法,在 iterator 类中嵌套定义 value type, 通过 typename Iterator::value_type 便可以取出类型,但是那些满足 concept iterator 的基本类型怎么办?比如 int *,我们无法把 Iterator::value_type 定义为 int

看来在 iterator 中声明嵌套类型依然不妥。那么单独定义一个 class 来处理这个问题,行不?

1
2
3
4
5
template <class Iterator>
struct iterator_traits
{
    typedef typename Iterator::value_type value_type;
};

我们可以使用诸如此类语句提取类型: iterator_traits<int *>::value_type; 而一些细节问题,例如 const int *,可以借助 template 的 partial specification 轻松的解决。

Iterator 主要应用于算法中需要遍历的场合,遍历中需要知道整个区域的 range 大小,而这个区间的大小是未知的,选择什么类型来存储便是一个问题,比如大数超过 int 最大值,却用 int 来存储,便会不够。模仿 value type:

1
2
3
4
5
6
template <class Iterator>
struct iterator_traits
{
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::difference_type difference_type;
}

同上,我们可以非常容易的实现 reference type 和 pointer type traits。

前面提到过,Iterator 分为五个 concepts,对于同一个算法,有时候不止一个 concept 成立,需要在此提一下 refinement 这个概念。

举个例子,Random Access Iterator 满足 Forward Iterator 的所有条件,即 Random Access Iterator 的任何 model 必定是 Forward Iterator 的 model,我们将这样的关系成为 refinement,如果 concept C2 提供 concept C1 的所有功能,再加上其他额外功能,则 C2 便是 C1 的 refinement。如果一个算法要求参数类型是 C1 的 model,那么传给它一个 C2 model 类型也是可以正常工作的。

正是因为有 refinement 的存在,有些算法为了效率的提高,会针对不同的 refinement concept 设计不同的实现,比如获取当前 iterator 后第 N 个 iterator,对于 Input Iterator 来说,只能一个一个遍历,但对于 Random Access Iterator,就可以直接 +N 就行了。

1
2
3
4
5
6
7
8
template <class InputIterator, class Distance>
void go_to(InputIterator &i, Distance n)
{
    if(is_random_access_iterator(i))
        goto_random(i, n);
    if(is_input_iterator(i))
        goto_input(i, n);
}

这的确是个很糟的实现,因为是一直等到运行期才进行选择,太慢了,如果能在编译时就确定好算法版本,就很好了。如何实现同一个函数多种不同实现呢?

当然是重载了!

为每一个算法函数加一个参数,用来指明该算法的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class InputIterator, class Distance>
void go_to(InputIterator &i, Distance n, input_iterator_tag)

{
    goto_input(i, n);
}

template <class RandomAccessIterator, class Distance>
void go_to(RandomAccessIterator &i, Distance n, random_iterator_tag)

{
    goto_random(i, n);
}

这个参数可以称之为 iterator_category,同样可以借用 value_type 的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template <class Iterator>
struct iterator_traits
{
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
};

template <class T>
struct iterator_traits<T*>
{
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
};

template <class T>
struct iterator_traits<const T*>
{
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
};

上面便是整个 iterator_traits 的实现,如果需要自己定义新的 iterator class,那就得在这个 class 中定义五个嵌套类型 iterator_category, value_type, difference_type, pointer, reference, 要不然,就必须像上面 T *const T* 那样,对 iterator_traits 进行 partial specification。

Comments