A recursive_count_if Template Function with Execution Policy in C++

Question

This is a follow-up question for Avoiding requires clause if possible on a series recursive function in C++ and A recursive_count_if Function with Automatic Type Deducing from Lambda for Various Type Arbitrary Nested Iterable Implementation in C++. Thanks to indi's detailed and clear answer. I got the key point "The point is to consider what kind of type your algorithm is supposed to work for. It’s about SEMANTICS, not syntax." and I am trying to perform the suggestion ideas including "using standard concepts wherever possible" and "avoiding the unnecessary copies" on function recursive_count_if based on the previous G. Sliepen's answer.

The experimental implementation

//  recursive_count_if implementation
template<typename Pred, typename Range>
concept is_applicable_to_elements = requires(Pred& predicate, const Range &container)
{
    predicate(*container.begin());
};

template<std::ranges::input_range Range, class Pred>
requires is_applicable_to_elements<Pred, Range>
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::count_if(input.cbegin(), input.cend(), predicate);
}

template<std::ranges::input_range Range, class Pred>
requires std::ranges::input_range<std::ranges::range_value_t<Range>>
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

//  recursive_count_if implementation (with execution policy)
template<class ExPo, std::ranges::input_range Range, class Pred>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (is_applicable_to_elements<Pred, Range>)
constexpr auto recursive_count_if(ExPo execution_policy, const Range& input, const Pred& predicate)
{
    return std::count_if(execution_policy, input.cbegin(), input.cend(), predicate);
}

template<class ExPo, std::ranges::input_range Range, class Pred>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_count_if(ExPo execution_policy, const Range& input, const Pred& predicate)
{
    return std::transform_reduce(execution_policy, std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [execution_policy, predicate](auto&& element) {
        return recursive_count_if(execution_policy, element, predicate);
        });
}

Test cases

template<class T>
void recursive_count_if_test_template1()
{
    std::cout << "recursive_count_if_test_template1" << std::endl;
    
    //  std::vector<std::vector<int>> case
    std::vector<T> test_vector{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
    std::vector<decltype(test_vector)> test_vector2;
    test_vector2.push_back(test_vector);
    test_vector2.push_back(test_vector);
    test_vector2.push_back(test_vector);

    // use a lambda expression to count elements divisible by 3.
    std::cout << "#number divisible by three in test_vector2: " << recursive_count_if(std::execution::par, test_vector2, [](T i) {return i % 3 == 0; }) << '\n';

    auto test_vector3 = n_dim_container_generator<5, std::vector, decltype(test_vector)>(test_vector, 3);
    // use a lambda expression to count elements divisible by 3.
    std::cout << "#number divisible by three in test_vector3: " << recursive_count_if(std::execution::par, test_vector3, [](T i) {return i % 3 == 0; }) << '\n';


    // std::deque<std::deque<int>> case
    std::deque<T> test_deque;
    test_deque.push_back(1);
    test_deque.push_back(2);
    test_deque.push_back(3);

    std::deque<decltype(test_deque)> test_deque2;
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);

    // use a lambda expression to count elements divisible by 3.
    std::cout << "#number divisible by three in test_deque2: " << recursive_count_if(std::execution::par, test_deque2, [](T i) {return i % 3 == 0; }) << '\n';

    auto test_deque3 = n_dim_container_generator<5, std::deque, decltype(test_deque)>(test_deque, 3);
    std::cout << "#number divisible by three in test_deque3: " << recursive_count_if(std::execution::par, test_deque3, [](T i) {return i % 3 == 0; }) << '\n';
}

int main()
{
    recursive_count_if_test_template1<int>();

    recursive_count_if_test_template1<short>();

    recursive_count_if_test_template1<long>();

    recursive_count_if_test_template1<long long int>();

    recursive_count_if_test_template1<unsigned char>();

    recursive_count_if_test_template1<unsigned int>();

    recursive_count_if_test_template1<unsigned short int>();

    recursive_count_if_test_template1<unsigned long int>();

    return 0;
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

  Avoiding requires clause if possible on a series recursive function in C++ and

  A recursive_count_if Function with Automatic Type Deducing from Lambda for Various Type Arbitrary Nested Iterable Implementation in C++

• What changes has been made in the code since last question?

  • Trying to use standard concepts wherever possible

  • Avoiding the unnecessary copies

• Why a new review is being asked for?

  Thanks so much to indi and G. Sliepen. After going through the previous answers, the improved code is as above. I am not sure if there is any other problem. If there is any possible improvement, please let me know.

Answer 1

Use std::invocable

It turns out there is a standard concept to check whether a function can be applied to a (set of) argument(s): std::invocable. It's very handy combined with the following:

Avoid having to deal with ranges of ranges

I think you can avoid having to deal with "ranges of ranges", by simplifying the templates like so:

template<class T, std::invocable<T> Pred>
constexpr std::size_t recursive_count_if(const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<std::ranges::input_range Range, class Pred>
requires (!std::invocable<Pred, Range>) // see below
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

Fixing control over recursion

As pointed out by others, one big issue with these recursive functions is that there are classes that can be both seen as values or as containers themselves. For example, if we have a std::vector<std::string>, do we want to count the strings or the characters in the strings? Since you referenced this earlier question, I assume you want to have the predicate control when to end recursion. Let's add a testcase for it:

std::vector<std::string> vector_of_strings{ "Hello", "world!" };
std::cout << "Number of non-empty strings: " <<
    recursive_count_if(vector_of_strings, [](const std::string &s) {return !s.empty();}) << '\n';
std::cout << "Number of lower-case characters: " <<
    recursive_count_if(vector_of_strings, [](char c) {return std::islower(static_cast<unsigned char>(c));}) << '\n';
std::cout << "Number of things: " <<
    recursive_count_if(vector_of_strings, [](const T &i) {(void)i; return true;}) << '\n';

The expected output is:

Number of non-empty strings: 2
Number of lower-case characters: 9
Number of things: 11 // did you expect this?

Your code will fail the case of counting strings, as it cannot decide what template is more important. There are two possible fixes; the first is to not restrict the recursive template overload:

template<std::ranges::input_range Range, class Pred>
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

Since that template is now unambiguously more generic than the first one. The drawback is a more confusing error message in case you try to recursive count a container using a lambda that doesn't match any recursion level. Alternatively, restrict it even more:

template<std::ranges::input_range Range, class Pred>
requires (std::ranges::input_range<std::ranges::range_value_t<Range>> && !is_applicable_to_elements(Range, Pred))
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

Slightly better error messages. I also had to do that with my version that avoids ranges of ranges. A third alternative is to not add any requirement that the input is a range, for example:

template<class T, std::invocable<T> Pred>
constexpr std::size_t recursive_count_if(const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<class Range, class Pred>
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

However this gives very long error messages. Your version with the extra requirements gives the nicest error messages in case you do something weird like:

std::vector<int> test_vector{1, 2, 3, 4, 4, 3, 7, 8, 9, 10};
std::cout << "Number of non-empty strings: " << recursive_count_if(test_vector, [](std::string i) {return !i.empty(); }) << '\n';

Note though that your version does not handle this corner case:

std::vector<std::string> vector_of_strings{ "Hello", "world!" };
std::cout << "Number of vectors of strings: " <<
    recursive_count_if(vector_of_strings, [](const std::vector<std::string> &v) {(void)v; return true;}) << '\n';