A recursive_count Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++

Question

This is a follow-up question for A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++, A recursive_count_if Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++ and A Function Applier for Applying Various Algorithms on Nested Container Things in C++. I am trying to use unwrap level template parameter as the termination condition of the recursion process in recursive_count template function.

The experimental implementation

The experimental implementation of recursive_count function is as below.

//  recursive_count implementation (the version with unwrap_level)
template<std::size_t unwrap_level, class T, typename ValueType>
constexpr auto recursive_count(const T& input, const ValueType& target)
{
    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>(), [&target](auto&& element) {
            return recursive_count<unwrap_level - 1>(element, target);
            });
    }
    else
    {
        if (input == target)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}

Test cases

The std::vector<int>, std::vector<std::vector<int>>, std::vector<std::string>, std::vector<std::vector<std::string>>, std::deque<int>, std::deque<std::deque<int>>, std::list<int> and std::list<std::list<int>> type input test case has been listed as below.

std::vector<int> test_vector{ 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
std::cout << recursive_count<1>(test_vector, 5) << std::endl;

//  std::vector<std::vector<int>>
std::vector<decltype(test_vector)> test_vector2{ test_vector , test_vector , test_vector };
std::cout << recursive_count<2>(test_vector2, 5) << std::endl;

//  std::vector<std::string>
std::vector<std::string> test_string_vector{ "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20" };
std::cout << recursive_count<1>(test_string_vector, "0") << std::endl;

//  std::vector<std::vector<std::string>>
std::vector<decltype(test_string_vector)> test_string_vector2{ test_string_vector , test_string_vector , test_string_vector };
std::cout << recursive_count<2>(test_string_vector2, "0") << std::endl;

//  std::deque<int>
std::deque<int> test_deque;
test_deque.push_back(1);
test_deque.push_back(2);
test_deque.push_back(3);
test_deque.push_back(4);
test_deque.push_back(5);
test_deque.push_back(6);
std::cout << recursive_count<1>(test_deque, 1) << std::endl;

//  std::deque<std::deque<int>>
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);
std::cout << recursive_count<2>(test_deque2, 1) << std::endl;

//  std::list<int>
std::list<int> test_list = { 1, 2, 3, 4, 5, 6 };
std::cout << recursive_count<1>(test_list, 1) << std::endl;


//  std::list<std::list<int>>
std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
std::cout << recursive_count<2>(test_list2, 1) << std::endl;

std::cout << recursive_count<11>(
        n_dim_container_generator<10, std::list>(test_list, 3),
        1
        ) << std::endl;

Full Testing Code

The full testing code:

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <exception>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <optional>
#include <ranges>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

//  recursive_copy_if function 
template <std::ranges::input_range Range, std::invocable<std::ranges::range_value_t<Range>> UnaryPredicate>
constexpr auto recursive_copy_if(const Range& input, const UnaryPredicate& unary_predicate)
{
    Range output{};
    std::ranges::copy_if(std::ranges::cbegin(input), std::ranges::cend(input),
        std::inserter(output, std::ranges::end(output)),
        unary_predicate);
    return output;
}

template <
    std::ranges::input_range Range,
    class UnaryPredicate>
constexpr auto recursive_copy_if(const Range& input, const UnaryPredicate& unary_predicate)
{
    Range output{};
    
    std::ranges::transform(
        std::ranges::cbegin(input),
        std::ranges::cend(input),
        std::inserter(output, std::ranges::end(output)),
        [&unary_predicate](auto&& element) { return recursive_copy_if(element, unary_predicate); }
        );
    return output;
}

//  recursive_count implementation
template<std::ranges::input_range Range, typename T>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::count(std::ranges::cbegin(input), std::ranges::cend(input), target);
}

//  transform_reduce version
template<std::ranges::input_range Range, typename T>
requires std::ranges::input_range<std::ranges::range_value_t<Range>>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::transform_reduce(std::ranges::cbegin(input), std::ranges::cend(input), std::size_t{}, std::plus<std::size_t>(), [target](auto&& element) {
        return recursive_count(element, target);
        });
}

//  recursive_count implementation (the version with unwrap_level)
template<std::size_t unwrap_level, class T, typename ValueType>
constexpr auto recursive_count(const T& input, const ValueType& target)
{
    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>(), [&target](auto&& element) {
            return recursive_count<unwrap_level - 1>(element, target);
            });
    }
    else
    {
        if (input == target)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}

//  recursive_count implementation (with execution policy)
template<class ExPo, std::ranges::input_range Range, typename T>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_count(ExPo execution_policy, const Range& input, const T& target)
{
    return std::count(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), target);
}

template<class ExPo, std::ranges::input_range Range, typename T>
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(ExPo execution_policy, const Range& input, const T& target)
{
    return std::transform_reduce(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::size_t{}, std::plus<std::size_t>(), [execution_policy, target](auto&& element) {
        return recursive_count(execution_policy, element, target);
        });
}

//  recursive_count_if implementation
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>)
constexpr auto recursive_count_if(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(element, predicate);
    });
}

//  recursive_count_if implementation (with execution policy)
template<class ExPo, class T, std::invocable<T> Pred>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr std::size_t recursive_count_if(ExPo execution_policy, const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

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

//  recursive_count_if implementation (the version with unwrap_level)
template<std::size_t unwrap_level, std::ranges::range T, class Pred>
auto recursive_count_if(const T& input, const Pred& predicate)
{
    if constexpr (unwrap_level > 1)
    {
        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 std::count_if(std::ranges::cbegin(input), std::ranges::cend(input), predicate);
    }
}

//  recursive_function_applier implementation
template<std::size_t unwrap_level, class F, std::ranges::range Range, class... Args>
constexpr auto recursive_function_applier(const F& function, const Range& input, Args... args)
{
    if constexpr (unwrap_level >= 1)
    {
        Range output{};
        std::ranges::transform(
            std::ranges::cbegin(input),
            std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            [&function, &args...](auto&& element) { return recursive_function_applier<unwrap_level - 1>(function, element, args...); }
        );
        return output;
    }
    else
    {
        Range output{};
        function(
            std::ranges::cbegin(input),
            std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            args...);
        return output;
    }
}

//  recursive_print implementation
template<std::ranges::input_range Range>
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto 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&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range Range> requires (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto 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;
}

//  recursive_replace_copy_if implementation
template<std::ranges::range Range, std::invocable<std::ranges::range_value_t<Range>> UnaryPredicate, class T>
constexpr auto recursive_replace_copy_if(const Range& input, const UnaryPredicate& unary_predicate, const T& new_value)
{
    Range output{};
    std::ranges::replace_copy_if(
        std::ranges::cbegin(input),
        std::ranges::cend(input),
        std::inserter(output, std::ranges::end(output)),
        unary_predicate,
        new_value);
    return output;
}

template<std::ranges::input_range Range, class UnaryPredicate, class T>
requires (!std::invocable<UnaryPredicate, std::ranges::range_value_t<Range>>)
constexpr auto recursive_replace_copy_if(const Range& input, const UnaryPredicate& unary_predicate, const T& new_value)
{
    Range output{};

    std::ranges::transform(
        std::ranges::cbegin(input),
        std::ranges::cend(input),
        std::inserter(output, std::ranges::end(output)),
        [&unary_predicate, &new_value](auto&& element) { return recursive_replace_copy_if(element, unary_predicate, new_value); }
    );
    return output;
}

//  recursive_size implementation
template<class T> requires (!std::ranges::range<T>)
constexpr auto recursive_size(const T& input)
{
    return 1;
}

template<std::ranges::range Range> requires (!(std::ranges::input_range<std::ranges::range_value_t<Range>>))
constexpr auto recursive_size(const Range& input)
{
    return std::ranges::size(input);
}

template<std::ranges::range Range> requires (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_size(const Range& input)
{
    return std::transform_reduce(std::ranges::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [](auto& element) {
        return recursive_size(element);
        });
}

//  recursive_transform implementation
//  recursive_invoke_result_t implementation
//  from https://stackoverflow.com/a/65504127/6667035
template<typename, typename>
struct recursive_invoke_result { };

template<typename T, std::invocable<T> F>
struct recursive_invoke_result<F, T> { using type = std::invoke_result_t<F, T>; };

template<typename F, template<typename...> typename Container, typename... Ts>
requires (
    !std::invocable<F, Container<Ts...>> &&
    std::ranges::input_range<Container<Ts...>> &&
    requires { typename recursive_invoke_result<F, std::ranges::range_value_t<Container<Ts...>>>::type; })
struct recursive_invoke_result<F, Container<Ts...>>
{
    using type = Container<typename recursive_invoke_result<F, std::ranges::range_value_t<Container<Ts...>>>::type>;
};

template<typename F, typename T>
using recursive_invoke_result_t = typename recursive_invoke_result<F, T>::type;

template <std::ranges::range Range>
constexpr auto get_output_iterator(Range& output)
{
    return std::inserter(output, std::ranges::end(output));
}

template <class T, std::invocable<T> F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

template <
    std::ranges::input_range Range,
    class F>
requires (!std::invocable<F, Range>)
constexpr auto recursive_transform(const Range& input, const F& f)
{
    recursive_invoke_result_t<F, Range> output{};
    
    std::ranges::transform(
        std::ranges::cbegin(input),
        std::ranges::cend(input),
        std::inserter(output, std::ranges::end(output)),
        [&f](auto&& element) { return recursive_transform(element, f); }
        );
    return output;
}

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

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
    {
        auto element = n_dim_array_generator<dim - 1, times>(input);
        std::array<decltype(element), times> output;
        std::fill(std::begin(output), std::end(output), element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_deque_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_deque_generator<dim - 1>(input, times);
        std::deque<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_list_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_list_generator<dim - 1>(input, times);
        std::list<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, template<class...> class Container = std::vector, 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<dim - 1, Container, T>(input, times));
    }
}

int main()
{
    std::vector<int> test_vector{ 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
    std::cout << recursive_count<1>(test_vector, 5) << std::endl;

    //  std::vector<std::vector<int>>
    std::vector<decltype(test_vector)> test_vector2{ test_vector , test_vector , test_vector };
    std::cout << recursive_count<2>(test_vector2, 5) << std::endl;

    //  std::vector<std::string>
    std::vector<std::string> test_string_vector{ "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20" };
    std::cout << recursive_count<1>(test_string_vector, "0") << std::endl;

    //  std::vector<std::vector<std::string>>
    std::vector<decltype(test_string_vector)> test_string_vector2{ test_string_vector , test_string_vector , test_string_vector };
    std::cout << recursive_count<2>(test_string_vector2, "0") << std::endl;

    //  std::deque<int>
    std::deque<int> test_deque;
    test_deque.push_back(1);
    test_deque.push_back(2);
    test_deque.push_back(3);
    test_deque.push_back(4);
    test_deque.push_back(5);
    test_deque.push_back(6);
    std::cout << recursive_count<1>(test_deque, 1) << std::endl;

    //  std::deque<std::deque<int>>
    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);
    std::cout << recursive_count<2>(test_deque2, 1) << std::endl;

    //  std::list<int>
    std::list<int> test_list = { 1, 2, 3, 4, 5, 6 };
    std::cout << recursive_count<1>(test_list, 1) << std::endl;


    //  std::list<std::list<int>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
    std::cout << recursive_count<2>(test_list2, 1) << std::endl;

    std::cout << recursive_count<11>(
            n_dim_container_generator<10, std::list>(test_list, 3),
            1
            ) << std::endl;
    return 0;
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++,

A recursive_count_if Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++ and

A Function Applier for Applying Various Algorithms on Nested Container Things in C++
What changes has been made in the code since last question?

The implementation of recursive_count function with unwrap level is the main idea here.
Why a new review is being asked for?

In the base comparison part, not sure using input == target as the equivalence condition is OK because ValueType and T may be different. The definition of == operator between ValueType and T is required in this design. If there is any possible improvement, please let me know.

G. Sliepen · Accepted Answer · 2021-10-23 20:04:19Z

Comparing using `==` is fine

In the base comparison part, not sure using input == target as the equivalence condition is OK because ValueType and T may be different.

This is fine, it does exactly what std::count() does, and I wouldn't know how else to compare two values for equivalence, apart from passing a predicate function, but then it would become a recursive_count_if().

Use `std::ranges::count`

For the non-recursive version of recursive_count(), you can just call std::ranges::count():

template<std::ranges::input_range Range, typename T>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::ranges::count(input, target);
}

Unfortunately, there is no std::ranges::transform_reduce() in C++20, but it might come in C++23.

Make use of `auto` parameter types

While this doesn't change anything, it might make the code clearer if you use auto for parameters that you don't want the caller to explicitly pass template types for, and template<> for those that it should. So for example:

template<std::size_t unwrap_level>
constexpr auto recursive_count(const auto& input, const auto& target)
{
    ...
}

Avoid code duplication

You have two versions of recursive_count(), one which takes an unwrap_level parameter, and another which doesn't. You can avoid implementing the latter version by calling the first one with the maximum recursion depth of the input argument:

template<std::ranges::input_range Range, typename T>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return recursive_count<recursive_depth<Range>()>(input, target);
}

Implementing recursive_depth() is left as an excercise.

Consider checking if `unwrap_level` is too high

If you call recursive_count() with an unwrap_level higher than the recursion depth of input, you'll get a very long and unreadable compiler error message. Consider adding a constraint or static_assert() to make it easier to debug this. For example:

template<std::size_t unwrap_level, class T, typename ValueType>
constexpr auto recursive_count(const T& input, const ValueType& target)
{
    if constexpr (unwrap_level > 0)
    {
        static_assert(unwrap_level <= recursive_depth<T>(),
                      "unwrap level higher than recursion depth of input");
        ...

user673679 · Accepted Answer · 2021-10-23 20:52:22Z

In addition to G. Sliepen's answer:

Return Type

std::count returns a difference_type (i.e. std::ptrdiff_t).
std::transform_reduce returns a std::size_t (because that's what we specify as the "init" argument).
The other two return statements return 1; and return 0; are integers.

So with the auto return type, the user will get a type depending on what version of the function they call, and how exactly they call it.

I'd probably just go with specifying std::size_t for the return type, but an argument could be made for using difference_type from the relevant iterator traits instead.

Stack Exchange Network

A recursive_count Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++

2 Answers 2

Comparing using `==` is fine

Use `std::ranges::count`

Make use of `auto` parameter types

Avoid code duplication

Consider checking if `unwrap_level` is too high

Return Type

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
recursion
template
c++20
or ask your own question.

Linked

Hot Network Questions

A recursive_count Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++

2 Answers 2

Comparing using == is fine

Use std::ranges::count

Make use of auto parameter types

Avoid code duplication

Consider checking if unwrap_level is too high

Return Type

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++recursiontemplatec++20 or ask your own question.

Linked

Related

Hot Network Questions

Comparing using `==` is fine

Use `std::ranges::count`

Make use of `auto` parameter types

Consider checking if `unwrap_level` is too high

Not the answer you're looking for? Browse other questions tagged
c++
recursion
template
c++20
or ask your own question.