std::list::merge

#include <list>

// Phiên bản 1: Sử dụng toán tử < để so sánh
void merge(list& other);
void merge(list&& other); // (since C++11)

// Phiên bản 2: Sử dụng hàm so sánh comp
template <class Compare>
void merge(list& other, Compare comp);
template <class Compare>
void merge(list&& other, Compare comp); // (since C++11)

Hợp nhất (merge) hai std::list đã được sắp xếp thành một std::list duy nhất, vẫn giữ nguyên thứ tự đã sắp xếp.

Tham số

other

• Tham chiếu đến std::list khác cần hợp nhất. Sau khi merge() hoàn tất, other sẽ trở thành rỗng.

comp

• (phiên bản 2): Hàm so sánh (comparison function) hoặc functor xác định thứ tự sắp xếp của các phần tử. comp phải nhận hai đối số có kiểu là value_type của std::list (hoặc kiểu có thể chuyển đổi thành value_type) và trả về true nếu đối số đầu tiên được coi là nhỏ hơn đối số thứ hai theo thứ tự sắp xếp, false nếu ngược lại.

Giá trị trả về

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

Đặc điểm

1. Yêu cầu đã sắp xếp: Cả hai std::list (hiện tại và other) phải được sắp xếp trước khi gọi merge(). Nếu không, kết quả sẽ không xác định.
2. Chuyển phần tử, không sao chép: merge() chuyển các phần tử từ other sang std::list hiện tại, không tạo ra các bản sao. Do đó, thao tác này rất hiệu quả.
3. other trở thành rỗng: Sau khi merge() hoàn tất, std::list other sẽ trở thành rỗng.
4. Hai phiên bản: Phiên bản thứ hai của merge() cho phép bạn định nghĩa cách so sánh các phần tử thông qua hàm so sánh comp, hữu ích khi bạn muốn hợp nhất theo một thứ tự khác ngoài thứ tự tăng dần mặc định.
5. Có thể làm thay đổi iterator: Việc chuyển các phần tử có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong cả hai std::list.
6. noexcept: Phiên bản move merge được đánh dấu là noexcept (kể từ C++11), nghĩa là nó được đảm bảo không ném ra ngoại lệ nào. Các phiên bản copy thì có thể ném ngoại lệ nếu constructor, copy constructor hoặc destructor của phần tử được chèn ném ngoại lệ.
7. Trường hợp other là chính nó: Nếu other là chính std::list hiện tại, merge() sẽ không làm gì cả.
8. Độ phức tạp: Độ phức tạp của merge() là O(n + m), với n và m lần lượt là số phần tử trong hai std::list trước khi hợp nhất.

Ví dụ

#include <iostream>
#include <list>

// Hàm so sánh tùy chỉnh (giảm dần)
bool compareDescending(int a, int b) {
  return a > b;
}

int main() {
  std::list<int> list1 = {1, 3, 5, 7};
  std::list<int> list2 = {2, 4, 6, 8};

  list1.merge(list2); // Hợp nhất list2 vào list1 (sử dụng toán tử <)

  std::cout << "list1 after merge(list2):";
  for (int x : list1) std::cout << ' ' << x; // Output: list1 after merge(list2): 1 2 3 4 5 6 7 8
  std::cout << '\n';
  std::cout << "list2 after merge(list2):";
  for (int x : list2) std::cout << ' ' << x; // Output: list2 after merge(list2): (empty)
  std::cout << '\n';

  std::list<int> list3 = {9, 7, 5, 3};
  std::list<int> list4 = {8, 6, 4, 2};

  list3.sort(compareDescending);
  list4.sort(compareDescending);
  list3.merge(list4, compareDescending); // Hợp nhất list4 vào list3 (sử dụng hàm so sánh tùy chỉnh)

  std::cout << "list3 after merge(list4, compareDescending):";
  for (int x : list3) std::cout << ' ' << x; // Output: list3 after merge(list4, compareDescending): 9 8 7 6 5 4 3 2
  std::cout << '\n';

  return 0;
}

Các hàm liên quan

splice	Chuyển (transfer) các phần tử từ một std::list khác sang std::list hiện tại, tại một vị trí xác định
insert	Chèn một hoặc nhiều phần tử mới vào một vị trí cụ thể trong std::list
remove	Xóa tất cả các phần tử có giá trị bằng với một giá trị cho trước khỏi std::list
erase	Xóa một hoặc nhiều phần tử khỏi std::list tại một vị trí cụ thể hoặc trong một phạm vi
push_back	Thêm một phần tử mới vào cuối std::list