std::forward_list::sort

#include <forward_list>

void sort();

template <class Compare>
void sort(Compare comp);

Sắp xếp các phần tử trong forward_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 forward_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 forward_list hiện tại, không tạo ra một forward_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): Phiên bản hiện tại của sort() trong thư viện chuẩn là stable sort. 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 xóa phần tử có thể làm thay đổi (invalidate) các iterator đang trỏ đến forward_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. Độ 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 forward_list. std::forward_list sử dụng thuật toán merge sort để sắp xếp.

Ví dụ

#include <iostream>
#include <forward_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::forward_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 forward_list đã được sắp xếp thành một forward_list duy nhất
reverse	Đảo ngược thứ tự các phần tử trong forward_list
unique	Xóa các phần tử trùng lặp liên tiếp khỏi forward_list