泛型编程和 STL笔记及思考.
这篇文章主要记录在 STL 中迭代器设计过程中出现的编程技巧, 围绕的 STL 主题为 (迭代器特征) Iterator traits 和 相关类型(Associated Types).
首先介绍 Associated Types
Associated Types
我们知道, Iterator 是一种泛化的指针, 我们有时会这样理解它:
指针 (广义的) 指向某个序列的一个 item, 而每个 item 的类型就是我们想要的 Associated Types.
对于 C 中的指针来说,*ptr 就是他的相关类型.
对于我们之前定义的外覆类 (C++ 泛型算法 find 那篇) 来说,*int_node (即 Node)是他的相关类型.
现在我们有个问题, 我们如何使用这个类型? 假设有一个 Iterator type P,P 的相关类型为 value_type. 我们想要在一些算法中使用这个类型声明一些临时变量(这很常见, 比如在计算数值的算法内), 然而 "P 的 value_type" 并没有告诉我们 C++ 如何表达这样的概念. 比如在之前的外覆类中, 我们可以通过外覆类的接口获得他的相关类型的具体引用, 但是却没办法使用这个类型信息用于外覆类之外的变量的声明.
技巧一 : 使用 C++ 的类型推断机制
假设有个泛型函数 f() , 需要一个类型为 P 的参数, 而且还需要声明一个类型为 P 的 value_type 的临时变量. 我们可以令 f() 成为一个单纯的传递函数, 并将所有工作委托给内部函数 f_impl():
- template <class P,class T>
- void f_impl(P iter,T t) {
- T tmp;
- ...
- }
- template <class T> inline void f(T iter) {
- f_impl(iter,*iter);
- }
于是, 我们可以在函数 f_impl 之中, 声明一个类型为 T 也即 P 的 value_type 类型的临时变量. template 参数的 "type inference" 机制是自动自发的, 所以在 f_impl 之中, template 的参数 T 和 *iter 是同义的.
这个技巧的确能够解决我们之前提出的问题, 但是, 他却解决不了另一个问题, 这个方案无法用来声明函数的返回类型. 通过类型推导得到的 Associated Type 信息是在 f() 方法内获得的, 我们无法将这个 Associated Type 用于函数的返回值. 所以我们来看一下技巧二.
技巧二 : 嵌套声明
这种方法的核心思想是在每个迭代器类中将具体的 Associated Type 统一定义为一个新的名为 value_type(又一次的隐藏了差异性)的类型.
用上一篇定义的外覆类 int_node 为例, 为它增加一个新的类型 value_type:
- template <class Node> //Node 是类型参数, 可能用 T 更好理解
- struct node_wrap {
- typedef Node value_type;
- Node *ptr;
- ...
- };
这样的话, 只要我们知道这个迭代器的类名, 便可以访问他的 Associated Type . 并且, 在每个定义了 value_type 的迭代器都可以换通过相同的方法访问.
对于声明一个 node_wrap 的 Associated Type 类型的变量, 我们可以这样:
typename node_wrap :: value_type tmp;
以这种方式来对变量命名.(typename 是为了向编译器指出这是类型名而不是成员方法名或其他)
声明函数的返回类型:
- typename node_wrap:: value_type f(...) {
- ...
- }
这样做相当于我们再次将差异性隐藏, 向外提供了一个统一的接口.
看起来这种方式解决了我们的问题. 但是我们忽略了一些情况. 上述成立的前提是迭代器是一个类, 所以我们可以在它们内部增加一个新的类型, 并从外部访问它. 但是 C 中的指针也是一个迭代器, 而且我们一直是在以 C 指针的行为来指导迭代器的行为. 显然我们无法为 C 指针提供这种操作. 为了解决这个问题, 为指针也提供合适的操作, 我们再次提出了新的方案.
技巧三 : 增加中间层和模板偏特化
我们可以增加一个中间层来解决这个问题. 具体的做法是定义一个辅助用的 class,iterator_traits:
- template <class Iterator>
- struct iterator_traits {
- typedef typename Iterator::value_type value_type;
- };
这么一来我们就可以以这样的写法来取用 Iterator 的 value_type(以声明变量为例):
typename iterator_traits<node_wrap>::value_type tmp;
这看起来没有任何改进, 因为 Iterator_traits 仍然假设它的 template 参数 Iterator 有一个嵌套类型.(指针仍然没有)
不过, 现在我们可以使用另一种技术来解决这个问题了. 我们将利用 "对某种 template 参数提供另一种定义" 的方法, 将 Iterator_traits class 特化.
C++ 中允许 template 的全特化 (亦即为某型别如 int* 提供另一种定义) 和偏特化(亦即提供另一个定义, 其自身仍为模板化的. 具体可参考 C++ primer). 在这个例子中, 我们需要针对每一种指针类型做出另一种定义, 因此我们需要偏特化:
- template <class T>
- struct iterator_traits<T*> {
- typedef T value_type;
- };
现在, 当我们面对普通的指针时, 也可以像对待迭代器一样, 使用相同的方法来取用它的 Associated Type.
主要的问题已经解决了, 但是还有一个细节问题需要提出来讨论一下: constant iterator 的 value_type 是什么? 考虑如下例子:
iterator_traits<const int*>::value_type
根据我们之前定义的 Iterator_traits value_type 将会是 const int 而非 int. 我们已经针对 T* 的参数将 iterator_traits 特化, 但当 T 是 const int 时, const int * 会符合 T* , 这不是我们期待的结果.
我们只需要另外设计一个版本的偏特化, 就能轻而易举的解决这个问题:
- template<class T>
- struct iterator_traits<cosnt T*> {
- typedef T value_type;
- };
现在我们有了三种不同的 itertaor_traits 版本. 一个是针对类型为 T 的参数, 一个是 T * , 另一个是 const T * 的参数. 当你写下 iterator_traits<const int*> 时, 原则上他符合任何一个版本, 不会有歧义的情况发生. 因为 C++ 编译器总能选出最能明确匹配的版本.
直到到现在, 我们有了某种机制, 让我们得以使用某个 iterator 的 value_type 来撰写算法.
举个例子, 以下的泛型函数用来计算 nonempty range 内的数值总和:
- template <class InputIterator>
- typename iterator_traits<InputIterator>::value_type
- sum_nonempty(InputIterator first,InputIterator last) {
- typename iterator_traits<InputIterator>::value_type result = *first;
- for (;first != last; ++first)
- result += *first;
- return result;
- }
来源: https://www.cnblogs.com/backwords/p/9327120.html