c++ - STL:set_union，包含，不匹配，find_if，但是没有includes_any吗？

从标题中，您几乎可以肯定地认为使用set_union创建一个list，然后检查它是否为空。但是，我正在比较的对象“昂贵”地复制。我看过includes，但是只有在一个列表中的所有项目都在另一个列表中时，该方法才有效。我也查看了mismatch，但由于明显的原因而拒绝了它。

我可以并且已经编写了自己的函数，该函数假定两个列表都已排序，但是我想知道STL中是否已经存在有效的函数。 （请勿要求Project使用第三方库（包括Boost和TR1）。）

最佳答案

如果集合未排序，则可以将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;
    }
}

这样可以提早退出。您可以替代地避免该异常，而只是让迭代器记住它递增了多少次，并且不操作分配。

关于c++ - STL:set_union，包含，不匹配，find_if，但是没有includes_any吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3613004/