std::list::sort

#include <list>

// Phiên bản 1: Sắp xếp theo thứ tự tăng dần (sử dụng toán tử <)
void sort();

// Phiên bản 2: Sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class Compare>
void sort(Compare comp);

Sắp xếp các phần tử trong std::list theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh.

Tham số

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. Sắp xếp tại chỗ: sort() sắp xếp các phần tử ngay trong std::list hiện tại, không tạo ra một std::list mới.
2. Mặc định là tăng dần: Nếu không có hàm so sánh comp được cung cấp, sort() sẽ sắp xếp các phần tử theo thứ tự tăng dần, sử dụng toán tử <.
3. Hỗ trợ hàm so sánh tùy chỉnh: Phiên bản thứ hai của sort() 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 sắp xếp theo một thứ tự khác ngoài thứ tự tăng dần mặc định.
4. Tính ổn định (Stability): sort() của std::list đảm bảo tính ổn định (stable). Có nghĩa là các phần tử bằng nhau sẽ giữ nguyên thứ tự ban đầu của chúng sau khi sắp xếp.
5. Có thể làm thay đổi iterator: Thao tác sắp xếp có thể làm thay đổi (invalidate) các iterator đang trỏ đến std::list.
6. Yêu cầu đối với kiểu phần tử:
   • Phiên bản 1: Kiểu phần tử phải hỗ trợ toán tử <.
   • Phiên bản 2: Kiểu phần tử phải hỗ trợ cách so sánh được định nghĩa bởi hàm so sánh comp.
7. noexcept: Nếu toán tử < hoặc hàm so sánh comp không ném ngoại lệ thì sort() cũng được đảm bảo là noexcept.
8. Độ phức tạp: Độ phức tạp của sort() là O(n log n), với n là số phần tử trong std::list. std::list sử dụng thuật toán merge sort để sắp xếp.

Ví dụ

#include <iostream>
#include <list>
#include <functional> // std::greater

// 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> mylist = {5, 2, 8, 1, 9, 4};

  mylist.sort(); // Sắp xếp tăng dần (sử dụng toán tử <)

  std::cout << "mylist after sort():";
  for (int x : mylist) std::cout << ' ' << x; // Output: mylist after sort(): 1 2 4 5 8 9
  std::cout << '\n';

  // Sắp xếp giảm dần (sử dụng functor std::greater)
  mylist.sort(std::greater<int>());
  std::cout << "mylist after sort(std::greater<int>()):";
  for (int x : mylist) std::cout << ' ' << x; // Output: mylist after sort(std::greater<int>()): 9 8 5 4 2 1
  std::cout << '\n';

  // Sắp xếp giảm dần (sử dụng hàm so sánh tùy chỉnh)
  mylist.sort(compareDescending);
  std::cout << "mylist after sort(compareDescending):";
  for (int x : mylist) std::cout << ' ' << x; // Output: mylist after sort(compareDescending): 9 8 5 4 2 1
  std::cout << '\n';

  // Sắp xếp giảm dần (sử dụng lambda function)
  mylist.sort([](int a, int b){return a > b;});
  std::cout << "mylist after sort([](int a, int b){return a > b;}):";
  for (int x : mylist) std::cout << ' ' << x; // Output: mylist after sort([](int a, int b){return a > b;}): 9 8 5 4 2 1
  std::cout << '\n';

  return 0;
}

Các hàm liên quan

merge	Hợp nhất (merge) hai std::list đã được sắp xếp thành một std::list duy nhất
reverse	Đảo ngược thứ tự các phần tử trong std::list
unique	Xóa các phần tử trùng lặp liên tiếp khỏi std::list