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

Hợp (Union) của hai tập hợp là tập chứa tất cả phần tử xuất hiện trong ít nhất một trong hai tập. Phần tử trùng lặp chỉ giữ một lần. C++ STL cung cấp std::set_union trong thư viện <algorithm>.

Thuật toán

1. Khai báo hai mảng đã sắp xếp (hoặc sắp xếp trước khi gọi).
2. Cấp phát vector kết quả đủ lớn.
3. Gọi set_union(first1, last1, first2, last2, result.begin()).
4. Resize vector kết quả theo iterator trả về.

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); // đủ lớn
    vector<int>::iterator st;

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

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

    cout << "Hợp 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ả

Hợp hai tập có 10 phần tử: 1 2 3 4 5 6 7 8 9 10