March 11, 2011, 5:03 a.m.
posted by madinteger
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:
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.