1
\$\begingroup\$

This is a follow-up question for A recursive_depth function for calculating depth of nested types implementation in C++ and A recursive_count Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++. I am trying to follow G. Sliepen's answer to implement another version of recursive_count function using recursive_depth for unwrap_level checking.

The experimental implementation

  • recursive_count function:

    //  recursive_count implementation
    
    //  recursive_count implementation (the version with unwrap_level)
    template<std::size_t unwrap_level, class T>
    constexpr auto recursive_count(const T& input, const auto& target)
    {
        if constexpr (unwrap_level > 0)
        {
            static_assert(unwrap_level <= recursive_depth<T>(),
                "unwrap level higher than recursion depth of input");
            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 (the version without unwrap_level)
    template<std::ranges::input_range Range>
    constexpr auto recursive_count(const Range& input, const auto& target)
    {
        return recursive_count<recursive_depth<Range>()>(input, target);
    }
    
  • recursive_depth function:

    //  recursive_depth function implementation
    template<typename T>
    constexpr std::size_t recursive_depth()
    {
        return 0;
    }
    
    template<std::ranges::input_range Range>
    constexpr std::size_t recursive_depth()
    {
        return recursive_depth<std::ranges::range_value_t<Range>>() + 1;
    }
    

The testing code

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

    //  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) << '\n';

    //  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") << '\n';

    //  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") << '\n';

    //  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) << '\n';

    //  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) << '\n';

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


    //  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) << '\n';

    std::cout << recursive_count<11>(
        n_dim_container_generator<10, std::list>(test_list, 3),
        1
        ) << '\n';
}

Full Testing Code

The full testing code:

#include <algorithm>
#include <array>
#include <concepts>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <numeric>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include <ranges>

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

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

//  recursive_count implementation

//  recursive_count implementation (the version with unwrap_level)
template<std::size_t unwrap_level, class T>
constexpr auto recursive_count(const T& input, const auto& target)
{
    if constexpr (unwrap_level > 0)
    {
        static_assert(unwrap_level <= recursive_depth<T>(),
            "unwrap level higher than recursion depth of input");
        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 (the version without unwrap_level)
template<std::ranges::input_range Range>
constexpr auto recursive_count(const Range& input, const auto& target)
{
    return recursive_count<recursive_depth<Range>()>(input, target);
}

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));
    }
}

void recursive_depth_test();
void recursive_count_test();

int main()
{
    recursive_count_test();
}

void recursive_depth_test()
{
    //  non-nested type `char`
    char test_char = 'A';
    std::cout << recursive_depth<decltype(test_char)>() << '\n';
    
    //  non-nested type `int`
    int test_int = 100;
    std::cout << recursive_depth<decltype(test_int)>() << '\n';
    
    //  std::vector<int>
    std::vector<int> test_vector{ 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
    std::cout << recursive_depth<decltype(test_vector)>() << '\n';

    //  std::vector<std::vector<int>>
    std::vector<decltype(test_vector)> test_vector2{ test_vector , test_vector , test_vector };
    std::cout << recursive_depth<decltype(test_vector2)>() << '\n';

    //  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_depth<decltype(test_deque)>() << '\n';

    //  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_depth<decltype(test_deque2)>() << '\n';

    //  std::list<int>
    std::list<int> test_list = { 1, 2, 3, 4, 5, 6 };
    std::cout << recursive_depth<decltype(test_list)>() << '\n';


    //  std::list<std::list<int>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
    std::cout << recursive_depth<decltype(test_list2)>() << '\n';
}

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

    //  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) << '\n';

    //  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") << '\n';

    //  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") << '\n';

    //  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) << '\n';

    //  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) << '\n';

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


    //  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) << '\n';

    std::cout << recursive_count<11>(
        n_dim_container_generator<10, std::list>(test_list, 3),
        1
        ) << '\n';
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$
2
\$\begingroup\$

Missing test cases

I don't see any test cases being added for the version of recursive_count() that doesn't take an unwrap level. Also, add test cases for corner cases, most importantly trying to apply recursive_count<0>() on ranges and applying recursive_count() on non-ranges. For example, consider adding the following test cases:

assert(recursive_count<0>(1, 2) == 0);
assert(recursive_count<0>(0, 0) == 1);

This will compile and run correctly. However, the following does not:

assert(recursive_count(1, 2) == 0);
assert(recursive_count(0, 0) == 1);

This will fail to compile with your code because your recursive_count() without an unwrap level only works on ranges. The fix is to make it template<typename T> instead of template<std::ranges::input_range Range>.

\$\endgroup\$
1
\$\begingroup\$
       if (input == target)
        {
            return 1;
        }
        else
        {
            return 0;
        }

Write this clearly as:
return (input == target) ? 1 : 0;

The cognitive overhead of what you wrote is quite high: the reader sees an if statement so the code does two different things. Then, each thing is a return statement. Ah, it returns either way, you always want to return -- you just want to condition to specify which value is returned.

So write it directly, rather than making the reader reverse-engineer that meaning.

I want to impress that it's not just "terse" for its own sake. The single statement is easier to read and understand, since it directly states the intent. In general, don't duplicate more than necessary in your conditional branches. If the condition is just to affect some values, don't repeat the function calls and unaffected values.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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