How to remove from any container?

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?