C++算法与函数对象详解

# C++ 算法与函数对象详解 ## 1. 序列与容器 在编程中，一个好的通用原则是，某事物最常见的用法应该是最短、最易表达且最安全的。但标准库为了通用性，有时会违背这一原则。比如，要在列表中找出`42`的前两次出现位置，代码如下： ```cpp void f(list<int>& li) { list<int>::iterator p = find(li.begin(), li.end(), 42); // 第一次出现 if (p != li.end()) { list<int>::iterator q = find(++p, li.end(), 42); // 第二次出现 // ... } // ... } ``` 若`find()`是容器上的操作，找第二次出现位置就需要额外机制，且为每个容器和算法泛化这种“额外机制”很困难。因此，标准库算法基于元素序列操作，算法输入用一对迭代器表示序列，第一个迭代器指向序列首元素，第二个指向序列尾元素的下一个位置，这种序列叫“半开”序列，它让很多算法无需将空序列作为特殊情况处理。 序列（尤其是可随机访问的序列）常被称为范围，半开范围的传统数学表示法是`[first,last)`和`[first,last[`。序列可以是容器的元素或容器的子序列，有些序列（如 I/O 流）不是容器，但基于序列的算法仍能正常工作。 ### 1.1 输入序列 用`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"); // 错误！(不同序列) // ... } ``` 此例有两个错误，第一个编译器不易检测，第二个即使有经验的程序员在实际代码中也难发现。减少显式迭代器的使用可缓解此问题。解决思路是明确将序列作为输入，例如： ```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); } ``` 一般通过重载，当使用`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()`更繁琐。简单的辅助函数可减轻这种繁琐，例如： ```cpp template<class C> Iseq<C::iterator_type> iseq(C& c) // 针对容器 { return Iseq<C::iterator_type>(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.2 函数对象 很多算法仅使用迭代器和值对序列操作。例如，在序列中找值为`7`的首个元素： ```cpp void f(list<int>& c) { list<int>::iterator p = find(c.begin(), c.end(), 7); // ... } ``` 为实现更有趣的功能，希望算法执行我们提供的代码。比如，找序列中值小于`7`的首个元素： ```cpp bool less_than_7(int v) { return v<7; } void f(list<int>& c) { list<int>::iterator p = find_if(c.begin(), c.end(), less_than_7); // ... } ``` 作为参数传递的函数有很多用途，如逻辑谓词、算术运算、从元素提取信息等。为每次使用编写单独函数既不方便也不高效，且函数在逻辑上不足以表达我们想表达的所有内容。通常，为每个元素调用的函数需要在调用间保存数据并返回多次应用的结果，类的成员函数更适合这种需求，因为其对象可保存数据，类还能提供初始化和提取这些数据的操作。 考虑编写一个计算总和的函数（或类似函数的类）： ```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; } // 返回总和 }; ``` 使用示例： ```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()`为`ld`的每个元素调用`Sum<double>::operator()(double)`，并返回作为第三个参数传递的对象。其关键原因是`for_each()`不要求第三个参数是函数，只要求它能用适当参数调用，合适定义的对象和函数一样好用，且类的应用运算符通常比作为函数指针传递的函数更容易内联，因此函数对象通常比普通函数执行更快。有应用运算符的类的对象称为函数式对象、仿函数或简称为函数对象。 ### 1.3 函数对象基类 标准库提供很多有用的函数对象，为辅助编写函数对象，库提供了两个基类： ```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`派生的类的用户提供参数和返回类型的标准名称，按标准库的方式一致使用这些基类，可避免程序员费力去发现它们的用处。 ### 1.4 谓词 谓词是返回`bool`的函数对象（或函数）。例如，`<functional>`定义： ```cpp template <class T> struct logical_not : public unary_function<T,bool> { bool operator()(const T& x) const { return !x; } }; template <class T> struct less : public binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const { return x<y; } }; ``` 一元和二元谓词常与算法结合使用。例如，比较两个序列，找其中一个序列中首个不小于另一个序列对应元素的元素： ```cpp void f(vector<int>& vi, list<int>& li) { typedef list<int>::iterator LI; typedef vector<int>::iterator VI; pair<VI,LI> p1 = mismatch(vi.begin(), vi.end(), li.begin(), less<int>()); // ... } ``` `mismatch()`算法对对应元素对重复应用其二元谓词，直到不满足条件，然后返回不满足比较条件的元素的迭代器。因为需要的是对象而非类型，所以使用`less<int>()`（带括号）而非`less<int>`。 若要找首个小于对应元素的元素，可将序列以相反顺序传递给`mismatch()`： ```cpp pair<LI,VI> p2 = mismatch(li.begin(), li.end(), vi.begin(), less<int>()); ``` 或使用互补谓词`greater_equal`： ```cpp p1 = mismatch(vi.begin(), vi.end(), li.begin(), greater_equal<int>()); ``` ### 1.5 常见谓词概述 `<functional>`中标准库提供了一些常见谓词，如下表： | 谓词 | 类型 | 描述 | | --- | --- | --- | | equal_to | 二元 | arg1==arg2 | | not_equal_to | 二元 | arg1!=arg2 | | greater | 二元 | arg1>arg2 | |