从 concept 到 iterator_traits

Posted on 
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。