std::inplace_merge

#include <algorithm>

// So sánh bằng toán tử <
template <class BidirectionalIterator>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                    BidirectionalIterator last);

// Sử dụng hàm so sánh tùy chỉnh
template <class BidirectionalIterator, class Compare>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                    BidirectionalIterator last, Compare comp);

Hợp nhất (merge) hai dãy con liên tiếp và đã được sắp xếp trong cùng một phạm vi (range) thành một dãy được sắp xếp duy nhất tại chỗ (in-place). Điều này có nghĩa là, inplace_merge() sẽ sắp xếp lại các phần tử trong phạm vi ban đầu mà không cần sử dụng thêm không gian lưu trữ đáng kể.

Tham số

`first`

Bidirectional Iterator trỏ đến phần tử đầu tiên trong phạm vi. Dãy con thứ nhất là [first, middle).

`middle`

Bidirectional Iterator trỏ đến phần tử đầu tiên của dãy con thứ hai trong phạm vi. Dãy con thứ hai là [middle, last).

`last`

Bidirectional Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi.

`comp`

Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (hai phần tử trong phạm vi) 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ề

Không có giá trị trả về

Đặc điểm

Hai dãy con [first, middle) và [middle, last) phải nằm liền kề nhau trong cùng một phạm vi.
Cả hai dãy con phải được sắp xếp theo cùng một tiêu chí so sánh trước khi gọi inplace_merge().
inplace_merge() thay đổi trực tiếp thứ tự các phần tử trong phạm vi gốc, không tạo ra một phạm vi mới.
inplace_merge() yêu cầu Bidirectional Iterator, cho phép di chuyển theo cả hai hướng.
Thứ tự của các phần tử bằng nhau (theo tiêu chí so sánh) từ hai dãy con được giữ nguyên trong phạm vi kết quả (tính ổn định).
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.
inplace_merge() thường sử dụng các thuật toán tương tự như Merge Sort, nhưng được tối ưu để hoạt động tại chỗ. Độ phức tạp thời gian trung bình của inplace_merge() là O(n), trong đó n là tổng số phần tử trong hai dãy con. Trong trường hợp xấu nhất, nếu không đủ bộ nhớ, độ phức tạp có thể là O(n log n).
inplace_merge() thực hiện hợp nhất tại chỗ, nghĩa là nó ghi đè lên các phần tử ban đầu trong phạm vi. Tuy nhiên, nó có thể yêu cầu một lượng nhỏ không gian lưu trữ tạm thời (thường là log(n)) cho các hoạt động nội bộ.
inplace_merge() thường được sử dụng trong các trường hợp sau:
- Nó là một bước quan trọng trong thuật toán Merge Sort (sắp xếp trộn).
- Khi bạn có hai dãy con đã sắp xếp nằm liền kề nhau trong cùng một container và bạn muốn hợp nhất chúng lại thành một dãy duy nhất đã sắp xếp tại chỗ.

Phân biệt với merge()

merge() hợp nhất hai phạm vi riêng biệt thành một phạm vi mới.
inplace_merge() hợp nhất hai dãy con liên tiếp trong cùng một phạm vi tại chỗ.

Ví dụ

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

// 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> numbers = {1, 3, 5, 7, 2, 4, 6, 8};

  // Sắp xếp hai nửa của numbers
  std::sort(numbers.begin(), numbers.begin() + 4);
  std::sort(numbers.begin() + 4, numbers.end());

  // Hợp nhất hai nửa đã sắp xếp tại chỗ
  std::inplace_merge(numbers.begin(), numbers.begin() + 4, numbers.end());

  std::cout << "numbers after inplace_merge: ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  std::vector<int> numbers2 = {9, 7, 5, 3, 10, 8, 6, 4};

  // Sắp xếp hai nửa của numbers2 theo thứ tự giảm dần
  std::sort(numbers2.begin(), numbers2.begin() + 4, compareDescending);
  std::sort(numbers2.begin() + 4, numbers2.end(), compareDescending);

  // Hợp nhất hai nửa đã sắp xếp tại chỗ theo thứ tự giảm dần
  std::inplace_merge(numbers2.begin(), numbers2.begin() + 4, numbers2.end(), compareDescending);

  std::cout << "numbers2 after inplace_merge (descending): ";
  for (int x : numbers2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan


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
partition	Sắp xếp lại các phần tử trong một phạm vi
includes	Kiểm tra xem một phạm vi đã được sắp xếp có chứa tất cả các phần tử của một phạm vi đã được sắp xếp khác hay không

Tham số​

first​

middle​

last​

comp​

Giá trị trả về​

Đặc điểm​

Ví dụ​

Các hàm liên quan​