2
\$\begingroup\$

This is a follow-up question for A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++. Thanks to G. Sliepen's answer. Based on the mentioned suggestion, the naming of the function for getting the element count in arbitrary nested iterables is updated into recursive_size. Here, I am trying to implement the functions (recursive_count and recursive_count_if) which purpose are similar to std::count and std::count_if and can be used in various type arbitrary nested iterable things. In the template function recursive_count, the first parameter is an input nested iterable object and the second parameter is the target value to search for.

//  recursive_count implementation
template<class T1, class T2> requires (!is_elements_iterable<T1> && is_iterable<T1>)
auto recursive_count(const T1& input, const T2 target)
{
    return std::count(input.begin(), input.end(), target);
}

//  for loop version
template<class T1, class T2> requires (is_elements_iterable<T1>)
auto recursive_count(const T1& input, const T2 target)
{
    size_t output{};
    for (auto &element : input)
    {
        output += recursive_count(element, target);
    }
    return output;
}

In the template function recursive_count_if, the first parameter is also an input nested iterable object and the second parameter is a unary predicate which returns ​true for the required elements.

//  recursive_count_if implementation
template<class T1, class T2> requires (!is_elements_iterable<T1> && is_iterable<T1>)
auto recursive_count_if(const T1& input, const T2 predicate)
{
    return std::count_if(input.begin(), input.end(), predicate);
}

//  for loop version
template<class T1, class T2> requires (is_elements_iterable<T1>)
auto recursive_count_if(const T1& input, const T2 predicate)
{
    size_t output{};
    for (auto &element : input)
    {
        output += recursive_count_if(element, predicate);
    }
    return output;
}

Some test cases for recursive_count template function:

//  std::vector<std::vector<int>> case
std::vector<int> 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);

// determine how many integers in a std::vector<std::vector<int>> match a target value.
int target1 = 3;
int target2 = 5;
int num_items1 = recursive_count(test_vector2, target1);
int num_items2 = recursive_count(test_vector2, target2);
std::cout << "number: " << target1 << " count: " << num_items1 << '\n';
std::cout << "number: " << target2 << " count: " << num_items2 << '\n';

// std::deque<std::deque<int>> case
std::deque<int> 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);

// determine how many integers in a std::deque<std::deque<int>> match a target value.
int num_items3 = recursive_count(test_deque2, target1);
int num_items4 = recursive_count(test_deque2, target2);
std::cout << "number: " << target1 << " count: " << num_items3 << '\n';
std::cout << "number: " << target2 << " count: " << num_items4 << '\n';

Some test cases for recursive_count_if template function:

//  std::vector<std::vector<int>> case
std::vector<int> 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.
int num_items1 = recursive_count_if(test_vector2, [](int i) {return i % 3 == 0; });
std::cout << "#number divisible by three: " << num_items1 << '\n';

// std::deque<std::deque<int>> case
std::deque<int> 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.
int num_items2 = recursive_count_if(test_deque2, [](int i) {return i % 3 == 0; });
std::cout << "#number divisible by three: " << num_items2 << '\n';

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++

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

    • The function for getting the element count in arbitrary nested iterables is renamed into recursive_size.

    • Besides the total element count, I am trying to implement the functions (recursive_count and recursive_count_if) which purpose are similar to std::count and std::count_if and can be used in various type arbitrary nested iterable things here.

  • Why a new review is being asked for?

    As similar as G. Sliepen's answer mentioned, there is another version of the last overload recursive_count template function implementation with std::transform_reduce:

    //  transform_reduce version
    template<class T1, class T2> requires (is_elements_iterable<T1>)
    auto recursive_count(const T1& input, const T2 target)
    {
        return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [target](auto& element) {
            return recursive_count(element, target);
            });
    }
    

    Also, there is another version of the last overload recursive_count_if template function implementation with std::transform_reduce:

    //  transform_reduce version
    template<class T1, class T2> requires (is_elements_iterable<T1>)
    auto recursive_count_if(const T1& input, const T2 predicate)
    {
        return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto& element) {
            return recursive_count_if(element, predicate);
            });
    }
    

    I am wondering which version is more readable.

    A Godbolt link for this (using std::transform_reduce) version is here.

    If there is any possible improvement, please let me know.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Instead of asking for a review of one algorithm at a time, maybe it makes sense to write a library with recursive versions of all the STL algorithms, and submit that as one review? \$\endgroup\$ – G. Sliepen Nov 13 '20 at 16:07
  • 2
    \$\begingroup\$ @G.Sliepen Thank you for the comment. If building a library about these recursive functions then submitting as one review is better than asking one by one. I am going to do that. \$\endgroup\$ – JimmyHu Nov 13 '20 at 16:13
  • 2
    \$\begingroup\$ FWIW, I think "please review my library" might fall too easily foul of the site rules like "provide the code, not [merely] a link to the code" and "keep the amount of code manageable." On the other hand, it would definitely reduce the amount of repetition happening in these questions. Jimmy has to keep explaining what concept is_iterable does, for example. \$\endgroup\$ – Quuxplusone Nov 15 '20 at 19:41
  • \$\begingroup\$ @Quuxplusone Based on your comment, it seems not a good idea to propose "a library" to review, does it? \$\endgroup\$ – JimmyHu Nov 16 '20 at 0:19
3
\$\begingroup\$

I think recursive_count_if is a bad API to begin with, because by design it can't work on a lot of types. Consider:

std::vector<std::vector<std::string>> v = {{"hello"}, {"world"}};
auto size5 = [](std::string s) { return s.size() == 5; };
auto n = recursive_count_if(v, size5);

With your current implementation, this doesn't work, right?

Worse, if the STL's std::string were non-explicitly constructible from char, like this—

std::string example = 'x';  // fortunately does not compile today

—then the above snippet would compile, and set n to zero. Because it would call size5('h'), size5('e'), size5('l'), and so on, each of which would evaluate to false. This is certainly not what the programmer intended!

I think the user of this API should have to tell the function explicitly how many "levels" to unwrap downward: recursive_count_if<0>(r, p) should be std::ranges::count_if(r, p), and then recursive_count_if<1>(r, p) should be what the user intends in the above snippet, and so on.

In fact, maybe you should just implement a flatten filter that takes a "range of ranges of E" and returns a "range of E." Then recursive_count_if<1>(r, p) would simply be std::ranges::count_if(flatten(r), p), and recursive_count_if<2>(r, p) would be std::ranges::count_if(flatten(flatten(r)), p), and so on. I like that API a lot better.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Good point about std::string. But maybe it can be made to work if recursion stops automatically if, for recursive_count(), the container's value_type matches T2 (or rather, that T2{}==(*T1{}.begin()) is a valid expression), and in the case of recursive_count_if, if T2::operator()(*T1{}.begin()) is a valid expression? \$\endgroup\$ – G. Sliepen Nov 15 '20 at 23:18
  • 1
    \$\begingroup\$ @JimmyHu: You're trying to specialize foo<0, T1, T2> differently from foo<N, T1, T2>, right? Think about how you could use if constexpr here; or, pre-C++17, think about what you could do with overload resolution if foo<I, T1, T2> consists of the single statement return fooImpl<T1, T2>(std::index_constant<I>(), r, p);. </hint> \$\endgroup\$ – Quuxplusone Nov 16 '20 at 14:55
  • 1
    \$\begingroup\$ @G.Sliepen: Think about when p is a generic lambda. In general, "figuring out the argument type of a callable" is a fool's errand. See quuxplusone.github.io/blog/2018/06/12/perennial-impossibilities/… \$\endgroup\$ – Quuxplusone Nov 16 '20 at 15:07
  • 1
    \$\begingroup\$ @G.Sliepen: Right, "check whether applying p to a T1 is well-formed" is easy and unambiguous; but then it requires the user to define their predicate p so that it is SFINAE-friendly, which generic lambdas aren't, in general. E.g. try your idea with recursive_count_if(vec_of_vec_of_string, [](const auto& s) { return s.starts_with("foo"); }). It blows up because p(vec_of_vec_of_string[0]) seems well-formed yet when we go to instantiate p's body we find that vector<string> has no member function starts_with (and by then it's too late to backtrack). \$\endgroup\$ – Quuxplusone Nov 16 '20 at 17:40
  • 2
    \$\begingroup\$ Vice versa, if p were, like, [](auto x) { return x.size()==5; }, then the question arises whether we might want to apply it at multiple levels! Is this like that "How many squares do you see?" brainteaser? :) Really, I just think it's a bad API. Using a library API as simple as count_if shouldn't require the user to solve a puzzle. \$\endgroup\$ – Quuxplusone Nov 16 '20 at 17:45

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.