如何从任何容器中删除？

Question

我想从容器中删除某些物品.问题是,我不知道它是什么样的容器.大多数STL的算法著名不在乎容器:如find_if,copy_if等所有的工作或多或少与任何容器类型.

但删除呢？对于vector类似容器,存在remove-erase-idiom,然而,其不能应用于例如set类似容器.使用模板特化或重载,我可以专门为特定的容器但没有规模,当其他容器(unordered_set,list,...)应该考虑了.

我的问题是: 如何实现一个有效地从任何容器中删除某些项目的功能？首选签名:

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

或者,更具体:我如何区分set类似容器(快速插入/删除,没有自定义顺序)和vector类似容器(慢插入/删除,自定义顺序)？是否有(常用的)容器不适合任何一种类别？

编辑:我刚刚发现std::experimental::erase_if,它有许多(所有？)容器的重载.也就是说,只有在不使用的情况下,我才接受解决方案std::experimental.

Answer 1

_编辑:

正如@pasbi 所指出的,似乎我们已经拥有了std::experimental::erase_if,这正是如此!它将被合并到std::C++ 20中.

如果您想要自定义实现,请提前阅读.

您不必专门针对特定容器.相反,您可以使用类型特征和SFINAE来确定容器"类别".

是否有(常用的)容器不适合任何一种类别？

我会说是的.有std::list和std::forward_list哪些有.remove_if()成员函数,它应该比擦除 - 删除更快.

因此,我们有三种可能的实现:

我们使用.remove_if()它是否可用(由确定std::experimental::is_detected).
这样我们处理std::list和std::forward_list.

否则,我们会尽可能使用erase-remove.(如果容器元素是可移动分配的,可以使用它进行测试std::is_move_assignable.)
这样我们处理除了std::[unordered_]map和之外的所有剩余标准容器std::[unordered_]set.(这就是你所说vector的容器.)

否则,我们会在元素上使用简单的擦除循环.
这样我们处理std::[unordered_]map和std::[unordered_]set.

示例实现:

#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++;
        }
    }
}

我更喜欢没有的东西 experimental

这是一个定制的替代品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;

请注意,我们不使用C++ 17 std::void_t,因为据我所知,在Clang中它仍然没有正确使用SFINAE.