仿函数和区间(5)
Mathew Wilson 著
刘未鹏 译
======================
这是最后一部分:-) enjoy it!
======================
Table 34.2 Characteristics of a notional range.
Name
Expressions
Semantics
Precondition
Postcondition
Dereference
*r
或
r.current()
返回当前位置的值
r还没有到达尾部
不改变r
Advance
++r
或
r.advance()
将当前位置前进一步
r还没有到达尾部
r或者到达尾部或者可以被解引用
State
r
或
r.is_open()
如果r已经到了尾部则求值为true，否则为false。
-
-
任何指针类型都不符合range的语法规则[1]，所以我们不必去迎合任何基本类型，这就使我们的实现具有了额外的灵活性。换句话说，我们可以相信任何range的实例的类型都是类(class)类型的，从而我们可以根据某些特性在该类型上的存在与否来特化作用于range上的算法(见34.4.4节)。
这和操纵Iterator[Aust99]的算法的工作方式很相似，但更为简单一些。我对range的实现依赖于这样一个事实：特定的range继承自恰当的tag类。
struct simple_range_tag
{};
struct iterable_range_tag
: public simple_range_tag
{};
下一节我们会看到如何使用它们。
34.4.2 概念性Range(Notional Range)
有时候，你并没有一个具体的range——也就是说，一个由一对迭代器定义的区间。更进一步说，你拥有一个“概念上的”range——它可能是“从1到99之间的所有奇数”，在这个简单的例子中，你知道所有的奇数一共有49个(包括1和97)，所以使用经典的STL的方式你会这样做:
struct next_odd_number
{
next_odd_number(int first)
: m_current(first - 2)
{}
int operator ()()
{
return ++++m_current; // Nasty, but it fits on one line ;/
}
private:
int m_current;
};
std::vector<int> ints(49);
std::generate(ints.begin(), ints.end(), next_odd_number(1));
有关STL的书籍通常把这种例子作为STL最佳实践的完美范例——它的确是的，不过对于我来说，这仍然还是过于痛苦了。首先，我们可能创建了一个其它地方根本用不到的仿函数(next_odd_number)。
其次，也是更为重要的一点：在这种技术中，仿函数作为一个被动的生成装置，其动作由标准库算法std::generate()来引发，而std::generate()的界限却又是由(它所填充的)vector来决定的。理清这一点很重要：它意味着我们得预先知道将会生成多少个结果，以便在vector中为它们准备恰当的空间。然而，要想预先知道生成多少个结果，我们必须得深刻理解生成装置(那个仿函数)的工作机理才行。在上面的这个简单的例子中，生成机理相对来说很简单(虽然我承认我第一次准备测试程序的时候把它给搞错了)，然而，考虑一下：如果我们是在计算菲波那契(Fibonacci)数列的项(其上界由用户给出)，那么除了把整个子数列枚举一遍(直到用户指定的最大值(上界)为止)之外，没有其它任何办法可以知道在这么一个range中一共有多少元素(或者说，要进行多少步迭代才能到头——译注)[2]，而唯一可行的办法(枚举一遍)又太过拖沓(且不说它的低效)。
在这种情况下，我们需要的是让生成装置来驱动整个过程(依照代码的作者所规定的准则)。是请出我最喜爱的range示例的时候了——integral_range模板——其简化版的定义在Listing 34.9中：
Listing 34.9
template <typename T>
class integral_range
: public simple_range_tag
{
public:
typedef simple_range_tag range_tag_type;
typedef T value_type;
// Construction
public:
integral_range( value_type first, value_type last
, value_type increment = +1)
~integral_range()
{
// Ensure that the parameterising type is integral
STATIC_ASSERT(0 != is_integral_type<T>::value);
}
// Enumeration
public:
operator “safe bool”() const; // See Chapter 24
value_type operator *() const;
class_type &operator ++();
// Members
. . .
};
integral_range在它对应的逻辑区间上进行枚举（通过给定的整型类型T的成员变量）。
我们现在可以重写前面的例子如下：
std::vector<int> ints;
ints.reserve(49); // No problem if this is wrong.
r_copy(integral_range<int>(1, 99, 2), std::back_inserter(ints));
注意，对reserve()的调用是一个优化，去掉它并不会对程序的正确性有任何影响。r_copy()是一个range算法(见34.4.3)，其语义和标准库算法std::copy()[Muss01]相同。现在，生成装置(即integeral_range<int>)驱动了整个过程——本该如此。我们可以很轻易的在这里把它替换成Fibonacci_range，并且代码一如既往的正确和高效(而前面的STL版本则做不到这一点)。
34.4.3 可迭代Range
可迭代range是概念性range的一个扩展，它额外提供了begin()，end()以及range()方法，从而可以和标准STL算法完全兼容(34.4.4)。
可迭代range通常在内部保存指向区间的当前位置和结尾的迭代器，并且通过begin()和end()方法来返回它们。range()方法是用于克隆(处于当前迭代状态的)区间的，尽管这要受制于迭代器拷贝的限制(如果range底层的迭代器是Input或Output迭代器的话[Aust99,Muss01])：只有Forward或“更高的”迭代器模型[Aust99,Muss01]支持多次遍历给定区间的能力。
自己写可迭代range类是可行的，但是通常的惯用手法(idiom)是使用适配器(adapter)。在我对Range概念的实现中，包含两个适配器——sequence_range和iterator_range模板类。很显然，sequence_range适配了STL序列(Sequence)，而iterator_range则适配了STL迭代器(Iterator)。
给出一个序列类型，我们可以把它适配为一个range——只要把该序列的实例传给sequence_range的某个恰当的实例的构造函数即可，像这样：
std::deque<std::string> d = . . . ;
sequence_range< std::deque<std::string> > r(d);
for(; r; ++r)
{
. . . // Use *r
}
类似的，一个iterator_range则是以一对迭代器来构造，像这样：
vector<int> v = . . . ;
for(iterator_range<vector<int>::iterator> r(v.begin(), v.end());r;++r)
{
... //Use *r
}
初看上去，可迭代range仅仅是在手写循环中可以提供语法上的便利以减轻不必要的变量带来的混乱。我得承认，对于我来说，这本身就已经是个非常引人注目的地方了，但是，这个概念还提供了比这要多得多的能力，我们会在接下来的章节中看到。
34.4.4 Range算法和标签(Tags)
到目前为止，所有的例子都展示了range在手写循环中的使用。但是range还可以被用于算法。这就是概念性range和迭代式range这两个概念被分离开的原因。考虑标准库算法distance()：
template <typename I>
size_t distance(I first, I last);
该算法返回[first,last)所表示的区间中的元素的个数，对于除随机访问(Random Access)之外的迭代器类型，元素个数通过逐步递增first直到它等于last来计算。但是该算法模板被实现为可以高效简洁地针对随机访问迭代器进行计算——(last – first)。而当把算法用于range时，我们当然不希望丧失这种高效性。
答案很简单：我们尽量使用标准库算法来实现range算法。Range算法r_distance()是这样定义的：
Listing 34.10
template <typename R>
ptrdiff_t r_distance_1(R r, iterable_range_tag const &)
{
return std::distance(r.begin(), r.end());
}
template <typename R>
ptrdiff_t r_distance_1(R r, simple_range_tag const &)
{
ptrdiff_t d = 0;
for(; r; ++r, ++d)
{}
return d;
}
template <typename R>
inline ptrdiff_t r_distance(R r)
{
return r_distance_1(r, r);
}
r_distance()由r_distance_l()[3]来实现。r_distance_l()有两个定义：一个是为可迭代range准备的，使用标准库算法来实现。另一个是为概念性range准备的，它手动进行枚举。r_distance_l()的两个重载版本通过它们的第二个参数——该参数取决于range是“简单的(simple)”还是“可迭代的(iterable)”——来区别。
我们使用了运行时多态(继承)来选择编译期多态(模板参数决议)，所以我们需要将同一个range作为r_distance_l()的两个参数来传给它——第一个参数保留原来的类型，第二个参数仅仅用于重载决议。由于编译器可以把这个简单的东西(第二个参数)优化掉，所以无损效率，同时这种机制巧妙地达成了我们的目的。我们曾在34.4.2节看到:integral_range模板继承自simple_range_tag，而可迭代range则继承自iterable_range_tag，因此所有的range算法都会无二义性地选择最合适的实现。
现在我们可以回到算法的命名问题上并解决它了(34.2.2):由于我们把表现为一对迭代器的区间和range类的实例清楚的区别开了，所以我们根本就不需要相同的名字来方便通用式编程——因为前者有两个参数(一对迭代器)，而后者只有一个参数(单个的range实例)。因此，我们可以轻易的避免一切有关名字空间的灾难——只要把range算法加上“r_”前缀就行了。
34.4.5 过滤器(Filters)
Range的另一个强大的方面是“过滤器”的概念。它(过滤器)不过才刚刚开始发展，就已经带来了极大的效益。下面我用一个简单的过滤器——divisible(我们将它应用于integral_range)——来演示这个概念。
Listing 34.11
template <typename R>
struct divisible
: public R::range_tag_type
{
public:
typedef R filtered_range_type;
typedef typename R::value_type value_type;
public:
divisible(filtered_range_type r, value_type div)
: m_r(r)
, m_div(div)
{
assert(div > 0);
for(; m_r && 0 != (*m_r % m_div); ++m_r)
{}
}
public:
operator "safe bool"() const; // See Chapter 24
{
. . . // implemented in terms of m_r's op safe bool
}
value_type operator *() const
{
return *m_r;
}
class_type &operator ++()
{
for(; m_r && 0 != (*++m_r % m_div); )
{}
return *this;
}
private:
filtered_range_type m_r;
value_type m_div;
};
当结合integral_range一起使用时，我们可以把给定range中的所有可被3整除的奇数过滤出来，像这样：
std::vector<int> ints;
integral_range<int> ir(1, 99, 2);
r_copy( divisible<integral_range<int> >(ir, 3)
, std::back_inserter(ints));
当然，在实际运用中，range过滤器比这个要丰富的多。
34.4.6 虚伪？
作为一个反对滥用操作符重载的人[4]，我随时准备接受指责我虚伪的声音(当人们面对range所支持的操作符时)。当然，如果有人实在不肯原谅我的话(^_^)，我可以争辩说：range提供的那些不切实际的操作符是一个误用(滥用)。
我无法以任何纯化论者的立场来捍卫range这个概念，因此我可以退回到“不完美实践者的哲学”中去，并且说：它工作得如此不赖，如此简洁，这值得我们“违背良心”(^_^)。
如果你喜欢range概念，但是不想使用操作符重载，你完全可以将部分或全部操作符换成对应的方法调用，其语义和效率没有任何改变，只不过语法稍显冗长而已。
for(R r = . . .; r.is_open(); r.advance())
{
. . . = r.current();
}
34.5 仿函数和区间:尾声
本章带你作了一次关于轻则带来过多的击键，重则损害代码的可维护性的“围炉夜话”。
我们考察了手写循环和使用仿函数的优缺点，以及C++语言关于使用局部仿函数的一些缺陷。
我们还看到如何最大化仿函数的通用性(让它适用于更多的类型(通过字符类型参数化，类型隧道，以及适配器实参类型参数化))，把这些技术结合起来，我们得到一个关于本章开始部分提出的问题的坚固的解决方案。
最后，我们介绍了Range概念。Range并非仅仅提供语法上的便利，它还促使了对“以迭代器定界”的range和(我们可能称作)纯粹的逻辑range的统一操纵。此外，range过滤器的应用(对于两种range而言)展示了一个强大且易于使用的，用于操纵规则驱动的range的机制。
更新:Range的最近一周更新加入了对回调式枚举API(STL迭代器无法处理这种情况)的支持(通过Indirect Range的形式)。见http://www.rangelib.org/ 最近的更新细节。
[1] 除非我们将它(指针)指向内存的高地址区段，并且迭代直到指针的值为0，但是这在许多平台上都会导致内存非法访问，所以这个问题其实没有实际意义。
[2] 译注：对于一个菲波那契(Fibonacci)数列，如果指定其项的最大值(上界)，除了挨个枚举到该最大值，并累计项的个数之外，没法通过公式一下知道小于上界的项到底有多少个。比如：小于2553的菲波那契数列的项有多少个呢？而被动的生成装置一个最大的弱点就是，必须预先知道将要生成的结果的个数，不然无法保证预留的空间是否足够，为什么要预留空间呢？这是由std::generator()算法的本质决定的： std::generate(begin,end,producer());这里[begin,end)必须表示一段有效的区间，这段区间的长度就是将要生成的结果的数目。
[3] 这是个通常被使用的实现函数(类)的命名策略，它有助于避免当“外层的”函数和“内层的”实现函数具有相同名字并且存在“外层”函数的多个重载版本时引起的冲突。不同的编译器在这种情况下的决议具有不同的倾向，所以最简单的解决方案是避开它，无二义性地命名“内层的”实现函数。
[4] 尽管你可能会注意到，我在第25章曾成功克服了我的这种苛刻的想法。
