std::merge

#include <algorithm>

// So sánh bằng toán tử <
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (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 merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);

Hợp nhất (merge) hai phạm vi (range) đã được sắp xếp thành một phạm vi đầu ra duy nhất cũng đã được sắp xếp.

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 (tăng dần theo mặc định hoặc theo comp).
2. Phạm vi đầu ra phải có đủ không gian để chứa tất cả các phần tử từ cả hai phạm vi đầu vào. 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. merge() không thay đổi các phạm vi đầu vào.
4. merge() trả về iterator trỏ đến sau phần tử cuối cùng được ghi trong phạm vi đầu ra.
5. merge() 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).
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. merge() hoạt động bằng cách so sánh lần lượt các phần tử đầu tiên của hai phạm vi đầu vào, sau đó sao chép phần tử nhỏ hơn (theo tiêu chí so sánh) vào phạm vi đầu ra và di chuyển iterator tương ứng của phạm vi đó về phía trước. Quá trình này lặp lại cho đến khi tất cả các phần tử của cả hai phạm vi đầu vào được sao chép vào phạm vi đầu ra.
9. Độ phức tạp thời gian: O(n), trong đó n là tổng số phần tử trong hai phạm vi đầu vào.
10. merge() thường được sử dụng để:
    • Hợp nhất hai container đã sắp xếp thành một container mới cũng đã 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 đã sắp xếp.
    • Triển khai các thuật toán sắp xếp dựa trên việc hợp nhất (ví dụ: Merge Sort).

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> numbers1 = {1, 3, 5, 7, 9};
  std::vector<int> numbers2 = {2, 4, 6, 8, 10};
  std::vector<int> mergedNumbers;

  // Hợp nhất numbers1 và numbers2 vào mergedNumbers (tăng dần)
  std::merge(numbers1.begin(), numbers1.end(), numbers2.begin(), numbers2.end(),
             std::back_inserter(mergedNumbers));

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

  std::vector<int> numbers3 = {9, 7, 5, 3, 1};
  std::vector<int> numbers4 = {10, 8, 6, 4, 2};
  std::vector<int> mergedNumbers2;

  // Hợp nhất numbers3 và numbers4 vào mergedNumbers2 (giảm dần)
  std::merge(numbers3.begin(), numbers3.end(), numbers4.begin(), numbers4.end(),
             std::back_inserter(mergedNumbers2), compareDescending);

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

  return 0;
}

Các hàm liên quan

inplace_merge	Hợp nhất hai dãy con liên tiếp và đã được sắp xếp trong cùng một phạm vi thành một dãy được sắp xếp duy nhất tại chỗ
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
copy	Sao chép các phần tử từ một phạm vi nguồn sang một phạm vi đích khác