std::set_intersection

#include <algorithm>

// So sánh bằng toán tử <
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection (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_intersection (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 giao (intersection) của hai phạm vi đã được sắp xếp đầu vào. Giao 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 cả hai tập hợp ban đầu, và các phần tử trong kết quả đượ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ả giao 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 các phần tử của giao. 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_intersection() không thay đổi các phạm vi đầu vào.
4. set_intersection() trả về iterator trỏ đến sau phần tử cuối cùng được ghi trong phạm vi đầu ra.
5. set_intersection() 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ử trong phạm vi đầu ra là ổn định (giữ nguyên thứ tự xuất hiện trong phạm vi đầu tiên).
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_intersection(). 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_intersection() thường được sử dụng để:
   • Tìm các phần tử chung giữa hai tập hợp đã sắp xếp.
   • Lọc dữ liệu dựa trên sự hiện diện của chúng trong một tập hợp khác đã sắp xế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 để tìm giao theo thứ tự giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

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

  // Tìm giao của set1 và set2 (tăng dần)
  std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                        std::back_inserter(intersection));

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

  std::vector<int> set3 = {9, 7, 5, 3, 1};
  std::vector<int> set4 = {8, 6, 4, 2};
  std::vector<int> intersection2;
    
  // Tìm giao của set3 và set4 (giảm dần)
  std::set_intersection(set3.begin(), set3.end(), set4.begin(), set4.end(),
                        std::back_inserter(intersection2), compareDescending);

  std::cout << "Intersection (descending): ";
  for (int x : intersection2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan

set_union	Tạo ra một phạm vi mới chứa hợp 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