Klaus Kreft and Angelika Langer
http://www.cuj.com/experts/1904/toc.htm?topic=experts
标准运行库中的几个泛型算法在运行时使用了一元判定式（unary predicate）。例子是带if的算法，比如count_if()、find_if()、remove_if()、和replace_if()，但也有partition()这样[不带if]的算法。在本次专栏中，我们就近距离接触unary predicate，看它们可能以及绝不能做什么。
让我们看看标准如何定义unary predicate的。它在标准中被简称为predicate[注1]。
UNARY PREDICATE。Predicate参数被用于每当泛型算法期望一个functor作用在相应的iterator的反引用上，并返回一个可以与true进行测试的值的时候。换句话说，如果一个泛型算法接受一个predicate参数pred和iterator参数first，在构造函数中，它应该能正确工作： (pred(*first)){...}。
functor对象pred不应该在iterator的反引用上应用任何非const函数。
这个functor可以是一个指向函数的指针，或有合适的调用操作operator()的类型的对象。
从这个描述和对使用unary predicate的泛型算法进行的检查(我们将在本文后面看到)，我们能鉴别出unary predicate的很多典型特性。我们将在本文仔细讨论每个特性。特性是：
基本特性1. unary predicate必须是可调用的。
2. unary predicate必须接受一个参数，并返回一个可转换到布尔型的值。
3. unary predicate不需要可拷贝（copyable）。
副作用特性4. unary predicate不能修改它的实参。
5. unary predicate不能使泛型算法正在存在的序列或iterator无效。
6. unary predicate可以有4和5以外的任何副作用。
其它特性7. unary predicate必须是顺序不敏感的，这意味着调用predicate的效果必须不依赖于传给它元素的顺序。
8. unary predicate不必对相同的实参的不同调用产生相同的结果。
让我们为什么有道理让predicate精确地拥有这些特性。
基本特性1、2和3unary predicate必须是可调用的，但不必可拷贝，并且必须接受一个参数和返回一个布尔值。
当我们考察标准如何定义在泛型算法中使用unary predicate（predicate“在构造函数中，它应该正确工作： (pred(*first)){...}）时，这些特性多少有些显然。这里是示范unary predicate的使用的泛型算法的典型实现：
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred) {
typename iterator_traits<InputIterator>::difference_type n = 0;
for ( ; first != last; ++first)
if ( pred(*first) )
++n;
return n;
}
换句话说，unary predicate像函数一样被调用。“可调用的”的要求被指向函数的指针满足，也被具有调用操作的类型的对象（所谓的functor）（或指向这样的对象的引用）满足。predicate被调用时，传入一个参数。这个参数是一个iterator的反引用的结果，也就是对序列中元素的一个引用。返回值被用作条件表达式，必须能转换到布尔类型。这是对unary prediate的意图的完整描述：它被调用，以根据序列中的元素产生一个布尔结果。
特别地，对unary predicate没有拷贝语义的要求。根本不需要可拷贝。作为一个通用规则，泛型算法不能依赖于任何它所使用的对象没被明确要求的特性。这包括泛型算法绝不能拷贝predicate，因为用户没被要求为他的predicate提供任何合理的拷贝语义。如果能将拷贝构造函数和赋值操作申明为私有成员并通过引用传递predicaet对象，就太好了。它不应该打破任何泛型算法的。实践中，你将发现假设predicate为可拷贝的运行库，虽然它们不应该这么做的。这样的标准运行库实作的一个令人惊讶的效果已经在C++ Report的一篇文章中被讨论过了[注2]。同时一些运行库实作已经除去了这个限制并且有期望中的行为；举例来说，Metrowerks CodeWarrior 6.0。考虑到不同的运行库实作，我们只能说最好避免具有“有趣的”拷贝语义或没有拷贝语义的unary predicate。
实践中，绝大多数predicate拥有正常的拷贝语义。这是因为通常我们以predicate被传值的方式来调用泛型算法的。为了能这么做，predicate必须是可拷贝的。不可拷贝的predicate可能有用，但不常见，因为它们必须被传引用，这必须额外小心，并需要看起来很有趣的模板语法。我们在前一篇中进行了functor的传引用问题的相关讨论：我们如何完成它，以及我们为什么可能想这么做[注3]。于此就不再进一步讨论了。而让我们继续进行到predicate的其余特性，讨论unary predicate产生的副作用。
副作用特性4、5和6unary predicate可以有任何副作用，除了修改它的实参和使得泛型算法正在操作的序列或iterator无效。
标准禁止这几个副作用，但允许其它的。为什么？为了理解这个要求，考虑一下在使用unary predicate的泛型算法内部发生了什么。有两个产生副作用的实体：泛型算法本身和unary predicate。泛型算法遍历输入的元素序列，检查元素，把它们作为参数传给unary predicate，修改和拷贝它们，并且可能产生其它副作用。unary predicate接受一个元素的引用，同样可能检查和修改这个元素并产生其它副作用。自然地，这些行为可能互相冲突。因为这个理由，让我们看一看unary predicate产生的副作用，并且根据潜在的冲突性分类为有害的、可能有害的和无害的副作用。
有害的副作用有害的副作用导致泛型算法正在操作的序列或iterator无效。(functor绝不该产生有害的副作用。这是适用于所有functor的通用规则，而不只是对predicate。标准甚至没有显式禁止这样的副作用，可能是因为这被认为是“常识”。)
有害的predicate的一个例子是在predicate内部保存了一个指向泛型算法正在操作的序列中的元素的指针或引用，并使用这个[指针或]引用来删除元素。元素的移除可能导致提供给泛型算法（以指明输入或输出序列）的iterator无效，而且在这种情况下，泛型算法可能导致程序崩溃。
移除元素是一个非常显眼的故障源，但有时，导致序列的无效并不怎么明显。如果泛型算法的实例依赖于序列的排列顺序，而predicate在被调用时有意或无意中修改了排序顺序，那么这将导致不可预知的结果。
无论如何，具有有害副作用的predicate必须绝对避免。作为一个规则，绝不要使用任何导致泛型算法所操作的序列或iterator无效的functor。
可能有害的副作用这种类型的副作用被标准显式禁止。所有使用其参数的非cosnt函数的unary predicate都属于此列，因为它们修改序列中的元素。让我们称之为变动性unary predicate。(注意“修改序列”(有害的)和“修改序列中元素”(只是可能有害)间的区别：“修改序列”意味着有元素插入或移除或移动，以使得某个iterator或iterator区间变得无效。“修改序列中的元件”意味着元素被访问了，它们的内容被改变了，但是不会导致任何iterator无效。)
变动性unary predicate的可能害处源于这样的事实：predicate不是唯一一个访问并改变输入序列中的元素的东西。泛型算法本身可能试图修改相同的元素。在这种情况下，有两个副作用实体（泛型算法和predicate），它们的行为可能冲突。
这样的冲突何时发生？不是所有的泛型算法都修改输入序列的元素，但是有一些是这么做了。泛型算法分为几类：非变动性算法和变动性算法，而变动性算法又可以分为in-place算法和拷贝算法。非变动性算法（比如，count_if()）只是查看元素；它们不作任何改变。变动性拷贝算法（比如，replace_copy_if()）不修改输入序列的元素，但将它们拷贝入输出序列；它们修改输出序列的元素。变动性in-place算法（比如，replace_if()）“就地”修改元素，这意味着它们修改输入序列的元素；他们是危险的东西。因此，predicate与泛型算法间的潜在冲突就发生在同时使用变动性in-place算法和变动性unary predicate的时候。
对相同元素修改两次的程序会导致两个问题：哪个修改被先执行并可能被第二个修改覆盖？结果可以完全预知吗？为了避免泛型算法和predicate间的这种冲突，标准要求unary predicate绝不能修改作为参数传给它的输入序列中的元素。注意这个变动性副作用对所有unary predicate都是禁止的，而不只是那些传给变动性in-place算法的unary predicate。
这个限制经常反映在predicate的函数签名中：典型地，一个unary predicate接受的参数不是传值就是传const的引用，以确保实参（相关的输入序列的元素）不被修改。
无害的副作用最后，但是不最少，predicate可以具有无害的副作用。所有的对序列中元素的非变动性访问都属于这个范畴。predicate可以使用其参数的const的函数；也就是说，它可以查看元素，但不能修改它们。另外，unary predicate可以修改实参以外的对象。比如，它可能拥有数据成员，并改变它们的值。或者它可能涉及无关元素序列并修改它们。只要被predicate改变的序列不是算法算法正在操作的序列，它就是无害的。
我们为什么会关心?我们已经看到predicate可能产生的不同类型的副作用，并且许多副作用被标准禁止。为什么我们会想在这些环境下使用带副作用的predicate？带副作用的predicate很少见还是很常见？
嗯，视情况而定。如果你查看C++教科书上predicate的例子，将发现isEven这样的predicate被定义为bool isEven(int elem){return elem % 2 == 0;}或bind2nd(greater<int>(),4)（用被称为binder的东西从预定义的binary predicate产生的unary predicate）。即使你研究那些用functor类型（也就是，重载了调用操作的类）实现的unary predicate，他们也很少拥有数据成员或做复杂的事，而且从不具有副作用。
实践中，微有不同。举例来说，我们关心效率。明显地，在完成某些操作时，一次遍历序列而不是重复在很长的序列上步进，会更快。考虑一些例子。
假设，我们有一个容器来描述客户。我们为内部统计的需要而检测常客的数目，并且，我们想建立一个邮寄列表，因为我们想寄推销信给常客。然而，邮寄列表不该超过5,000的界限。那是任务。我们如何完成？一个可能的方法是用一个unary predicate，对常客产生true，并由它累积邮寄列表的信息。当将它传给count_if()算法时，将产生想要的计数并（作为副作用）建立邮寄列表。这样的unary predicate严格地遵照了规则。 它接受一个对客户的const的引用，查看客户，并且产生一个无害的副作用：邮寄列表。
让我们考虑另外一个相似的例子。我们需要将所有非常客从客户数据中移除，并更新保留的常客的折扣记录。再一次，我们试图高效，而期望在一次遍历客户数据时将两者都做掉。和前面的方法相比，我们可以试图给remove_if()提供一个unary predicate，它对非常客产生true（以便泛型算法移除它们），并将折扣的信息加给其余的客户。 与较早的例子相反，这是不合法的，对输入系列中的元素增加信息是被禁止的副作用。记住：predicate绝不能修改它的实参。但那确实是我们想要的：我们想更新系列中的剩余元素。那么，怎么做？
我们没有太多能做的。对标准的泛型算法章节的彻底研究表明，for_each()是唯一一个接受functor，并允许functor修改实参的泛型算法。(我们在前一篇文章讨论了for_each()4)。) 因为这个原因，对于包含修改输入系列的元素的任务，我们在泛型算法的选择上严重受限；for_each()基本上是唯一的选择。
结果是我们必须要将任务分解为非改动性的行为(实现为供remove_if()用的unary predicate) 和改动性的行为(实现为供for_each()用的functor)。这样的对序列的额外遍历是不可避免的，包括不可避免的效率损失。
替代选择是:
l 供for_each()使用的一个functor，移除和修改元素（重复了使用我们的predicate的remove_if()的功能，这当然不是我们想要的）
l 用户自定义的remove_if()版本，它允许修改输入序列的元素(这是可行的；甚至是标准泛型算法的拷贝都可能仰赖于它是如何实现的)
l 手工编写的算法(忽略所有标准泛型算法)
底线是：如果输入序列的元件一定要被修改，就不能使用unary predicate。
如果需要这样的修改(比如，因为效率的原因)，而又想使用标准泛型算法的话，那么我们必须将任务分解为改动性和非改动性两类，并且必须接受对输入序列的多次遍历。
特性 7unary predicate必须是顺序不敏感的；也就是说，它的效果必须不依赖于调用顺序。
另外两个方面和unary predicate的副作用有联系： predicate的调用顺序和调用次数。如果每当predicate作用在输入序列的元素上时都产生副作用的话，那么我们会想知道副作用是以怎样的频度和顺序产生的。举例来说，在我们的例子中，我们累加一个计数以决定生成的邮寄列表的最大大小。自然地，predicate精确地对每个元素作用一次和可能重复作用，这之间是有区别的。依赖于副作用的性质，调用的顺序和次数将扮演不同的角色。
调用的次数被精确描述了：count_if()或remove_if()这类泛型算法精确地将predicate作为于输入序列中的每个元素一次。调用顺序则有不同：没有任何一个接受redicate的泛型算法描述了它向predicate提供元素的顺序。于是，unary predicate必须不依赖于调用顺序。如果我们使用一个依赖于调用顺序的predicate，结果不可预知。
这里是一个例子：一个(顺序敏感的)predicate对序列中每第n个元素产生ture:
class Nth {
public:
Nth(int n) : theN(n), theCnt(0) {}
bool operator()(int)
{ return (++theCnt)%theN; }
private:
const int theN;
int theCnt;
};
如果我们将Nth(3)这样的predicate传给remove_copy_if()这样的泛型算法，然后期望它会将输入序列中的第3的倍数个的元素移入输出序列。但这不能得到保证，因为序列中的元素不一定以明确的顺序被操作。我们能确定的只是有三分之一的元素被从输入序列移入输出序列。
为什么标准没有对unary predicate的调用顺序给出保证？这是因为某些泛型算法能够对某些类型的iterator进行优化。举例来说，如果 iterator是input iterator ，泛型算法可能从序列的begin步进到end，但对random access iterator能够作任意跳进。因为标准不想限制这种优化的可能，所以没有对unary predicate的调用顺序给出保证。
结果，对STL的使用者而言，所有的unary predicate都绝不能依赖于序列中的元素被提供的顺序。如果我们想使用顺序敏感的predicate，那么就必须实现我们自定义的泛型算法，以给予对unary predicate的调用顺序的保证。
关于unary predicate的调用顺序和次数，这是最后一个观测。
特性8unary predicate在对相同实参的不同调用时，不必产生相同的结果。
这个特性可能听起来稍微牵强。我们将它列入特性表，因为我们注意到有时候存在一个假设，隐含要求predicate表现为“稳定的”行为，也就是说当它们被用相同或“相等/等价”的实参调用时，每次都产生相同的结果。这个假设不成立；标准没有规定任何类似的要求。
那么，为什么有时候假设unary predicate被要求有“稳定的”行为？因为它会给实作相当多的自由度。具有“稳定的”行为，它不必在意predicate被相同的元素调用了多少次，因为结果总是相同的。它也不在乎传给泛型算法的是序列中元素的引用还是其临时拷贝（即“相等/等价”元素）。
然而，对STL的unary predicate，没有“稳定的”行为的要求。完全有道理定义一个“不稳定”的predicate。例如，对所有具有某个属性的元素都产生true，直到达到一个界限。它可能被用于remove_copy_if()以从输入序列中拷贝maximum个具有给定属性的元素到输出序列。
总结标准运行库的下列泛型算法使用unary predicate：replace_if()， remove_if()，partition()，stable_partition()，replace_copy_if()，remove_copy_if()，count_if()和find_if()。
如果一个unary predicate具有下列特性，那么它能用于上述任何泛型算法，并且结果可移植和可预知。
l unary predicate必须是可调用的（callable），并且必须接受一个实参，并返回一个布尔值，但不必具有任何特别的拷贝语义。(某些运行库实作对此有限制，因为它们需要某种拷贝语义。)
l unary predicate绝不能修改它的实参，并且绝不能导致泛型算法正在操作的序列或iterator无效，但可以有其它任何副作用。
l unary predicate必须不依赖于调用顺序，并且可以对相同实参的不同调用产生不同的结果。
引用[1] International Standard. Programming languages — C++ ISO/IEC IS 14882:1998(E).
[2] Nicolai M. Josuttis. "Predicates vs. Function Objects," C++ Report, June 2000.
[3] Klaus Kreft and Angelika Langer. "Effective Standard C++ Library: Explicit Function Template Argument Specification and the STL," C/C++ Users Journal, December 2000, http://www.cuj.com/experts/1812/langer.html.
[4] Klaus Kreft and Angelika Langer. "Effective Standard C++ Library: for_each vs. transform," C/C++ Users Journal, February 2001. http://www.cuj.com/experts/1902/langer.html
本文地址：http://com.8s8s.com/it/it1779.htm