WEB开发网
开发学院软件开发C++ C++箴言:为类型信息使用特征类 阅读

C++箴言:为类型信息使用特征类

 2008-03-08 22:03:26 来源:WEB开发网   
核心提示:STL 主要是由 containers(容器),iterators(迭代器)和 algorithms(算法)的 templates(模板)构成的,C++箴言:为类型信息使用特征类,但是也有几个 utility templates(实用模板),其中一个被称为 advance,它们使用 templates(模板)和 tem

  STL 主要是由 containers(容器),iterators(迭代器)和 algorithms(算法)的 templates(模板)构成的,但是也有几个 utility templates(实用模板)。其中一个被称为 advance。advance 将一个指定的 iterator(迭代器)移动一个指定的距离:

template// move iter d units
void advance(IterT& iter, DistT d); // forward; if d < 0,
// move iter backward

  在概念上,advance 仅仅是在做 iter += d,但是 advance 不能这样实现,因为只有 random access iterators(随机访问迭代器)支持 += Operation。不够强力的 iterator(迭代器)类型不得不通过反复利用 ++ 或 -- d 次来实现 advance。

  你不记得 STL iterator categories(迭代器种类)了吗?没问题,我们这就做一个简单回顾。对应于它们所支持的操作,共有五种 iterators(迭代器)。input iterators(输入迭代器)只能向前移动,每次只能移动一步,只能读它们指向的东西,而且只能读一次。它们以一个输入文件中的 read pointer(读指针)为原型;C++ 库中的 istream_iterators 就是这一种类的典型代表。output iterators(输出迭代器)与此类似,只不过用于输出:它们只能向前移动,每次只能移动一步,只能写它们指向的东西,而且只能写一次。它们以一个输出文件中的 write pointer(写指针)为原型;ostream_iterators 是这一种类的典型代表。这是两个最不强力的 iterator categories(迭代器种类)。因为 input(输入)和 output iterators(输出迭代器)只能向前移动而且只能读或者写它们指向的地方最多一次,它们只适合 one-pass 运算。

  一个更强力一些的 iterator category(迭代器种类)是 forward iterators(前向迭代器)。这种 iterators(迭代器)能做 input(输入)和 output iterators(输出迭代器)可以做到的每一件事情,再加上它们可以读或者写它们指向的东西一次以上。这就使得它们可用于 multi-pass 运算。STL 没有提供 singly linked list(单向链表),但某些库提供了(通常被称为 slist),而这种 containers(容器)的 iterators(迭代器)就是 forward iterators(前向迭代器)。TR1 的 hashed containers(哈希容器)的 iterators(迭代器)也可以属于 forward category(前向迭代器)。

  bidirectional iterators(双向迭代器)为 forward iterators(前向迭代器)加上了和向前一样的向后移动的能力。STL 的 list 的 iterators(迭代器)属于这一种类,set,multiset,map 和 multimap 的 iterators(迭代器)也一样。

  最强力的 iterator category(迭代器种类)是 random access iterators(随机访问迭代器)。这种 iterators(迭代器)为 bidirectional iterators(双向迭代器)加上了 "iterator arithmetic"(“迭代器运算”)的能力,也就是说,在常量时间里向前或者向后跳转一个任意的距离。这样的运算类似于指针运算,这并不会让人感到惊奇,因为 random access iterators(随机访问迭代器)就是以 built-in pointers(内建指针)为原型的,而 built-in pointers(内建指针)可以和 random access iterators(随机访问迭代器)有同样的行为。vector,deque 和 string 的 iterators(迭代器)是 random access iterators(随机访问迭代器)。

  对于五种 iterator categories(迭代器种类)中的每一种,C++ 都有一个用于识别它的 "tag strUCt"(“标签结构体”)在标准库中:

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 {};

  这些结构体之间的 inheritance relationships(继续关系)是正当的 is-a 关系:所有的 forward iterators(前向迭代器)也是 input iterators(输入迭代器),等等,这都是成立的。我们不久就会看到这个 inheritance(继续)的功用。

  但是返回到 advance。对于不同的 iterator(迭代器)能力,实现 advance 的一个方法是使用反复增加或减少 iterator(迭代器)的循环的 lowest-common-denominator(最小共通特性)策略。然而,这个方法要花费 linear time(线性时间)。random access iterators(随机访问迭代器)支持 constant-time iterator arithmetic(常量时间迭代器运算),当它出现的时候我们最好能利用这种能力。

  我们真正想做的就是大致像这样实现 advance:

template
void advance(IterT& iter, DistT d)
{
 if (iter is a random access iterator) {
  iter += d; // use iterator arithmetic
 } // for random access iters
 else {
  if (d >= 0) { while (d--) ++iter; } // use iterative calls to
  else { while (d++) --iter; } // ++ or -- for other
 } // iterator categories
}

  这就需要能够确定 iter 是否是一个 random access iterators(随机访问迭代器),依次下来,就需要知道它的类型,IterT,是否是一个 random access iterators(随机访问迭代器)类型。换句话说,我们需要得到关于一个类型的某些信息。这就是 traits 让你做到的:它们答应你在编译过程中得到关于一个类型的信息。 traits 不是 C++ 中的一个要害字或预定义结构;它们是一项技术和 C++ 程序员遵守的惯例。建立这项技术的要求之一是它在 built-in types(内建类型)上必须和在 user-defined types(用户定义类型)上一样有效。例如,假如 advance 被一个指针(譬如一个 const char*)和一个 int 调用,advance 必须有效,但是这就意味着 traits 技术必须适用于像指针这样的 built-in types(内建类型)。

  traits 对 built-in types(内建类型)必须有效的事实意味着将信息嵌入到类型内部是不可以的,因为没有办法将信息嵌入指针内部。那么,一个类型的 traits 信息,必须在类型外部。标准的方法是将它放到 template(模板)以及这个 template(模板)的一个或更多的 specializations(特化)中。对于 iterators(迭代器),标准库中 template(模板)被称为 iterator_traits:

template// template for information about
struct iterator_traits; // iterator types

  就像你能看到的,iterator_traits 是一个 struct(结构体)。根据惯例,traits 总是被实现为 struct(结构体)。另一个惯例就是用来实现 traits 的 structs(结构体)以 traits classes(这可不是我捏造的)闻名。

  iterator_traits 的工作方法是对于每一个 IterT 类型,在 struct(结构体)iterator_traits中声明一个名为 iterator_category 的 typedef。这个 typedef 被看成是 IterT 的 iterator category(迭代器种类)。

  iterator_traits 通过两部分实现这一点。首先,它强制要求任何 user-defined iterator(用户定义迭代器)类型必须包含一个名为 iterator_category 的嵌套 typedef 用以识别适合的 tag struct(标签结构体)。例如,deque 的 iterators(迭代器)是随机访问的,所以一个 deque iterators 的 class 看起来就像这样:

template < ... >// template params elided
class deque {
 public:
  class iterator {
   public:
    typedef random_access_iterator_tag iterator_category;
    ...
  };
 ...
};

  然而,list 的 iterators(迭代器)是双向的,所以它们是这样做的:

template < ... >
class list {
 public:
 class iterator {
  public:
  typedef bidirectional_iterator_tag iterator_category;
  ...
 };
 ...
};

  iterator_traits 仅仅是简单地模拟了 iterator class 的嵌套 typedef:

// the iterator_category for type IterT is whatever IterT says it is;
// see Item 42 for info on the use of "typedef typename"
template
struct iterator_traits {
 typedef typename IterT::iterator_category iterator_category;
 ...
};

  这样对于 user-defined types(用户定义类型)能很好地运转。但是对于本身是 pointers(指针)的 iterators(迭代器)根本不起作用,因为不存在类似于带有一个嵌套 typedef 的指针的东西。iterator_traits 实现的第二个部分处理本身是 pointers(指针)的 iterators(迭代器)。
  为了支持这样的 iterators(迭代器),iterator_traits 为 pointer types(指针类型)提供了一个 partial template specialization(部分模板特化)。pointers 的行为类似 random access iterators(随机访问迭代器),所以这就是 iterator_traits 为它们指定的种类:


template// partial template specialization
struct iterator_traits// for built-in pointer types
{
 typedef random_access_iterator_tag iterator_category;
 ...
};

  到此为止,你了解了如何设计和实现一个 traits class:

  ·识别你想让它可用的关于类型的一些信息(例如,对于 iterators(迭代器)来说,就是它们的 iterator category(迭代器种类))。

  ·选择一个名字标识这个信息(例如,iterator_category)。

  ·提供一个 template(模板)和一系列 specializations(特化)(例如,iterator_traits),它们包含你要支持的类型的信息。

  给出了 iterator_traits ——实际上是 std::iterator_traits,因为它是 C++ 标准库的一部分——我们就可以改善我们的 advance 伪代码:

template
void advance(IterT& iter, DistT d)
{
 if (typeid(typename std::iterator_traits::iterator_category) ==
  typeid(std::random_access_iterator_tag))
 ...
}

  这个虽然看起来有点希望,但它不是我们想要的。在某种状态下,它会导致编译问题,这个问题我们以后再来研究它,现在,有一个更基础的问题要讨论。IterT 的类型在编译期间是已知的,所以 iterator_traits::iterator_category 可以在编译期间被确定。但是 if 语句还是要到运行时才能被求值。为什么要到运行时才做我们在编译期间就能做的事情呢?它浪费了时间(严格意义上的),而且使我们的执行码膨胀。

  我们真正想要的是一个针对在编译期间被鉴别的类型的 conditional construct(条件结构)(也就是说,一个 if...else 语句)。碰巧的是,C++ 已经有了一个得到这种行为的方法。它被称为 overloading(重载)。

  当你重载某个函数 f 时,你为不同的 overloads(重载)指定不同的 parameter types(形参类型)。当你调用 f 时,编译器会根据被传递的 arguments(实参)挑出最佳的 overload(重载)。基本上,编译器会说:“假如这个 overload(重载)与被传递的东西是最佳匹配的话,就调用这个 f;假如另一个 overload(重载)是最佳匹配,就调用它;假如第三个 overload(重载)是最佳的,就调用它”等等。看到了吗?一个针对类型的 compile-time conditional construct(编译时条件结构)。为了让 advance 拥有我们想要的行为方式,我们必须要做的全部就是创建一个包含 advance 的“内容”的重载函数的多个版本(此处原文有误,根据作者网站勘误修改——译者注),声明它们取得不同 iterator_category object 的类型。我为这些函数使用名字 doAdvance:

template// use this impl for
void doAdvance(IterT& iter, DistT d, // random access
std::random_access_iterator_tag) // iterators
{
 iter += d;
}

template// use this impl for
void doAdvance(IterT& iter, DistT d, // bidirectional
std::bidirectional_iterator_tag) // iterators
{
 if (d >= 0) { while (d--) ++iter; }
 else { while (d++) --iter; }
}

template// use this impl for
void doAdvance(IterT& iter, DistT d, // input iterators
std::input_iterator_tag)
{
 if (d < 0 ) {
  throw std::out_of_range("Negative distance"); // see below
 }
 while (d--) ++iter;
}

  因为 forward_iterator_tag 从 input_iterator_tag 继续而来,针对 input_iterator_tag 的 doAdvance 版本也将处理 forward iterators(前向迭代器)。这就是在不同的 iterator_tag structs 之间继续的动机。
(实际上,这是所有 public inheritance(公有继续)的动机的一部分:使针对 base class types(基类类型)写的代码也能对 derived class types(派生类类型)起作用。)

  advance 的规范对于 random access(随机访问)和 bidirectional iterators(双向迭代器)答应正的和负的移动距离,但是假如你试图移动一个 forward(前向)或 input iterator(输入迭代器)一个负的距离,则行为是未定义的。在我检查过的实现中简单地假设 d 是非负的,因而假如一个负的距离被传入,则进入一个直到计数降为零的非常长的循环。在上面的代码中,我展示了改为一个异常被抛出。这两种实现都是正确的。未定义行为的诅咒是:你无法预知会发生什么。

  给出针对 doAdvance 的各种重载,advance 需要做的全部就是调用它们,传递一个适当的 iterator category(迭代器种类)类型的额外 object 以便编译器利用 overloading resolution(重载解析)来调用正确的实现:

template
void advance(IterT& iter, DistT d)
{
 doAdvance( // call the version
  iter, d, // of doAdvance
  typename // that is
  std::iterator_traits::iterator_category() // apPRopriate for
 ); // iter's iterator
} // category

  我们现在能够概述如何使用一个 traits class 了:

  ·创建一套重载的 "worker" functions(函数)或者 function templates(函数模板)(例如,doAdvance),它们在一个 traits parameter(形参)上不同。与传递的 traits 信息一致地实现每一个函数。

  ·创建一个 "master" function(函数)或者 function templates(函数模板)(例如,advance)调用这些 workers,传递通过一个 traits class 提供的信息。

  traits 广泛地用于标准库中。有 iterator_traits,当然,再加上 iterator_category,提供了关于 iterators(迭代器)的四块其它信息(其中最常用的是 value_type )。还有 char_traits 持有关于 character types(字符类型)的信息,还有 numeric_limits 提供关于 numeric types(数值类型)的信息,例如,可表示值的最小值和最大值,等等。(名字 numeric_limits 令人有些希奇,因为关于 traits classes 更常用的惯例是以 "traits" 结束,但是它就是被叫做 numeric_limits,所以 numeric_limits 就是我们用的名字。)

  TR1引入了一大批新的 traits classes 提供关于类型的信息,包括 is_fundamental(T 是否是一个 built-in type(内建类型)),is_array(T 是否是一个 array type(数组类型)),以及 is_base_of(T1 是否和 T2 相同或者是 T2 的一个 base class(基类))。合计起来,TR1 在标准 C++ 中加入了超过 50 个 traits classes。

  Things to Remember

  ·traits classes 使关于类型的信息在编译期间可用。它们使用 templates(模板)和 template specializations(模板特化)实现。

  ·结合 overloading(重载),traits classes 使得执行编译期类型 if...else 检验成为可能。

Tags:箴言 类型 信息

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接