std::lexicographical_compare

#include <algorithm>

// So sánh bằng toán tử <
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2);

// Sử dụng hàm so sánh tùy chỉnh
template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              Compare comp);

So sánh hai phạm vi (range) theo thứ tự từ điển (lexicographical order). Giống như cách bạn so sánh hai từ trong từ điển, lexicographical_compare() so sánh từng cặp phần tử tương ứng trong hai phạm vi, và trả về kết quả dựa trên sự so sánh của cặp phần tử khác nhau đầu tiên được tìm thấy.

Tham số

first1

• Input Iterator trỏ đến phần tử đầu tiên trong phạm vi thứ nhất.

last1

• Input Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi thứ nhất. Phạm vi thứ nhất là [first1, last1).

first2

• Input Iterator trỏ đến phần tử đầu tiên trong phạm vi thứ hai.

last2

• Input Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi thứ hai. Phạm vi thứ hai là [first2, last2).

comp

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

true

• Nếu phạm vi thứ nhất được coi là nhỏ hơn phạm vi thứ hai theo thứ tự từ điển.

false

• Nếu phạm vi thứ nhất được coi là không nhỏ hơn phạm vi thứ hai theo thứ tự từ điển.

Đặc điểm

1. Phạm vi [first1, last1) và [first2, last2) là "nửa mở", không bao gồm phần tử last1 và last2.
2. lexicographical_compare() không thay đổi các phạm vi đầu vào.
3. lexicographical_compare() yêu cầu Input Iterator cho cả hai phạm vi đầu vào.
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. lexicographical_compare() thường được sử dụng để:
   • So sánh hai chuỗi (string).
   • So sánh hai mảng hoặc vector các số hoặc ký tự.
   • Sắp xếp các container chứa các chuỗi hoặc mảng theo thứ tự từ điển.
   • Triển khai các thuật toán liên quan đến so sánh chuỗi hoặc dãy.

Thứ tự từ điển (Lexicographical Order)

Phạm vi thứ nhất được coi là nhỏ hơn phạm vi thứ hai theo thứ tự từ điển nếu:

1. Phần tử đầu tiên khác nhau trong hai phạm vi, nhỏ hơn trong phạm vi thứ nhất so với phạm vi thứ hai (theo toán tử < hoặc comp).
2. Hoặc, nếu tất cả các phần tử tương ứng trong hai phạm vi đều bằng nhau, nhưng phạm vi thứ nhất ngắn hơn phạm vi thứ hai.

Ví dụ

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

// Hàm so sánh tùy chỉnh để so sánh theo thứ tự từ điển giảm dần
bool compareDescending(char a, char b) {
  return a > b;
}

int main() {
  std::string str1 = "apple";
  std::string str2 = "banana";
  std::string str3 = "app";

  // So sánh str1 và str2 (tăng dần)
  if (std::lexicographical_compare(str1.begin(), str1.end(), str2.begin(), str2.end())) {
    std::cout << "str1 is lexicographically less than str2.\n";
  } else {
    std::cout << "str1 is not lexicographically less than str2.\n";
  }

  // So sánh str1 và str3 (tăng dần)
  if (std::lexicographical_compare(str1.begin(), str1.end(), str3.begin(), str3.end())) {
      std::cout << "str1 is lexicographically less than str3.\n";
  } else {
      std::cout << "str1 is not lexicographically less than str3.\n";
  }
    
  // So sánh str3 và str1 (tăng dần)
  if (std::lexicographical_compare(str3.begin(), str3.end(), str1.begin(), str1.end())) {
      std::cout << "str3 is lexicographically less than str1.\n";
  } else {
      std::cout << "str3 is not lexicographically less than str1.\n";
  }

  std::string str4 = "ZOO";
  std::string str5 = "zoo";

  // So sánh str4 và str5 (giảm dần) sử dụng hàm so sánh tùy chỉnh
  if (std::lexicographical_compare(str4.begin(), str4.end(), str5.begin(), str5.end(), compareDescending)) {
    std::cout << "str4 is lexicographically less than str5 (descending).\n";
  } else {
    std::cout << "str4 is not lexicographically less than str5 (descending).\n";
  }

  return 0;
}

Các hàm liên quan

mismatch	So sánh hai phạm vi và tìm vị trí đầu tiên mà các phần tử tương ứng không khớp
equal	Kiểm tra xem hai phạm vi có bằng nhau hay không
search	Tìm kiếm sự xuất hiện đầu tiên của một dãy con trong một phạm vi lớn hơn
find_end	Tìm kiếm sự xuất hiện cuối cùng của một dãy con trong một phạm vi khác
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