Phần tử có trong mảng 1 nhưng không trong mảng 2 dùng STL C++

Cho 2 mảng, tìm các phần tử chỉ có trong mảng 1 không có trong mảng 2, dùng STL.

Thuật toán: set_difference

set_difference tính hiệu 2 tập đã sắp xếp: phần tử có trong tập 1 không có trong tập 2. Yêu cầu cả 2 mảng đã sắp xếp.

Cú pháp

OutputIterator set_difference(InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              OutputIterator result);

Chương trình mẫu

#include <bits/stdc++.h>
using namespace std;

void find(int array1[], int array2[], int x, int y) {
    vector<int> v(x + y);
    vector<int>::iterator it;
    
    sort(array1, array1 + x);
    sort(array2, array2 + y);
    
    it = set_difference(array1, array1 + x, array2, array2 + y, v.begin());
    v.resize(it - v.begin());
    
    cout << "Elements in array1 but not in array2: ";
    for (it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main() {
    int array1[] = {1, 2, 3, 4, 5, 7};
    int array2[] = {2, 3, 4, 5, 6, 8};
    int x = sizeof(array1)/sizeof(array1[0]);
    int y = sizeof(array2)/sizeof(array2[0]);
    find(array1, array2, x, y);
    return 0;
}

Kết quả

Elements in array1 but not in array2: 1 7

Lưu ý: Phải sắp xếp trước khi dùng set_difference. Kết quả giữ thứ tự của mảng 1 (sau khi sort). Độ phức tạp O(n log n + m log m) do sort.