Discussion

Algorithms make an unknowable number of copies of their predicates at unknowable times in an unknowable order, and then go on to pass those copies around while casually assuming that the copies are all equivalent.

That is why it's your responsibility to make sure that copies of predicates are indeed all equivalent, and that means that they must be pure functions: functions whose result is not affected by anything other than the arguments passed to operator(). Additionally, predicates must also consistently return the same result for the same set of arguments they are asked to evaluate.

Stateful predicates may seem useful, but they are explicitly not very useful with the C++ standard library and its algorithms, and that is intentional. In particular, stateful predicates can only be useful if:

• The predicate is not copied: The standard algorithms make no such guarantee, and in fact assume that predicates are safely copyable.

• The predicate is applied in a documented deterministic order: The standard algorithms generally make no guarantee about the order in which the predicate will be applied to the elements in the range. In the absence of guarantees about the order in which objects will be visited, operations like "flag the third element" (see Examples) make little sense, because which element will be visited "third" is not well-defined.

It is possible to work around the first point by writing a lightweight predicate that uses reference-counting techniques to share its deep state. That solves the predicate-copying problem too because the predicate can be safely copied without changing its semantics when it is applied to objects. (See [Sutter02].) It is not possible, however, to work around the second point.

Always declare a predicate type's operator() as a const member function so that the compiler can help you avoid this mistake by emitting an error if you try to change any data members that the predicate type may have. This won't prevent all abusesfor example, it won't flag accesses to global databut it will help the compiler to help you avoid at least the most common mistakes.