Chương trình C++ triển khai Set_Intersection trong STL

Giao (Intersection) của hai tập hợp là tập các phần tử xuất hiện trong cả hai tập. STL cung cấp std::set_intersection yêu cầu hai dãy đầu vào đã sắp xếp.

Thuật toán

1. Sắp xếp hai mảng/dãy đầu vào.
2. Cấp phát vector kết quả.
3. Gọi set_intersection.
4. Resize vector kết quả.

Ví dụ mã

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int set1[] = {5, 6, 7, 8, 9, 10};
    int set2[] = {1, 2, 3, 4, 6, 7};
    vector<int> v(12);
    vector<int>::iterator st;

    sort(set1, set1 + 6);
    sort(set2, set2 + 6);

    st = set_intersection(set1, set1 + 6, set2, set2 + 6, v.begin());
    v.resize(st - v.begin());

    cout << "Giao hai tập có " << v.size() << " phần tử: ";
    for (st = v.begin(); st != v.end(); ++st)
        cout << *st << " ";
    cout << endl;

    return 0;
}

Kết quả

Giao hai tập có 2 phần tử: 6 7