算法与函数对象：序列、容器及函数对象的深入解析

# 算法与函数对象：序列、容器及函数对象的深入解析 ## 1. 序列与容器 ### 1.1 标准库的设计原则与序列概念 在编程中，通常遵循一个良好的原则，即某事物最常见的使用方式应该是最短、最易表达且最安全的。然而，标准库为了追求通用性，在一定程度上违背了这一原则。例如，要在一个列表中找出 `4422` 的前两次出现位置，代码如下： ```cpp void f(list<int>& li) { list<int>::iterator p = find(li.begin(), li.end(), 4422); // 第一次出现 if (p != li.end()) { list<int>::iterator q = find(++p, li.end(), 4422); // 第二次出现 // ... } // ... } ``` 如果 `find()` 被设计为对容器的操作，那么要找出第二次出现的位置就需要额外的机制。而且，为每个容器和每个算法泛化这样的“额外机制”是很困难的。因此，标准库算法是基于元素序列来工作的。算法的输入通过一对迭代器来表示一个序列，第一个迭代器指向序列的第一个元素，第二个迭代器指向序列最后一个元素的下一个位置，这种序列被称为“半开”序列，因为它包含第一个元素但不包含第二个元素。半开序列使得许多算法在处理空序列时无需特殊处理。 ### 1.2 序列与范围 序列，尤其是可以进行随机访问的序列，通常被称为范围。传统数学中半开范围的表示法有 `[first, last)` 和 `[first, last[`。需要注意的是，序列可以是容器的元素，也可以是容器的子序列。此外，像 I/O 流这样的一些序列并不是容器，但基于序列的算法同样可以正常工作。 ### 1.3 输入序列 在代码中，使用 `x.begin(), x.end()` 来表示“`x` 的所有元素”是很常见的，但这种方式既繁琐又容易出错。例如： ```cpp void f(list<string>& fruit, list<string>& citrus) { typedef list<string>::const_iterator LI; LI p1 = find(fruit.begin(), citrus.end(), "apple"); // 错误！(不同序列) LI p2 = find(fruit.begin(), fruit.end(), "apple"); // 正确 LI p3 = find(citrus.begin(), citrus.end(), "pear"); // 正确 LI p4 = find(p2, p3, "peach"); // 错误！(不同序列) // ... } ``` 在这个例子中存在两个错误。第一个错误一旦被怀疑就比较明显，但编译器很难检测到；第二个错误即使是有经验的程序员在实际代码中也很难发现。减少显式迭代器的使用可以缓解这个问题。这里介绍一种明确输入序列概念的方法来解决这个问题。 ### 1.4 明确输入序列的实现 关键思想是明确将序列作为输入。例如，标准的 `find()` 函数和扩展的 `find()` 函数： ```cpp template<class In, class T> In find(In first, In last, const T& v) // 标准 { while (first!=last && *first!=v) ++first; return first; } template<class In, class T> In find(IsEq<In> r, const T& v) // 扩展 { return find(r.first, r.second, v); } ``` 一般来说，通过重载（`§13.3.2`），当使用 `IsEq` 参数时，优先使用输入序列版本的算法。 输入序列自然地被实现为一对迭代器： ```cpp template<class In> struct IsEq : public pair<In, In> { IsEq(In i1, In i2) : pair<In, In>(i1, i2) { } }; ``` 我们可以显式地创建调用第二个版本 `find()` 所需的 `IsEq`： ```cpp LI p = find(IsEq<LI>(fruit.begin(), fruit.end()), "apple"); ``` 但这种方式比直接调用原始的 `find()` 更繁琐。可以使用简单的辅助函数来简化这个过程。例如，容器的 `IsEq` 是从其 `begin()` 到 `end()` 的元素序列： ```cpp template<class C> IsEq<typename C::iterator> iseq(C& c) // 针对容器 { return IsEq<typename C::iterator>(c.begin(), c.end()); } ``` 这样就可以简洁且无重复地表达容器上的算法。例如： ```cpp void f(list<string>& ls) { list<string>::iterator p = find(ls.begin(), ls.end(), "standard"); list<string>::iterator q = find(iseq(ls), "extension"); // .. } ``` `IsEq` 的关键好处是明确了输入序列的概念，使用 `iseq()` 可以消除将每个输入序列表示为一对迭代器时所需的繁琐且容易出错的重复操作。 ### 1.5 输出序列 输出序列的概念也很有用，但它没有输入序列那么简单和直接（`§18.13[7]`；另见 `§19.2.4`）。 ## 2. 函数对象 ### 2.1 函数对象的引入 许多算法仅使用迭代器和值来操作序列。例如，在序列中查找值为 `77` 的第一个元素： ```cpp void f(list<int>& c) { list<int>::iterator p = find(c.begin(), c.end(), 77); // ... } ``` 为了实现更有趣的功能，我们希望算法能够执行我们提供的代码。例如，查找序列中值小于 `77` 的第一个元素： ```cpp bool less_than_77(int v) { return v < 77; } void f(list<int>& c) { list<int>::iterator p = find_if(c.begin(), c.end(), less_than_77); // ... } ``` 将函数作为参数传递有很多明显的用途，如逻辑谓词、算术运算、从元素中提取信息等。但为每个用途编写一个单独的函数既不方便也不高效，而且一个函数在逻辑上也不足以表达我们想要的所有内容。通常，对每个元素调用的函数需要在调用之间保存数据，并返回多次调用的结果。类的成员函数比独立函数更能满足这些需求，因为其对象可以保存数据，并且类可以提供初始化和提取这些数据的操作。 ### 2.2 计算总和的函数对象示例 考虑如何编写一个类似函数的类来计算总和： ```cpp template<class T> class Sum { T res; public: Sum(T i = 0) : res(i) { } // 初始化 void operator()(T x) { res += x; } // 累加 T result() const { return res; } // 返回总和 }; ``` 显然，`Sum` 是为那些支持初始化为 `0` 和 `+=` 操作的算术类型设计的。例如： ```cpp void f(list<double>& ld) { Sum<double> s; s = for_each(ld.begin(), ld.end(), s); // 对 ld 的每个元素调用 s() cout << "the sum is " << s.result() << '\n'; } ``` 这里，`for_each()`（`§18.5.1`）对 `ld` 的每个元素调用 `Sum<double>::operator()(double)`，并返回作为第三个参数传递的对象。`for_each()` 能正常工作的关键原因是它并不假设其第三个参数是一个函数，而只是假设它是一个可以用适当参数调用的对象。一个合适定义的对象可以像函数一样工作，而且通常比普通函数执行得更快。具有应用运算符的类的对象被称为函数式对象、仿函数或简称为函数对象。 ### 2.3 函数对象基类 标准库提供了许多有用的函数对象。为了帮助编写函数对象，在 `<functional>` 中，库提供了两个基类： ```cpp template <class Arg, class Res> struct unary_function { typedef Arg argument_type; typedef Res result_type; }; template <class Arg, class Arg2, class Res> struct binary_function { typedef Arg first_argument_type; typedef Arg2 second_argument_type; typedef Res result_type; }; ``` 这些类的目的是为从 `unary_function` 和 `binary_function` 派生的类的用户提供参数和返回类型的标准名称。像标准库那样一致地使用这些基类，可以避免程序员在实践中才发现它们的用处（`§18.4.4.1`）。 ### 2.4 谓词 谓