std::is_sorted_until

#include <algorithm>

// Kiểm tra sắp xếp tăng dần theo mặc định sử dụng toán tử <
template <class ForwardIterator>
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

// Kiểm tra sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class ForwardIterator, class Compare>
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last,
                                 Compare comp);

Tìm vị trí phần tử đầu tiên trong một phạm vi (range) mà từ vị trí đó trở đi, phạm vi không còn được sắp xếp theo thứ tự tăng dần (mặc định) hoặc theo một tiêu chí so sánh tùy chỉnh. Nói cách khác, nó tìm vị trí kết thúc của dãy con đã được sắp xếp tính từ đầu phạm vi.

Tham số

first

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi cần kiểm tra.

last

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi cần kiểm tra. Phạm vi là [first, last).

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ề

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi mà từ vị trí đó trở đi, phạm vi không còn được sắp xếp.
• Nếu toàn bộ phạm vi đã được sắp xếp, iterator trả về sẽ là last.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. is_sorted_until() không thay đổi phạm vi đầu vào.
3. is_sorted_until() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
4. 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.
5. is_sorted_until() thường được sử dụng để:
   • Xác định phần đầu tiên của một phạm vi đã được sắp xếp.
   • Tìm vị trí bắt đầu của phần chưa được sắp xếp trong một phạm vi.
   • Kiểm tra xem một phần của container có được sắp xếp hay không.

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

• is_sorted() kiểm tra xem toàn bộ phạm vi có được sắp xếp hay không.
• is_sorted_until() tìm vị trí phần tử đầu tiên làm mất tính sắp xếp của phạm vi.

Ví dụ

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

// Hàm so sánh để kiểm tra sắp xếp giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

int main() {
  std::vector<int> numbers1 = {1, 2, 3, 4, 5, 3, 4};
  std::vector<int> numbers2 = {5, 4, 3, 2, 1, 6, 0};
  std::vector<int> numbers3 = {1, 2, 3, 4, 5};

  // Tìm vị trí phần tử đầu tiên không theo thứ tự tăng dần trong numbers1
  auto it1 = std::is_sorted_until(numbers1.begin(), numbers1.end());
  std::cout << "numbers1 is sorted until index: " << (it1 - numbers1.begin()) << std::endl;
  if (it1 != numbers1.end())
      std::cout << "Value: " << *it1 << std::endl;

  // Tìm vị trí phần tử đầu tiên không theo thứ tự giảm dần trong numbers2
  auto it2 = std::is_sorted_until(numbers2.begin(), numbers2.end(), compareDescending);
  std::cout << "numbers2 is sorted (descending) until index: " << (it2 - numbers2.begin()) << std::endl;
  if (it2 != numbers2.end())
      std::cout << "Value: " << *it2 << std::endl;

  // Kiểm tra numbers3 (đã sắp xếp hoàn toàn)
  auto it3 = std::is_sorted_until(numbers3.begin(), numbers3.end());
  if (it3 == numbers3.end()) {
    std::cout << "numbers3 is completely sorted.\n";
  } else {
      std::cout << "numbers3 is not completely sorted.\n";
  }

  return 0;
}

Các hàm liên quan

is_sorted	Kiểm tra xem một phạm vi đã được sắp xếp theo thứ tự tăng dần hay theo một tiêu chí so sánh tùy chỉnh hay chưa
sort	Sắp xếp các phần tử trong một phạm vi theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh
find_if	Tìm kiếm phần tử đầu tiên trong một phạm vi thỏa mãn một điều kiện cụ thể được xác định bởi một hàm vị từ