How to remove from any container?

Question

I'd like to remove certain items from a container. The problem is, I don't know what kind of container it is. Most STL-algorithms famously don't care about container: e.g., find_if, copy_if, etc. all work more or less with any container type.

But what about deleting? For vector-like containers, there is the remove-erase-idiom, which, however, cannot be applied to, e.g., set-like containers. Using template specialization or overloading, I could specialize for particular containers but that does not scale when other containers (unordered_set, list, ...) should be considered, too.

My question is: How to implement a function which removes certain items from any container efficiently? Preferred signature:

template<typename Ts, typename Predicate>
void remove_if(Ts& ts, const Predicate& p);

Or, more concrete: How can I distinguish between set-like containers (fast insert/delete, no custom order) and vector-like containers (slow insert/delete, custom order)? Is there a (commonly used) container which does not fit in either category?

Edit: I just found std::experimental::erase_if, which has overloads for many (all?) containers. That is, I will accept a solution only if it doesn't use std::experimental.

Answer 1

_Edit:

As noted by @pasbi, it seems that we already have std::experimental::erase_if, which does exactly that! It will be merged into std:: in C++20.

If you want a custom implementation, read ahead.

---

You don't have to specialize for specific containers. Instead, you can use type traits and SFINAE to determine container 'category'.

Is there a (commonly used) container which does not fit in either category?

I'd say yes. There are std::list and std::forward_list which have .remove_if() member function, which should be faster than erase-remove.

---

Thus, we have three possible implementations:

We use .remove_if() if it's available (as determined by std::experimental::is_detected).
This way we handle std::list and std::forward_list.

Otherwise, we use erase-remove if possible. (Which is possible if container elements are move-assignable, which can be tested with std::is_move_assignable.)
This way we handle all remaining standard containers except for std::[unordered_]map and std::[unordered_]set. (This is what you call vector-like containers.)

Otherwise we resort to a simple erasing loop over the elements.
This way we handle std::[unordered_]map and std::[unordered_]set.

---

Example implementation:

#include <algorithm>
#include <iterator>
#include <experimental/type_traits>
#include <utility>

inline auto dummy_predicate = [](auto &&){return false;};

template <typename T> using detect_member_remove_if =
    decltype(std::declval<T&>().remove_if(dummy_predicate));

template <typename T, typename F> void remove_if(T &container, F &&func)
{
    using element_t = std::remove_reference_t<decltype(*std::begin(container))>;

    if constexpr (std::experimental::is_detected_v<detect_member_remove_if, T>)
    {
        container.remove_if(std::forward<F>(func));
    }
    else if constexpr (std::is_move_assignable_v<element_t>)
    {
        auto new_end = std::remove_if(std::begin(container), std::end(container),
                                      std::forward<F>(func));
        container.erase(new_end, std::end(container));
    }
    else
    {
        auto it = std::begin(container);
        while (it != std::end(container))
        {
            if (func(*it))
                it = container.erase(it);
            else
                it++;
        }
    }
}

---

I'd prefer something without experimental

Here's a custom replacement for std::experimental::is_detected_v:

namespace impl
{
    template <typename ...P> struct void_impl {using type = void;};
    template <typename ...P> using void_t = typename void_impl<P...>::type;

    template <typename Dummy, template <typename...> typename A, typename ...B>
    struct is_detected : std::false_type {};

    template <template <typename...> typename A, typename ...B>
    struct is_detected<void_t<A<B...>>, A, B...> : std::true_type {};
}

template <template <typename...> typename A, typename ...B>
inline constexpr bool is_detected_v = impl::is_detected<void, A, B...>::value;

Note that we don't use C++17 std::void_t because, as far as I know, it still doesn't SFINAE correctly in Clang.

Answer 2

std::erase and std::erase_if will be part of C++20. See P1209

Libc++ (trunk) implements this already (as of yesterday :-)), and it will be part of clang 8.0.