2
\$\begingroup\$

This is a follow-up question for A recursive_copy_if Template Function Implementation in C++. Besides the recursive version std::ranges::copy_if, I am trying to implement a recursive version std::replace_copy_if.

The experimental implementation

The experimental implementation is as below.

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

Test cases

The test cases for recursive_replace_copy_if function including 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 are as below.

int main()
{
    std::vector<int> test_vector{ 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
    recursive_print(recursive_replace_copy_if(test_vector, std::bind(std::less<int>(), std::placeholders::_1, 5), 55));
    recursive_print(test_vector);

    std::vector<decltype(test_vector)> test_vector2{ test_vector , test_vector , test_vector };
    recursive_print(recursive_replace_copy_if(test_vector2, std::bind(std::less<int>(), std::placeholders::_1, 5), 55));

    //  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" };
    recursive_print(
        recursive_replace_copy_if(
            test_string_vector, [](std::string x) { return (x == "1"); }, "11"
        )
    );

    //  std::vector<std::vector<std::string>>
    std::vector<decltype(test_string_vector)> test_string_vector2{ test_string_vector , test_string_vector , test_string_vector };
    recursive_print(
        recursive_replace_copy_if(
            test_string_vector2, [](std::string x) { return (x == "1"); }, "11"
        )
    );

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

    recursive_print(recursive_replace_copy_if(test_deque, [](int x) { return (x % 2) == 0; }, 0));
    
    //  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);

    recursive_print(recursive_replace_copy_if(test_deque2, [](int x) { return (x % 2) == 0; }, 0));

    //  std::list<int>
    std::list<int> test_list = { 1, 2, 3, 4, 5, 6 };

    recursive_print(recursive_replace_copy_if(test_list, [](int x) { return (x % 2) == 0; }, 0));


    //  std::list<std::list<int>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };

    recursive_print(recursive_replace_copy_if(test_list2, [](int x) { return (x % 2) == 0; }, 0));

    return 0;
}

The output of the testing code above:

Level 0:
 5
 7
 55
 55
 8
 6
 55
 9
 55
 55
Level 0:
 Level 1:
  5
  7
  55
  55
  8
  6
  55
  9
  55
  55
 Level 1:
  5
  7
  55
  55
  8
  6
  55
  9
  55
  55
 Level 1:
  5
  7
  55
  55
  8
  6
  55
  9
  55
  55
Level 0:
 Level 1:
  0
 Level 1:
  1
  1
 Level 1:
  2
 Level 1:
  3
 Level 1:
  4
 Level 1:
  5
 Level 1:
  6
 Level 1:
  7
 Level 1:
  8
 Level 1:
  9
 Level 1:
  1
  0
 Level 1:
  1
  1
 Level 1:
  1
  2
 Level 1:
  1
  3
 Level 1:
  1
  4
 Level 1:
  1
  5
 Level 1:
  1
  6
 Level 1:
  1
  7
 Level 1:
  1
  8
 Level 1:
  1
  9
 Level 1:
  2
  0
Level 0:
 Level 1:
  Level 2:
   0
  Level 2:
   1
   1
  Level 2:
   2
  Level 2:
   3
  Level 2:
   4
  Level 2:
   5
  Level 2:
   6
  Level 2:
   7
  Level 2:
   8
  Level 2:
   9
  Level 2:
   1
   0
  Level 2:
   1
   1
  Level 2:
   1
   2
  Level 2:
   1
   3
  Level 2:
   1
   4
  Level 2:
   1
   5
  Level 2:
   1
   6
  Level 2:
   1
   7
  Level 2:
   1
   8
  Level 2:
   1
   9
  Level 2:
   2
   0
 Level 1:
  Level 2:
   0
  Level 2:
   1
   1
  Level 2:
   2
  Level 2:
   3
  Level 2:
   4
  Level 2:
   5
  Level 2:
   6
  Level 2:
   7
  Level 2:
   8
  Level 2:
   9
  Level 2:
   1
   0
  Level 2:
   1
   1
  Level 2:
   1
   2
  Level 2:
   1
   3
  Level 2:
   1
   4
  Level 2:
   1
   5
  Level 2:
   1
   6
  Level 2:
   1
   7
  Level 2:
   1
   8
  Level 2:
   1
   9
  Level 2:
   2
   0
 Level 1:
  Level 2:
   0
  Level 2:
   1
   1
  Level 2:
   2
  Level 2:
   3
  Level 2:
   4
  Level 2:
   5
  Level 2:
   6
  Level 2:
   7
  Level 2:
   8
  Level 2:
   9
  Level 2:
   1
   0
  Level 2:
   1
   1
  Level 2:
   1
   2
  Level 2:
   1
   3
  Level 2:
   1
   4
  Level 2:
   1
   5
  Level 2:
   1
   6
  Level 2:
   1
   7
  Level 2:
   1
   8
  Level 2:
   1
   9
  Level 2:
   2
   0
Level 0:
 1
 0
 3
 0
 5
 0
Level 0:
 Level 1:
  1
  0
  3
  0
  5
  0
 Level 1:
  1
  0
  3
  0
  5
  0
 Level 1:
  1
  0
  3
  0
  5
  0
Level 0:
 1
 0
 3
 0
 5
 0
Level 0:
 Level 1:
  1
  0
  3
  0
  5
  0
 Level 1:
  1
  0
  3
  0
  5
  0
 Level 1:
  1
  0
  3
  0
  5
  0
 Level 1:
  1
  0
  3
  0
  5
  0

Full Testing Code

The full testing code:

//  A recursive_replace_copy_if Template Function Implementation in C++

#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_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_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

//  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
    {
        return (input == target) ? 1 : 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_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_print implementation
template<typename T>
constexpr void recursive_print(const T& input, const std::size_t level = 0)
{
    std::cout << std::string(level, ' ') << input << '\n';
}

template<std::ranges::input_range Range>
constexpr void recursive_print(const Range& input, const std::size_t level = 0)
{
    std::cout << std::string(level, ' ') << "Level " << level << ":" << "\n";
    std::ranges::for_each(input, [level](auto&& element) {
        recursive_print(element, level + 1);
    });
}

//  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
//  recursive_invoke_result_t implementation
template<std::size_t, typename, typename>
struct recursive_invoke_result { };

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

template<std::size_t unwrap_level, std::copy_constructible F, template<typename...> typename Container, typename... Ts>
requires (std::ranges::input_range<Container<Ts...>> &&
        requires { typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type; })
struct recursive_invoke_result<unwrap_level, F, Container<Ts...>>
{
    using type = Container<typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type>;
};

template<std::size_t unwrap_level, std::copy_constructible F, typename T>
using recursive_invoke_result_t = typename recursive_invoke_result<unwrap_level, F, T>::type;

template <std::ranges::range Range>
constexpr auto get_output_iterator(Range& output)
{
    return std::inserter(output, std::ranges::end(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>
    std::vector<int> test_vector{ 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
    recursive_print(recursive_replace_copy_if(test_vector, std::bind(std::less<int>(), std::placeholders::_1, 5), 55));

    //  std::vector<std::vector<int>>
    std::vector<decltype(test_vector)> test_vector2 = {
        test_vector, test_vector, test_vector
    };
    recursive_print(recursive_replace_copy_if(test_vector2, std::bind(std::less<int>(), std::placeholders::_1, 5), 55));
    
    //  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" };
    recursive_print(
        recursive_replace_copy_if(
            test_string_vector, [](std::string x) { return (x == "1"); }, "11"
        )
    );

    //  std::vector<std::vector<std::string>>
    std::vector<decltype(test_string_vector)> test_string_vector2{ test_string_vector , test_string_vector , test_string_vector };
    recursive_print(
        recursive_replace_copy_if(
            test_string_vector2, [](std::string x) { return (x == "1"); }, "11"
        )
    );

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

    recursive_print(recursive_replace_copy_if(test_deque, [](int x) { return (x % 2) == 0; }, 0));
    
    //  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);

    recursive_print(recursive_replace_copy_if(test_deque2, [](int x) { return (x % 2) == 0; }, 0));

    //  std::list<int>
    std::list<int> test_list = { 1, 2, 3, 4, 5, 6 };

    recursive_print(recursive_replace_copy_if(test_list, [](int x) { return (x % 2) == 0; }, 0));


    //  std::list<std::list<int>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };

    recursive_print(recursive_replace_copy_if(test_list2, [](int x) { return (x % 2) == 0; }, 0));
    return 0;
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_copy_if Template Function Implementation in C++

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

    The implementation of recursive_replace_copy_if template function is the main idea in this question.

  • Why a new review is being asked for?

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think it looks good. \$\endgroup\$
    – JDługosz
    Commented Nov 4, 2021 at 14:53

1 Answer 1

Reset to default
3
\$\begingroup\$

Try to use the same interface as std::ranges::replace_copy_if()

Have a good look at how parameters are passed to std::ranges::replace_copy_if(), in particular:

  • The range is passed as a forwarding reference.
  • The range is constrained to be std::ranges::input_range (you didn't in the first overload).
  • The predicate is passed by value. However, doing that in a recursive function is going to give unexpected results. Better would be to pass it as a non-const reference, as then anything captured by value in the predicate will work as expected from the caller's point of view.

Issues constraining the predicate in the recursive case

You are restraining the recursive case to be when the predicate does not apply to the current recursive level's value type. That works in some cases, but while you are writing generic code, consider that the caller might also be very generic. Maybe the caller doesn't even know what types it is acting on, and passes a generic lambda as the predicate:

SomeType recursive_range = …;
auto clamp_negative_values = recursive_replace_copy_if(
    recursive_range,
    [](const auto& value){ return value < 0; },
    0
);

But because the predicate's parameter is auto, it will already match in the outermost recursion level. It would be better to have this always applied to the innermost level, and/or have a way to pass the desired recursion level to recursive_replace_copy_if().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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