c++ - STL: set_union, includes, mismatch, find_if 但是没有includes_any吗？

Question

根据标题，您几乎肯定会想到使用 set_union 创建一个 list，然后检查它是否为空。但是，我比较的对象复制起来“很昂贵”。我查看了 includes，但只有当 所有 一个列表的项目在另一个列表中找到时才有效。我也看过 mismatch 但由于明显的原因拒绝了它。

我可以并且已经编写了我自己的函数，该函数假设两个列表都已排序，但我想知道 STL 中是否已经存在有效的函数。 (项目禁止使用Boost、TR1等第三方库，请勿询问。)

Answer 1

如果集合未排序，则可以使用 find_first_of 进行 O(N*M) 算法。

如果它们已排序(无论如何 set_intersection 都需要)，那么您可以迭代一个集合，在另一个集合中为每个元素调用 equal_range。如果每个返回的范围都是空的，则没有交集。性能为 O(N log M)。

但是，没有理由不拥有 O(N+M) 的性能，对吧？如果通过虚拟迭代器，set_intersection 不会复制任何内容。

struct found {};

template< class T > // satisfy language requirement
struct throwing_iterator : std::iterator< std::output_iterator_tag, T > {
    T &operator*() { throw found(); }
    throwing_iterator &operator++() { return *this; }
    throwing_iterator operator++(int) { return *this; }
};

template< class I, class J >
bool any_intersection( I first1, I last1, J first2, J last2 ) {
    try {
        throwing_iterator< typename std::iterator_traits<I>::value_type > ti;
        set_intersection( first1, last1, first2, last2, ti );
        return false;
    } catch ( found const& ) {
        return true;
    }
}

这提供了提前退出。您也可以避免异常，只让迭代器记住它递增了多少次，然后不对赋值进行操作。