Is this code an abuse of STL's find_if?

Question

Let's say I have a list of server names stored in a vector, and I would like to contact them one at a time until one has successfully responded. I was thinking about using STL's find_if algorithm in the following way:

find_if(serverNames.begin(), serverNames.end(), ContactServer());

Where ContactServer is a predicate function object.
On one hand, there's a problem since the predicate will not always return the same result for the same server name (because of server downtime, network problems, etc...). However, the same result will be returned regardless of which copy of the predicate is used (i.e. the predicate has no real state), so the original problem with state-keeping predicates is not relevant in this case.

What do you say?

Answer 1

I think I would go for it.

The only thing I would worry about is the readability (and therefore maintainability) of it. To me, it reads something like "Find the first server I can contact", which makes perfect sense.

You might want to rename ContactServer to indicate that it is a predicate; CanContactServer? (But then people would complain about hidden side effects. Hmm...)

Answer 2

Isn't that what find_if is for?

Note though, that it will find all the servers, if you iterate over the iterator - but you aren't going to do that (according to OP).

Answer 3

However, the same result will be returned regardless of which copy of the predicate is used (i.e. the predicate has no real state), so the original problem with state-keeping predicates is not relevant in this case.

So where's the problem? Function objects don't necessarily have to be stateful. It's actually best practice to use function objects instead of function pointers in such situations because compilers are better at inlining them. In your case, the instantiation and call of the function object may have no overhead at all since find_if is a function template and the compiler will generate an own version for your functor.

On the other hand, using a function pointer would incur an indirection.

Answer 4

Note though, that it will find all the servers, if you iterate over the iterator - but you aren't going to do that (according to OP).

That's actually an interesting point. Although find_if returns the first element for which the predicate returns true, I don't see any mention of a promise that the predicate will not be called on subsequent elements as well. The behavior is OK with Visual Studio 2003 (the iteration stops on the first element for which the predicate is true), but this might not be portable.

Answer 5

So where's the problem? Function objects don't necessarily have to be stateful

The problems is the other way around. Predicates (specifically) are not supposed to hold on to state that affects their answer since they might be copied several times during the algorithm.

Answer 6

So where's the problem? Function objects don't necessarily have to be stateful

The problems is the other way around. Predicates (specifically) are not supposed to hold on to state that affects their answer since they might be copied several times during the algorithm.

Sorry but I still don't see the problem. Perhaps it would help if you could post (at least a sketch of) the implementation of ContactServer. What state does it hold and how does this affect the answer? More importantly, why and how is this state changed upon copying?

Answer 7

What state does it hold and how does this affect the answer? More importantly, why and how is this state changed upon copying?

I guess I was a bit ambiguous. What I meant was that in general, in order to avoid potential state issues that result from the predicate being passed by value, it is considered good practice that any instance of the predicate will return the same answer for the same object under any circumstance. My predicate does not conform with this requirement (its answers depend on server availability), however, two instances of the predicate are identical in the sense that regardless of the instance chosen at a given time, the answer returned will be the same.
This seems to avoid the problem, but does not comply with the general practice and may mislead some readers of the code. This is the reason I decided to ask this question.

Answer 8

In the upcoming version of the C++ standard, I could not find any explicit restriction with respect to the fact that a predicate should always return the same value for the same input. I looked into section 25 (paragraphs 7 to 10).

Methods returning values that may change from one call to another, as in your case, should be volatile (from 7.1.6.1/11: "volatile is a hint to the implementation to avoid aggressive optimization involving the object because the value of the object might be changed by means undetectable by an implementation").

Predicates "shall not apply any non-constant function through the dereferenced iterators" (paragraphs 7 and 8). I take this to mean that they are not required to use non-volatile methods, and that your use-case is thus ok with respect to the standard.

If the wording was "predicates should apply const functions..." or something like that, then I would have concluded that 'const volatile' functions were not ok. But this is not the case.

Answer 9

In the upcoming version of the C++ standard, I could not find any explicit restriction with respect to the fact that a predicate should always return the same value for the same input. I looked into section 25 (paragraphs 7 to 10).

It's not so much a question of standard adherence but rather of correct use of certain algorithms (most notably remove_if). Many implementations use several copies of the predicate and thus saving state in the predicate is problematic. This lead to a practice of predicates that always return the same value for the same input.

Answer 10

find_if appears to be the right choice here. The predicate isn't stateful in this situation.

Answer 11

This is exactly what the STL algorithms are for. This is not an abuse at all. Furthermore, it is very readable. Redirect to null anyone who tells you otherwise.