How do I return from a function inside a lambda?

Question

Consider the following toy code to determine whether a range contains an element:

template<typename Iter, typename T>
bool contains1(Iter begin, Iter end, const T& x)
{
    for (; begin != end; ++begin)
    {
        if (*begin == x) return true;
    }
    return false;
}

(Yes I know, there are already perfectly fine algorithms in the standard library, that's not the point.)

How would I write the same thing with for_each and a lambda? The following doesn't work...

template<typename Iter, typename T>
bool contains2(Iter begin, Iter end, const T& x)
{
    std::for_each(begin, end, [&x](const T& y) {
        if (x == y) return true;
    });
    return false;
}

...because that would only return from the lambda, not from the function.

Do I have to throw an exception to get out of the lambda? Again, there are probably a dozen better solutions to this specific problem that do not involve lambdas at all, but that's not what I'm asking for.

Answer 1

How would I write the same thing with for_each and a lambda?

You can’t (leaving aside exceptions). Your function isn’t isomorphic to a for-each loop (= kind of a mapping), it’s as simple as that.

Instead, your function is described by a reduction so if you want to use higher-order functions to replace it, use a reduction, not a map.

If C++ had an appropriate, general-purpose reduce then your algorithm would look as follows:

template<typename Iter, typename T>
bool contains2(Iter begin, Iter end, const T& x)
{
    return stdx::reduce(begin, end, [&x](const T& y, bool accumulator) {
        return accumulator or x == y;
    });
}

Of course, this only exits early if the reduction is properly specialised for boolean result values, in order to short-circuit.

Alas, C++ doesn’t offer such a functionality as far as I see. There’s accumulate but that won’t short-circuit (it can’t – C++ doesn’t know that the operation inside the lambda is short-circuited, and it isn’t implemented recursively).