1
\$\begingroup\$

This is a follow-up question for recursive_any_of and recursive_none_of Template Functions Implementation in C++. I am trying to follow the suggestion of G. Sliepen's answer to implement recursive_find_if_all template function in this post.

The experimental implementation

  • recursive_find_if_all Template Function Implementation

    //  recursive_find_if_all template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
requires(std::invocable<Proj, T>) && (std::invocable<UnaryPredicate, T>)
constexpr auto recursive_find_if_all(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    return std::invoke(p, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_find_if_all(T& inputRange, UnaryPredicate&& p, Proj&& proj = {}) {
    for(auto&& element : inputRange)
    {
        if(recursive_find_if_all(element, std::forward<UnaryPredicate>(p), std::forward<Proj>(proj)))
            return true;
    }
    return false;
}

Full Testing Code

The full testing code:

//  recursive_find_if_all Template Function Implementation in C++

#include <algorithm>
#include <array>
#include <chrono>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
//#include <experimental/ranges/algorithm>
#include <functional>
#include <iostream>
#include <ranges>
#include <string>
#include <utility>
#include <vector>

//  is_reservable concept
template<class T>
concept is_reservable = requires(T input)
{
    input.reserve(1);
};

//  is_sized concept, https://codereview.stackexchange.com/a/283581/231235
template<class T>
concept is_sized = requires(T x)
{
    std::size(x);
};

template<typename T>
concept is_summable = requires(T x) { x + x; };

//  recursive_unwrap_type_t struct implementation
template<std::size_t, typename, typename...>
struct recursive_unwrap_type { };

template<class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_unwrap_type<1, Container1<Ts1...>, Ts...>
{
    using type = std::ranges::range_value_t<Container1<Ts1...>>;
};

template<std::size_t unwrap_level, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_unwrap_type<unwrap_level, Container1<Ts1...>, Ts...>
{
    using type = typename recursive_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container1<Ts1...>>
        >::type;
};

template<std::size_t unwrap_level, typename T1, typename... Ts>
using recursive_unwrap_type_t = typename recursive_unwrap_type<unwrap_level, T1, Ts...>::type;

//  recursive_variadic_invoke_result_t implementation
template<std::size_t, typename, typename, typename...>
struct recursive_variadic_invoke_result { };

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<std::invoke_result_t<F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...>>;
};

template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_variadic_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<
        typename recursive_variadic_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...
        >::type>;
};

template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>
using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;

//  recursive_array_invoke_result implementation
template<std::size_t, typename, typename, typename...>
struct recursive_array_invoke_result { };

template<   typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
struct recursive_array_invoke_result<1, F, Container<T, N>>
{
    using type = Container<
        std::invoke_result_t<F, std::ranges::range_value_t<Container<T, N>>>,
        N>;
};

template<   std::size_t unwrap_level,
            typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_invoke_result<unwrap_level, F, Container<T, N>>
{
    using type = Container<
        typename recursive_array_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container<T, N>>
        >::type, N>;
};

template<   std::size_t unwrap_level,
            typename F,
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
using recursive_array_invoke_result_t = typename recursive_array_invoke_result<unwrap_level, F, Container<T, N>>::type;

//  recursive_array_unwrap_type struct implementation, https://stackoverflow.com/a/76347485/6667035
template<std::size_t, typename>
struct recursive_array_unwrap_type { };

template<template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
struct recursive_array_unwrap_type<1, Container<T, N>>
{
    using type = std::ranges::range_value_t<Container<T, N>>;
};

template<std::size_t unwrap_level, template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_unwrap_type<unwrap_level, Container<T, N>>
{
    using type = typename recursive_array_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container<T, N>>
        >::type;
};

template<std::size_t unwrap_level, class Container>
using recursive_array_unwrap_type_t = typename recursive_array_unwrap_type<unwrap_level, Container>::type;

//  https://codereview.stackexchange.com/a/253039/231235
template<template<class...> class Container = std::vector, std::size_t dim, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<Container, dim - 1, T>(input, times));
    }
}

template<std::size_t dim, std::size_t times, class T>
constexpr auto n_dim_array_generator(T input)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        std::array<decltype(n_dim_array_generator<dim - 1, times>(input)), times> output;
        for (size_t i = 0; i < times; i++)
        {
            output[i] = n_dim_array_generator<dim - 1, times>(input);
        }
        return output;
    }
}

//  recursive_depth function implementation
template<typename T>
constexpr std::size_t recursive_depth()
{
    return std::size_t{0};
}

template<std::ranges::input_range Range>
constexpr std::size_t recursive_depth()
{
    return recursive_depth<std::ranges::range_value_t<Range>>() + std::size_t{1};
}

//  recursive_depth function implementation with target type
template<typename T_Base, typename T>
constexpr std::size_t recursive_depth()
{
    return std::size_t{0};
}

template<typename T_Base, std::ranges::input_range Range>
requires (!std::same_as<Range, T_Base>)
constexpr std::size_t recursive_depth()
{
    return recursive_depth<T_Base, std::ranges::range_value_t<Range>>() + std::size_t{1};
}

/*  recursive_foreach_all template function performs specific function on input container exhaustively
    https://codereview.stackexchange.com/a/286525/231235
*/
namespace impl {

    template<class F, class Proj = std::identity>
    struct recursive_for_each_state {
        F f;
        Proj proj;
    };

    //  recursive_foreach_all template function implementation
    template<class T, class State>
    requires (recursive_depth<T>() == 0)
    constexpr void recursive_foreach_all(T& value, State& state) {
        std::invoke(state.f, std::invoke(state.proj, value));
    }

    template<class T, class State>
    requires (recursive_depth<T>() != 0)
    constexpr void recursive_foreach_all(T& inputRange, State& state) {
        for (auto& item: inputRange)
            impl::recursive_foreach_all(item, state);
    }

    //  recursive_reverse_foreach_all template function implementation
    template<class T, class State>
    requires (recursive_depth<T>() == 0)
    constexpr void recursive_reverse_foreach_all(T& value, State& state) {
        std::invoke(state.f, std::invoke(state.proj, value));
    }

    template<class T, class State>
    requires (recursive_depth<T>() != 0)
    constexpr void recursive_reverse_foreach_all(T& inputRange, State& state) {
        for (auto& item: inputRange | std::views::reverse)
            impl::recursive_reverse_foreach_all(item, state);
    }
}

template<class T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    impl::recursive_for_each_state state(std::move(f), std::move(proj));
    impl::recursive_foreach_all(inputRange, state);
    return std::make_pair(inputRange.end(), std::move(state.f));
}

template<class T, class Proj = std::identity, class F>
constexpr auto recursive_reverse_foreach_all(T& inputRange, F f, Proj proj = {})
{
    impl::recursive_for_each_state state(std::move(f), std::move(proj));
    impl::recursive_reverse_foreach_all(inputRange, state);
    return std::make_pair(inputRange.end(), std::move(state.f));
}

template<class T, class I, class F>
constexpr auto recursive_fold_left_all(const T& inputRange, I init, F f)
{
    recursive_foreach_all(inputRange, [&](auto& value) {
        init = std::invoke(f, init, value);
    });

    return init;
}

template<class T, class I, class F>
constexpr auto recursive_fold_right_all(const T& inputRange, I init, F f)
{
    recursive_reverse_foreach_all(inputRange, [&](auto& value) {
        init = std::invoke(f, value, init);
    });

    return init;
}

//  recursive_count_if template function implementation
template<class T, std::invocable<T> Pred>
requires (recursive_depth<T>() == 0)
constexpr std::size_t recursive_count_if_all(const T& input, const Pred& predicate)
{
    return predicate(input) ? std::size_t{1} : std::size_t{0};
}

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

template<std::size_t unwrap_level, class T, class Pred>
requires(unwrap_level <= recursive_depth<T>())
constexpr auto recursive_count_if(const T& input, const Pred& predicate)
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(std::ranges::cbegin(input), std::ranges::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
            return recursive_count_if<unwrap_level - 1>(element, predicate);
            });
    }
    else
    {
        return predicate(input) ? 1 : 0;
    }
    
}

/*  recursive_all_of template function implementation
*/
template<class T, class Proj = std::identity, class UnaryPredicate>
requires(std::invocable<Proj, T>) && (std::invocable<UnaryPredicate, T>)
constexpr auto recursive_all_of(T&& value, UnaryPredicate p, Proj proj = {}) {
    return std::invoke(p, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_all_of(T& inputRange, UnaryPredicate&& p, Proj proj = {}) {
    return std::ranges::all_of(inputRange, [&](auto&& range) {
        return recursive_all_of(range, std::forward<UnaryPredicate>(p), proj);
    }, proj);
}

//  recursive_find_if_all template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
requires(std::invocable<Proj, T>) && (std::invocable<UnaryPredicate, T>)
constexpr auto recursive_find_if_all(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    return std::invoke(p, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_find_if_all(T& inputRange, UnaryPredicate&& p, Proj&& proj = {}) {
    for(auto&& element : inputRange)
    {
        if(recursive_find_if_all(element, std::forward<UnaryPredicate>(p), std::forward<Proj>(proj)))
            return true;
    }
    return false;
}

//  recursive_any_of template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_any_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return recursive_find_if_all(value, p, proj);
}

//  recursive_none_of template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_none_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return !recursive_any_of(value, p, proj);
}

template<std::ranges::input_range T>
constexpr auto recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [level](auto&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range T>
requires (std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr T recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::ranges::transform(std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
        [level](auto&& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

void recursive_find_if_all_tests()
{
    std::cout << "***recursive_find_if_all_tests function***\n";

    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[1][0][0][0] = 3;
    std::cout << "Play with test_vectors_1:\n";
    if(recursive_find_if_all(test_vectors_1, [](int i) { return i == 1; }))
        std::cout << "1 is found in test_vectors_1\n";
    if(recursive_find_if_all(test_vectors_1, [](int i) { return i == 2; }))
        std::cout << "2 is found in test_vectors_1\n";
    if(recursive_find_if_all(test_vectors_1, [](int i) { return i == 3; }))
        std::cout << "3 is found in test_vectors_1\n";
    
    std::cout << "Projection Tests\n";
    if(recursive_find_if_all(test_vectors_1,
                                [](int i) { return i == 1; },
                                [](int i) { return i + 1; }))
        std::cout << "1 is found in test_vectors_1 after projection\n";
    if(recursive_find_if_all(test_vectors_1,
                                [](int i) { return i == 2; },
                                [](int i) { return i + 1; }))
        std::cout << "2 is found in test_vectors_1 after projection\n";
}

void recursive_any_of_tests()
{
    std::cout << "***recursive_any_of_tests function***\n";

    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[0][0][0][0] = 3;
    std::cout << "Play with test_vectors_1:\n";
    
    if (recursive_any_of(test_vectors_1, [](int i) { return i == 2; }))
        std::cout << "2 is one of the elements in test_vectors_1\n";

    if (recursive_any_of(test_vectors_1, [](int i) { return i == 3; }))
        std::cout << "3 is one of the elements in test_vectors_1\n";

    std::cout << "Projection Tests\n";
    if(recursive_any_of(test_vectors_1,
                                [](int i) { return i == 1; },
                                [](int i) { return i + 1; }))
        std::cout << "1 is one of the elements in test_vectors_1 after projection\n";
    if(recursive_any_of(test_vectors_1,
                                [](int i) { return i == 2; },
                                [](int i) { return i + 1; }))
        std::cout << "2 is one of the elements in test_vectors_1 after projection\n";
}

void recursive_none_of_tests()
{
    std::cout << "***recursive_none_of_tests function***\n";

    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[0][0][0][0] = 3;
    std::cout << "Play with test_vectors_1:\n";
    
    if (recursive_none_of(test_vectors_1, [](int i) { return i == 0; }))
        std::cout << "None of the elements in test_vectors_1 is 0\n";

    std::cout << "Projection Tests\n";
    if(recursive_none_of(test_vectors_1,
                                [](int i) { return i == 0; },
                                [](int i) { return i + 1; }))
        std::cout << "None of the elements in test_vectors_1 is 0 after projection\n";
    if(recursive_none_of(test_vectors_1,
                                [](int i) { return i == 1; },
                                [](int i) { return i + 1; }))
        std::cout << "None of the elements in test_vectors_1 is 1 after projection\n";
    if(recursive_none_of(test_vectors_1,
                                [](int i) { return i == 2; },
                                [](int i) { return i + 1; }))
        std::cout << "None of the elements in test_vectors_1 is 2 after projection\n";
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_find_if_all_tests();
    recursive_any_of_tests();
    recursive_none_of_tests();
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    std::cout << "Computation finished at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << '\n';
    return 0;
}

The output of the test code above:

***recursive_find_if_all_tests function***
Play with test_vectors_1:
1 is found in test_vectors_1
3 is found in test_vectors_1
Projection Tests
2 is found in test_vectors_1 after projection
***recursive_any_of_tests function***
Play with test_vectors_1:
3 is one of the elements in test_vectors_1
Projection Tests
2 is one of the elements in test_vectors_1 after projection
***recursive_none_of_tests function***
Play with test_vectors_1:
None of the elements in test_vectors_1 is 0
Projection Tests
None of the elements in test_vectors_1 is 0 after projection
None of the elements in test_vectors_1 is 1 after projection
Computation finished at Tue Jan 23 13:11:35 2024
elapsed time: 0.0013986

Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    recursive_any_of and recursive_none_of Template Functions Implementation in C++

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

    I am trying to implement recursive_find_if_all template function in this post.

  • Why a new review is being asked for?

    Please review the recursive_find_if_all template function. In this version, the techniques including early termination are performed.

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

The problem seems so simple, and at first glance the implementation looks OK. However, looks can be deceiving; there are actually lots of issues with this code.

Never std::forward() the same object multiple times

You are calling std::forward() multiple times on the same p and proj. This will result in undefined behavior if p and/or proj are rvalues, as then it will be equivalent to std::moveing from them multiple times.

Just omit std::forward(). Also note that std::ranges::find_if() takes the predicate and projection by value. You could do that too, but then you might be making lots of copies if the predicate and/or projection have state, which is inefficient and might not be what the caller expects.

Implement recursive algorithms using their non-recursive counterparts

You should be able to use std::ranges::find_if() to build your recursive version. In fact, most recursive algorithms you have written so far do or can use the following pattern for the recursing case:

template<std::ranges::some_range R, class Pred, …>
auto recursive_algorithm(R&& r, Pred p, …) {
    return std::non_recursive_algorithm(r, [&](auto& element) {
        return recursive_algorithm(element, p, …);
    });
}

Some minor changes to the pattern are necessary depending on the exact algorithm you are implementing. So for finding, you could write:

template<std::ranges::input_range T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_find_if_all(T&& inputRange, UnaryPredicate&& p, Proj&& proj = {}) {
    return std::ranges::find_if(inputRange, [&](auto& element) {
        return recursive_find_if_all(element, p, proj);
    }) != std::ranges::end(inputRange);
}

The requires clause is incorrect

You wrote:

requires(std::invocable<Proj, T>) && (std::invocable<UnaryPredicate, T>)

However, the predicate will not be applied directly to a T, but rather to the projection of a T. So you should instead do something like:

requires(std::invocable<UnaryPredicate, std::invoke_result_t<Proj, T>>)

However, that is not the only issue. Consider that the caller might not actually know what the value type of the innermost range is, for example because the caller might be some other generic algorithm you want to apply on top of recursive_find_if_all(). So they might use a generic lambda as a predicate:

bool contains_zeroes(auto&& range) {
    return recursive_find_if_all(range, [](auto& value){ return value == 0; });
}

The above algorithm will work with integers, floating point numbers, complex numbers and potentially lots of other types. But the problem is that the lambda accepts any type of value, so it will match range types as well. That means it will immediately invoke the non-recursing version of recursive_find_if_all(), which is very likely not what you want. Constraining the recursing version as well will help here.

Other issues

  • Your recursing version of recursive_find_if_all() takes inputRange by lvalue reference, whereas the non-recursing one takes it by forwarding reference. They should all take the range by forwarding reference (just like the STL algorithms do).
  • The predicate does not have to return a bool, as long as it returns something that can be explicitly cast to a bool. Because you use auto return type for both recursing and non-recursing versions, it can be that for some inputs, the result type of recursive_find_if_all() will be a bool, but for other inputs it could be a different type, even if the exact same predicate is used.
  • There is no requires clause on the recursing version. If you pass in an incorrect predicate or projection, then while eventually it will hit the requires clause of the non-recursing version, that will result in a very complicated error message. Putting one on the recursing version as well will result in a much better error message.
  • Your test suite is evidently still not comprehensive enough, as it didn't catch some of the issues I've mentioned.
  • Naming: recursive_find_if_all() makes it sounds like it tries to "find if all" items match the predicate. Maybe just recursive_find_if()?
\$\endgroup\$
3
  • \$\begingroup\$ Sorry, I am not familiar with std::forward(). So, how can I deal with r-value references correctly with avoiding making lots of copies in recursive processes? \$\endgroup\$ Commented Jan 24, 2024 at 13:15
  • 1
    \$\begingroup\$ Just don't use std::forward() here. Then when recursing, the predicate and projection will be passed by lvalue reference, which is what you want here. Basically, std::forward() does nothing if UnaryPredicate/Projection is an lvalue, and it will do std::move() it is an rvalue. \$\endgroup\$ Commented Jan 24, 2024 at 18:19
  • \$\begingroup\$ The reason of naming recursive_find_if_all with "all" is because this recursive function with no unwrap_level specified. The word "all" means "all level". But yeah, it's ambiguous to "find if all" items match the predicate. Is there any better way to name it? \$\endgroup\$ Commented Jan 26, 2024 at 6:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.