recursive_remove and recursive_remove_if Template Function with Unwrap Level Implementation in C++

Question

This is a follow-up question for recursive_find and recursive_find_if_not Template Functions Implementation in C++ and A recursive_copy_if Template Function Implementation with Unwrap Level Implementation in C++. I am trying to implement recursive_remove and recursive_remove_if template function in this post. recursive_remove function takes a container and a value and it removes the elements which is equal to the given value. Similarly, recursive_remove_if function takes a container and a lambda expression (unary_predicate) and it removes the elements which unary_predicate(element) is true.

The experimental implementation

• recursive_remove_if template function implementation

  //  recursive_remove_if function implementation with unwrap level
  template <std::size_t unwrap_level, std::ranges::input_range Range, class UnaryPredicate>
  requires(recursive_invocable<unwrap_level, UnaryPredicate, Range> &&
           is_inserterable<Range> &&
           unwrap_level > 0)
  constexpr auto recursive_remove_if(const Range& input, const UnaryPredicate& unary_predicate)
  {
      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)),
              [&unary_predicate](auto&& element) { return recursive_remove_if<unwrap_level - 1>(element, unary_predicate); }
              );
          return output;
      }
      else
      {
          Range output{};
          std::ranges::copy_if(std::ranges::cbegin(input), std::ranges::cend(input),
              std::inserter(output, std::ranges::end(output)),
              [&](auto&& element) { return !unary_predicate(element); } );
          return output;
      }
  }
  

• recursive_remove template function implementation

  //  recursive_remove function implementation with unwrap level
  template <std::size_t unwrap_level, std::ranges::input_range Range, class T>
  requires(is_inserterable<Range> &&
           unwrap_level > 0)
  constexpr auto recursive_remove(const Range& input, const T& value)
  {
      return recursive_remove_if<unwrap_level>(input, [&](auto&& element) { return element == value; });
  }
  

Full Testing Code

The full testing code:

//  recursive_remove and recursive_remove_if Template Function with Unwrap Level 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 <ranges>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#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 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 template 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};
}

//  is_recursive_invocable template function implementation
template<std::size_t unwrap_level, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>())
static constexpr bool is_recursive_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, T...>;
    } else {
        return is_recursive_invocable<
                    unwrap_level - 1,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_invocable concept
template<std::size_t unwrap_level, class F, class... T>
concept recursive_invocable =
        is_recursive_invocable<unwrap_level, F, T...>();

//  is_recursive_project_invocable template function implementation
template<std::size_t unwrap_level, class Proj, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>() &&
        recursive_invocable<unwrap_level, Proj, T...>)
static constexpr bool is_recursive_project_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, std::invoke_result_t<Proj, T...>>;
    } else {
        return is_recursive_project_invocable<
                    unwrap_level - 1,
                    Proj,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_project_invocable concept
template<std::size_t unwrap_level, class Proj, class F, class... T>
concept recursive_project_invocable =
        is_recursive_project_invocable<unwrap_level, Proj, F, T...>();

//  recursive_remove_if function implementation with unwrap level
template <std::size_t unwrap_level, std::ranges::input_range Range, class UnaryPredicate>
requires(recursive_invocable<unwrap_level, UnaryPredicate, Range> &&
         is_inserterable<Range> &&
         unwrap_level > 0)
constexpr auto recursive_remove_if(const Range& input, const UnaryPredicate& unary_predicate)
{
    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)),
            [&unary_predicate](auto&& element) { return recursive_remove_if<unwrap_level - 1>(element, unary_predicate); }
            );
        return output;
    }
    else
    {
        Range output{};
        std::ranges::copy_if(std::ranges::cbegin(input), std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            [&](auto&& element) { return !unary_predicate(element); } );
        return output;
    }
}

//  recursive_remove function implementation with unwrap level
template <std::size_t unwrap_level, std::ranges::input_range Range, class T>
requires(is_inserterable<Range> &&
         unwrap_level > 0)
constexpr auto recursive_remove(const Range& input, const T& value)
{
    return recursive_remove_if<unwrap_level>(input, [&](auto&& element) { return element == value; });
}

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

//  Copy from https://stackoverflow.com/a/37264642/6667035
#ifndef NDEBUG
#   define M_Assert(Expr, Msg) \
    __M_Assert(#Expr, Expr, __FILE__, __LINE__, Msg)
#else
#   define M_Assert(Expr, Msg) ;
#endif

void __M_Assert(const char* expr_str, bool expr, const char* file, int line, const char* msg)
{
    if (!expr)
    {
        std::cerr << "Assert failed:\t" << msg << "\n"
            << "Expected:\t" << expr_str << "\n"
            << "Source:\t\t" << file << ", line " << line << "\n";
        abort();
    }
}

void recursive_remove_if_tests()
{
    //  std::vector<int> test case
    std::vector<int> test_vector_1 = {
        1, 2, 3, 4, 5, 6
    };
    std::vector<int> expected_result_1 = {
        1, 3, 5
    };
    M_Assert(
        recursive_remove_if<1>(test_vector_1, [](auto&& x) { return (x % 2) == 0; }) ==
        expected_result_1,
        "std::vector<int> test case failed");

    //  std::vector<std::vector<int>> test case
    std::vector<decltype(test_vector_1)> test_vector_2 = {
        test_vector_1, test_vector_1, test_vector_1
    };
    std::vector<std::vector<int>> expected_result_2 = {
        expected_result_1, expected_result_1, expected_result_1
    };
    M_Assert(
        recursive_remove_if<2>(test_vector_2, [](auto&& x) { return (x % 2) == 0; }) ==
        expected_result_2,
        "std::vector<std::vector<int>> test case failed");
    
    //  std::vector<std::string> test case
    std::vector<std::string> test_vector_3 = {
        "1", "2", "3", "4", "5", "6"
    };
    std::vector<std::string> expected_result_3 = {
        "2", "3", "4", "5", "6"
    };
    M_Assert(
        recursive_remove_if<1>(test_vector_3, [](auto&& x) { return (x == "1"); }) ==
        expected_result_3,
        "std::vector<std::string> test case failed");
    
    //  std::vector<std::vector<std::string>> test case
    std::vector<std::vector<std::string>> test_vector_4 = {
        test_vector_3, test_vector_3, test_vector_3
    };
    std::vector<std::vector<std::string>> expected_result_4 = {
        expected_result_3, expected_result_3, expected_result_3
    };
    M_Assert(
        recursive_remove_if<2>(test_vector_4, [](auto&& x) { return (x == "1"); }) ==
        expected_result_4,
        "std::vector<std::vector<std::string>> test case failed");

    //  std::deque<int> test case
    std::deque<int> test_deque_1;
    test_deque_1.push_back(1);
    test_deque_1.push_back(2);
    test_deque_1.push_back(3);
    test_deque_1.push_back(4);
    test_deque_1.push_back(5);
    test_deque_1.push_back(6);
    std::deque<int> expected_result_5;
    expected_result_5.push_back(2);
    expected_result_5.push_back(3);
    expected_result_5.push_back(4);
    expected_result_5.push_back(5);
    expected_result_5.push_back(6);
    M_Assert(
        recursive_remove_if<1>(test_deque_1, [](auto&& x) { return (x == 1); }) ==
        expected_result_5,
        "std::deque<int> test case failed"
    );

    //  std::deque<std::deque<int>> test case
    std::deque<decltype(test_deque_1)> test_deque_2;
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    std::deque<decltype(expected_result_5)> expected_result_6;
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    M_Assert(
        recursive_remove_if<2>(test_deque_2, [](auto&& x) { return (x == 1); }) ==
        expected_result_6,
        "std::deque<std::deque<int>> test case failed"
    );

    //  std::list<int> test case
    std::list<int> test_list_1 = { 1, 2, 3, 4, 5, 6 };
    std::list<int> expected_result_7 = {1, 3, 5};
    M_Assert(
        recursive_remove_if<1>(test_list_1, [](int x) { return (x % 2) == 0; }) ==
        expected_result_7,
        "std::list<int> test case failed"
    );

    //  std::list<std::list<int>> test case
    std::list<std::list<int>> test_list_2 = { test_list_1, test_list_1, test_list_1, test_list_1 };
    std::list<std::list<int>> expected_result_8 = {
        expected_result_7, expected_result_7, expected_result_7, expected_result_7
    };
    M_Assert(
            recursive_remove_if<2>(test_list_2, [](int x) { return (x % 2) == 0; }) ==
            expected_result_8,
            "std::list<std::list<int>> test case failed"
        );
    
    std::cout << "All tests passed!\n";
}

void recursive_remove_tests()
{
    //  std::vector<int> test case
    std::vector<int> test_vector_1 = {
        1, 2, 3, 4, 5, 6
    };
    std::vector<int> expected_result_1 = {
        2, 3, 4, 5, 6
    };
    M_Assert(
        recursive_remove<1>(test_vector_1, 1) ==
        expected_result_1,
        "std::vector<int> test case failed");

    //  std::vector<std::vector<int>> test case
    std::vector<decltype(test_vector_1)> test_vector_2 = {
        test_vector_1, test_vector_1, test_vector_1
    };
    std::vector<std::vector<int>> expected_result_2 = {
        expected_result_1, expected_result_1, expected_result_1
    };
    M_Assert(
        recursive_remove<2>(test_vector_2, 1) ==
        expected_result_2,
        "std::vector<std::vector<int>> test case failed");
    
    //  std::vector<std::string> test case
    std::vector<std::string> test_vector_3 = {
        "1", "2", "3", "4", "5", "6"
    };
    std::vector<std::string> expected_result_3 = {
        "2", "3", "4", "5", "6"
    };
    M_Assert(
        recursive_remove<1>(test_vector_3, "1") ==
        expected_result_3,
        "std::vector<std::string> test case failed");

    //  std::vector<std::vector<std::string>> test case
    std::vector<std::vector<std::string>> test_vector_4 = {
        test_vector_3, test_vector_3, test_vector_3
    };
    std::vector<std::vector<std::string>> expected_result_4 = {
        expected_result_3, expected_result_3, expected_result_3
    };
    M_Assert(
        recursive_remove<2>(test_vector_4, "1") ==
        expected_result_4,
        "std::vector<std::vector<std::string>> test case failed");

    //  std::deque<int> test case
    std::deque<int> test_deque_1;
    test_deque_1.push_back(1);
    test_deque_1.push_back(2);
    test_deque_1.push_back(3);
    test_deque_1.push_back(4);
    test_deque_1.push_back(5);
    test_deque_1.push_back(6);
    std::deque<int> expected_result_5;
    expected_result_5.push_back(2);
    expected_result_5.push_back(3);
    expected_result_5.push_back(4);
    expected_result_5.push_back(5);
    expected_result_5.push_back(6);
    M_Assert(
        recursive_remove<1>(test_deque_1, 1) ==
        expected_result_5,
        "std::deque<int> test case failed"
    );

    //  std::deque<std::deque<int>> test case
    std::deque<decltype(test_deque_1)> test_deque_2;
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    std::deque<decltype(expected_result_5)> expected_result_6;
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    M_Assert(
        recursive_remove<2>(test_deque_2, 1) ==
        expected_result_6,
        "std::deque<std::deque<int>> test case failed"
    );

    //  std::list<int> test case
    std::list<int> test_list_1 = { 1, 2, 3, 4, 5, 6 };
    std::list<int> expected_result_7 = {2, 3, 4, 5, 6};
    M_Assert(
        recursive_remove<1>(test_list_1, 1) ==
        expected_result_7,
        "std::list<int> test case failed"
    );

    //  std::list<std::list<int>> test case
    std::list<std::list<int>> test_list_2 = { test_list_1, test_list_1, test_list_1, test_list_1 };
    std::list<std::list<int>> expected_result_8 = {
        expected_result_7, expected_result_7, expected_result_7, expected_result_7
    };
    M_Assert(
            recursive_remove<2>(test_list_2, 1) ==
            expected_result_8,
            "std::list<std::list<int>> test case failed"
        );

    std::cout << "All tests passed!\n";
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_remove_if_tests();
    recursive_remove_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:

All tests passed!
All tests passed!
Computation finished at Sun Mar 31 12:29:00 2024
elapsed time: 7.8283e-05

Godbolt link is here.

All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

  recursive_find and recursive_find_if_not Template Functions Implementation in C++ and

  A recursive_copy_if Template Function Implementation with Unwrap Level Implementation in C++

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

  I am trying to implement recursive_remove and recursive_remove_if template function in this post.

• Why a new review is being asked for?

  Please review the implementation of recursive_remove_if and recursive_remove template functions and those tests. About the naming, there are several options came up in my mind: one are recursive_remove_if and recursive_remove like the usage in this post, another are recursive_erase_if and recursive_erase, or something like recursive_copy_if_not because a new range is constructed. I want to know which one is better for representing its function.

Answer 1

Naming

You named it recursive_remove_if(), but std::remove_if() does something very different from your code: it doesn't actually erase or copy anything, it just moves undesired elements to the back of the range, and returns an iterator to the end of the range of the desired elements.

There is however an STL algorithm that more closely matches what you are doing, and that is std::remove_copy_if(). To avoid any confusion, I recommend you rename your function to recursive_remove_copy_if(). And similarly for recursive_remove(), which should become recursive_remove_copy().

Notice how you can also use std::remove_copy_if() in your own code instead of std::copy_if(), as that avoids having to negate the predicate.

About the implementation of recursive_remove()

While it seems convenient to let recursive_remove() call recursive_remove_if(), and it also reduces code duplication, there is a potential downside. Consider that std::remove_copy() might implement optimizations for some types T. For example, it could use SSE instructions to compare multiple elements at once. By calling recursive_remove_if() with a custom predicate, you might bypass such optimizations.

In this case, I think it is highly unlikely that this is an issue. All the code is templated, so the compiler will be able to inline the lambda and see you are just doing equality comparisons, and it could still vectorize the code. So I would leave it as is (except for changing the names of your functions, as mentioned above). It is something to keep in mind though.