c++ - 如何从任何容器中取出？

Question

我想从容器中取出某些元素。问题是，我不知道它是什么样的容器。众所周知，大多数 STL 算法都不关心容器:例如，find_if、copy_if 等都或多或少地适用于任何容器类型。

但是删除呢？对于 vector-like 容器，有 remove-erase-idiom，但是不能应用于例如 set-like 容器。使用模板特化或重载，我可以专门针对特定容器，但在也应考虑其他容器(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

_编辑:

作为noted通过@pasbi，我们似乎已经有了std::experimental::erase_if ，正是这样做的!它将被合并到 C++20 中的 std::。

如果您想要自定义实现，请提前阅读。

---

您不必专门针对特定容器。相反，您可以使用类型特征和 SFINAE 来确定容器“类别”。

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

我会说是的。有 std::list 和 std::forward_list 有 .remove_if() 成员函数，应该比 erase-remove 快。

---

因此，我们有三种可能的实现方式:

我们使用 .remove_if() 如果可用(由 std::experimental::is_detected 确定)。
这样我们就可以处理 std::list 和 std::forward_list。

否则，我们会尽可能使用删除-删除。 (如果容器元素是可移动赋值的，这是可能的，可以使用 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++;
        }
    }
}

---

I'd prefer something without 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。