How to remove from any container?

  • A+
Category:Languages

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.

 


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: