1
\$\begingroup\$

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:

\$\endgroup\$

    1 Answer 1

    Reset to default
    1
    \$\begingroup\$

    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.

    \$\endgroup\$

      Start asking to get answers

      Find the answer to your question by asking.

      Ask question

      Explore related questions

      See similar questions with these tags.