STL: set_union, includes, несоответствие, find_if, но нет ли include_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;
    }
}

Это обеспечивает ранний выход.Вы можете поочередно избежать исключения и просто сделать, чтобы итератор запомнил, сколько раз оно было увеличено, и не определял назначение.

Answer 2

Является ли find_first_of() тем, что вы ищете?