Раздел «Алгоритмы».SetIntersection:

Пересечение двух множеств с использованием STL

Пример ввода/вывода:

$ ./set_intersection 
15 4 3 3 17 2 3 -1
3 17 1 15 1 14 22 -1
3 15 17

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#define all(v) (v).begin(), (v).end()
#define vi vector<int>

using namespace std;

void read(vi& v)
{
    while (1)
    {
        int i;
        cin >> i;
        if (i == -1) break;
        v.push_back(i);
    }
}

int main() {
    vi s1, s2, s3;

    read(s1);
    read(s2);
    sort(all(s1));
    sort(all(s2));
    s3.resize(s1.size());
    copy(s3.begin(), 
        set_intersection(all(s1), all(s2), s3.begin()), 
        ostream_iterator<int>(cout, " "));
    return 0;
}

Пояснения

Функция set_intersection получает 5 параметров — итераторы начал и концов задающие множества, которые необходимо пересечь, и итератор, указывающий на на место контейнера, начиная с которого требуется записать результат. Возвращяемым значением этой функции является итератор, указывающий на следующий элемент после последнего, полученного в результате пересечения множеств. Алгоритм set_intersection работает за линейное время и требует, чтобы интервалы были предворительно отсортированны.

ostream_iterator(cout, " ") создаёт итератор, для вывода переменных типа int в поток cout, разделителем в данном случае определён пробел.

Для вывода результата мы используем алгоритм copy, который копирует содержимое между двумя итераторами начиная с третьего итератора, в данном случае, данное копирование приводит к выводу содержимого в поток cout.

AlgorithmClasifyForm
Type: Код, Задача
Scope: Структуры данных, STL
Strategy:  
Language: C++
Complexity: Low