std::set_union

#include <algorithm>

// So sánh bằng toán tử <
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                          InputIterator2 first2, InputIterator2 last2,
                          OutputIterator result);

// Sử dụng hàm so sánh tùy chỉnh
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                          InputIterator2 first2, InputIterator2 last2,
                          OutputIterator result, Compare comp);

Tạo ra một phạm vi (range) mới chứa hợp (union) của hai phạm vi đã được sắp xếp đầu vào. Hợp của hai tập hợp là một tập hợp chứa tất cả các phần tử xuất hiện trong ít nhất một trong hai tập hợp ban đầu, các phần tử trùng nhau chỉ xuất hiện một lần trong kết quả, và được sắp xếp theo thứ tự.

Tham số

first1

• Input Iterator trỏ đến phần tử đầu tiên trong phạm vi đã sắp xếp thứ nhất.

last1

• Input Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi thứ nhất. Phạm vi thứ nhất là [first1, last1).

first2

• Input Iterator trỏ đến phần tử đầu tiên trong phạm vi đã sắp xếp thứ hai.

last2

• Input Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi thứ hai. Phạm vi thứ hai là [first2, last2).

result

• Output Iterator trỏ đến phần tử đầu tiên trong phạm vi đầu ra nơi kết quả hợp nhất sẽ được lưu trữ.

comp

• Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (mỗi đối số là một phần tử từ một trong hai phạm vi đầu vào) và trả về true nếu phần tử thứ nhất được coi là nhỏ hơn phần tử thứ hai theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

• Output Iterator trỏ đến phần tử ngay sau phần tử cuối cùng được ghi trong phạm vi đầu ra.

Đặc điểm

1. Cả hai phạm vi đầu vào [first1, last1) và [first2, last2) phải được sắp xếp theo cùng một tiêu chí so sánh.
2. Phạm vi đầu ra phải có đủ không gian để chứa tất cả các phần tử của hợp. Sử dụng std::back_inserter là một cách an toàn khi hợp nhất vào container có thể thay đổi kích thước như std::vector.
3. set_union() không thay đổi các phạm vi đầu vào.
4. set_union() trả về iterator trỏ đến sau phần tử cuối cùng được ghi trong phạm vi đầu ra.
5. set_union() yêu cầu Input Iterator cho các phạm vi đầu vào và Output Iterator cho phạm vi đầu ra.
6. Thứ tự của các phần tử bằng nhau (theo tiêu chí so sánh) từ hai phạm vi đầu vào được giữ nguyên trong phạm vi đầu ra (tính ổn định). Tuy nhiên, nếu có nhiều phần tử bằng nhau ở cả 2 dãy, chỉ 1 phần tử được đưa vào kết quả.
7. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
8. Cả hai phạm vi đầu vào phải được sắp xếp theo cùng một tiêu chí so sánh (tăng dần theo mặc định hoặc theo tiêu chí so sánh tùy chỉnh) trước khi gọi set_union(). Nếu các phạm vi không được sắp xếp, kết quả sẽ không chính xác.
9. set_union() thường được sử dụng để:
   • Tạo ra một tập hợp mới là hợp của hai tập hợp đã sắp xếp.
   • Kết hợp dữ liệu từ hai nguồn đã sắp xếp thành một nguồn duy nhất, loại bỏ các phần tử trùng lặp.
   • Triển khai các thuật toán và cấu trúc dữ liệu liên quan đến tập hợp.

Ví dụ

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

// Hàm so sánh để hợp nhất theo thứ tự giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

int main() {
  std::vector<int> set1 = {1, 3, 5, 7, 9};
  std::vector<int> set2 = {2, 4, 6, 8, 10};
  std::vector<int> unionSet;

  // Hợp nhất set1 và set2 vào unionSet (tăng dần)
  std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
                 std::back_inserter(unionSet));

  std::cout << "unionSet (ascending): ";
  for (int x : unionSet) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  std::vector<int> set3 = {9, 7, 5, 3, 1};
  std::vector<int> set4 = {10, 8, 6, 4, 2};
  std::vector<int> unionSet2;

  // Hợp nhất set3 và set4 vào unionSet2 (giảm dần)
  std::set_union(set3.begin(), set3.end(), set4.begin(), set4.end(),
                 std::back_inserter(unionSet2), compareDescending);

  std::cout << "unionSet2 (descending): ";
  for (int x : unionSet2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;
  
  std::vector<int> set5 = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5};
  std::vector<int> set6 = {2, 4, 6};
  std::vector<int> unionSet3;
    
  std::set_union(set5.begin(), set5.end(), set6.begin(), set6.end(),
                 std::back_inserter(unionSet3));
  std::cout << "unionSet3 (duplicates removed): ";
  for (int x : unionSet3) {
      std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan

set_intersection	Tạo ra một phạm vi mới chứa giao của hai phạm vi đã được sắp xếp đầu vào
set_difference	Tạo ra một phạm vi mới chứa hiệu của hai phạm vi đã được sắp xếp đầu vào
set_symmetric_difference	Tạo ra một phạm vi mới chứa hiệu đối xứng của hai phạm vi đã được sắp xếp đầu vào
merge	Hợp nhất hai phạm vi đã được sắp xếp thành một phạm vi đầu ra duy nhất cũng đã được sắp xếp