Bài 22.2: Bài tinh thực hành hàm so sánh trong C++

Chào mừng bạn trở lại với series học lập trình C++! Hôm nay, chúng ta sẽ đi vào một chủ đề thiết yếu khi làm việc với các cấu trúc dữ liệu và thuật toán trong C++: Hàm so sánh (Comparison Functions). Đây là công cụ cho phép chúng ta kiểm soát cách các phần tử được sắp xếp, tìm kiếm hoặc xử lý dựa trên các quy tắc tùy chỉnh.

Trong C++, nhiều thuật toán của Thư viện Chuẩn (Standard Library - STL), đặc biệt là các thuật toán liên quan đến sắp xếp (sort), tìm kiếm (binary_search, min_element, max_element) và các cấu trúc dữ liệu có thứ tự (map, set), đều hoạt động dựa trên khả năng so sánh hai phần tử bất kỳ để xác định mối quan hệ thứ tự của chúng.

Mặc định, các thuật toán này thường sử dụng toán tử nhỏ hơn (<) của kiểu dữ liệu để so sánh. Ví dụ, khi sắp xếp số nguyên, 5 < 10 là true, nên 5 sẽ đứng trước 10.

Tuy nhiên, phép so sánh mặc định này không phải lúc nào cũng phù hợp với nhu cầu của chúng ta. Bạn sẽ làm gì nếu muốn:

  • Sắp xếp các số theo thứ tự giảm dần?
  • Sắp xếp các chuỗi dựa trên độ dài thay vì thứ tự bảng chữ cái?
  • Sắp xếp các đối tượng tùy chỉnh (ví dụ: struct SinhVien) dựa trên một thuộc tính cụ thể như điểm số hoặc tên?

Đây chính là lúc Hàm so sánh tùy chỉnh phát huy sức mạnh của nó!

Hàm so sánh là gì?

Về cơ bản, một hàm so sánh trong ngữ cảnh này là một hàm (hoặc một đối tượng hàm - functor, hoặc một lambda) nhận hai đối số cùng kiểu và trả về một giá trị kiểu bool (hoặc có thể chuyển đổi thành bool). Giá trị trả về này cho thuật toán biết mối quan hệ thứ tự giữa hai đối số đó.

Quy tắc quan trọng cần nhớ đối với các thuật toán như sort: Hàm so sánh của bạn phải định nghĩa một quan hệ thứ tự nghiêm ngặt yếu (strict weak ordering). Nghe có vẻ phức tạp, nhưng với các trường hợp phổ biến (như dùng < hoặc >), nó thường tự động đúng. Về cơ bản, điều này có nghĩa là:

  1. Một phần tử không thể "nhỏ hơn" chính nó.
  2. Nếu a "nhỏ hơn" b, thì b không thể "nhỏ hơn" a.
  3. Nếu a "nhỏ hơn" b và b "nhỏ hơn" c, thì a phải "nhỏ hơn" c (tính bắc cầu).

Hàm so sánh trả về true khi đối số đầu tiên được coi là "đứng trước" đối số thứ hai theo tiêu chí sắp xếp mong muốn của bạn. Đối với sắp xếp tăng dần thông thường, a < b trả về true nghĩa là a đứng trước b.

Các cách định nghĩa Hàm so sánh tùy chỉnh

Trong C++, bạn có thể định nghĩa hàm so sánh theo một số cách phổ biến:

  1. Sử dụng hàm độc lập (Regular Function): Tạo một hàm thông thường.
  2. Sử dụng đối tượng hàm (Functor): Tạo một class/struct và overload toán tử ().
  3. Sử dụng biểu thức Lambda (Lambda Expression): Cách hiện đại và thường gọn gàng nhất cho các trường hợp đơn giản.

Trong bài viết này, chúng ta sẽ tập trung vào Hàm độc lập và Lambda vì chúng là hai cách được sử dụng rộng rãi nhất, đặc biệt là Lambda ngày nay.

Thực hành với sort

sort là một trong những thuật toán phổ biến nhất trong STL và là ví dụ tuyệt vời để minh họa việc sử dụng hàm so sánh tùy chỉnh. sort có phiên bản nhận ba đối số: hai iterator chỉ định phạm vi cần sắp xếp, và đối số thứ ba là hàm so sánh.

Cú pháp cơ bản: sort(first_iterator, last_iterator, comparison_function);

Hãy cùng xem các ví dụ cụ thể!

Ví dụ 1: Sắp xếp số nguyên theo thứ tự giảm dần

Mặc định, sort sắp xếp tăng dần. Để sắp xếp giảm dần, chúng ta cần một hàm so sánh trả về true khi số đầu tiên lớn hơn số thứ hai.

#include <iostream>
#include <vector>
#include <algorithm> // Bao gồm sort

// Cách 1: Sử dụng hàm độc lập làm hàm so sánh
bool compareDescending(int a, int b) {
    // Chúng ta muốn 'a' đứng trước 'b' nếu 'a' LỚN HƠN 'b'
    return a > b;
}

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4, 7, 3, 6};

    cout << "Vector ban dau: ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    // Sử dụng sort với hàm so sánh tùy chỉnh compareDescending
    // sort sẽ gọi compareDescending(a, b) để quyết định thứ tự
    sort(numbers.begin(), numbers.end(), compareDescending);

    cout << "Vector sau khi sap xep giam dan: ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Trong ví dụ này:

  • Chúng ta định nghĩa hàm compareDescending nhận hai số nguyên a và b.
  • Hàm này trả về a > b. Điều này có nghĩa là nếu a lớn hơn b, hàm so sánh trả về true.
  • Khi sort sử dụng hàm compareDescending, nó coi true là điều kiện để phần tử đầu tiên đứng trước phần tử thứ hai. Do đó, nếu a > b là true, a sẽ được đặt trước b, tạo ra thứ tự giảm dần.
  • Output sẽ là: Vector sau khi sap xep giam dan: 9 8 7 6 5 4 3 2 1.
Ví dụ 2: Sắp xếp chuỗi theo độ dài bằng Lambda

Sắp xếp theo độ dài là một yêu cầu phổ biến. Thay vì tạo hàm độc lập, chúng ta có thể sử dụng Lambda để định nghĩa hàm so sánh ngay tại chỗ.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Bao gồm sort

int main() {
    vector<string> words = {"apple", "banana", "cherry", "date", "grape", "fig"};

    cout << "Vector chuoi ban dau: ";
    for (const auto& s : words) {
        cout << s << " ";
    }
    cout << endl;

    // Cách 2: Sử dụng Lambda làm hàm so sánh
    // Sắp xếp theo độ dài tăng dần
    sort(words.begin(), words.end(), [](const string& s1, const string& s2) {
        // Chúng ta muốn 's1' đứng trước 's2' nếu độ dài của 's1' NHỎ HƠN độ dài của 's2'
        return s1.length() < s2.length();
    });

    cout << "Vector chuoi sau khi sap xep theo do dai (tang dan): ";
    for (const auto& s : words) {
        cout << s << " ";
    }
    cout << endl;

    // Nếu muốn sắp xếp theo độ dài giảm dần, chỉ cần đổi logic trong lambda
    // sort(words.begin(), words.end(), [](const string& s1, const string& s2) {
    //     return s1.length() > s2.length(); // Lon hon de dung truoc
    // });

    return 0;
}

Giải thích:

  • Biểu thức Lambda [](const string& s1, const string& s2) { return s1.length() < s2.length(); } là một hàm ẩn danh.
  • [] là capture clause (chúng ta không cần capture gì ở đây).
  • (const string& s1, const string& s2) là danh sách tham số. Ta nhận hai chuỗi làm tham chiếu hằng để hiệu quả hơn.
  • { return s1.length() < s2.length(); } là thân hàm. Nó trả về true nếu độ dài của s1 nhỏ hơn độ dài của s2.
  • sort sử dụng lambda này. Nếu s1.length() < s2.length() là true, s1 được đặt trước s2. Điều này dẫn đến việc sắp xếp các chuỗi theo thứ tự tăng dần của độ dài.
  • Output sẽ là: Vector chuoi sau khi sap xep theo do dai (tang dan): fig date apple grape banana cherry.
Ví dụ 3: Sắp xếp đối tượng tùy chỉnh (struct) theo một thuộc tính cụ thể

Làm việc với các đối tượng phức tạp là lúc hàm so sánh tùy chỉnh trở nên cực kỳ hữu ích.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Bao gồm sort

// Định nghĩa một struct SinhVien đơn giản
struct SinhVien {
    string ten;
    int diem;
};

int main() {
    vector<SinhVien> danhSach = {
        {"An", 85},
        {"Binh", 92},
        {"Hoa", 78},
        {"Minh", 95},
        {"Lan", 88}
    };

    cout << "Danh sach Sinh Vien ban dau:" << endl;
    for (const auto& sv : danhSach) {
        cout << sv.ten << " (" << sv.diem << ") ";
    }
    cout << endl;

    // Sử dụng sort với Lambda để so sánh SinhVien theo diem (tang dan)
    sort(danhSach.begin(), danhSach.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        // Chúng ta muốn 'sv1' đứng trước 'sv2' nếu diem của 'sv1' NHỎ HƠN diem của 'sv2'
        return sv1.diem < sv2.diem;
    });

    cout << "Danh sach Sinh Vien sau khi sap xep theo diem (tang dan):" << endl;
    for (const auto& sv : danhSach) {
        cout << sv.ten << " (" << sv.diem << ") ";
    }
    cout << endl;

    // Bạn cũng có thể sắp xếp theo tên (thứ tự bảng chữ cái)
    // sort(danhSach.begin(), danhSach.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
    //     return sv1.ten < sv2.ten; // So sanh theo ten
    // });
    // cout << "\nDanh sach Sinh Vien sau khi sap xep theo ten:" << endl;
    // for (const auto& sv : danhSach) {
    //     cout << sv.ten << " (" << sv.diem << ") ";
    // }
    // cout << endl;


    return 0;
}

Giải thích:

  • Chúng ta định nghĩa một struct SinhVien với hai thuộc tính ten và diem.
  • Lambda [](const SinhVien& sv1, const SinhVien& sv2) { return sv1.diem < sv2.diem; } nhận hai đối tượng SinhVien làm tham chiếu hằng.
  • Nó so sánh giá trị của thuộc tính diem của hai sinh viên.
  • sort sử dụng lambda này để sắp xếp vector danhSach dựa trên điểm số. Nếu sv1.diem < sv2.diem, sv1 sẽ được coi là "nhỏ hơn" và đứng trước sv2.
  • Output sẽ hiển thị danh sách sinh viên được sắp xếp theo điểm số tăng dần.
Vài Lời Khuyên Khi Sử Dụng Hàm So Sánh
  • Chọn đúng tiêu chí: Xác định rõ ràng bạn muốn so sánh các phần tử dựa trên tiêu chí nào (giá trị, độ dài, thuộc tính của đối tượng, v.v.).
  • Quán tính: Hãy đảm bảo logic so sánh của bạn là quán tính. Nếu a "nhỏ hơn" b theo tiêu chí của bạn, thì b không được "nhỏ hơn" a.
  • Lambda vs Hàm độc lập: Đối với các hàm so sánh đơn giản, ngắn gọn và chỉ sử dụng ở một vài nơi, Lambda thường là lựa chọn tiện lợi và rõ ràng nhất vì nó cho phép bạn định nghĩa logic so sánh ngay tại điểm sử dụng. Đối với logic phức tạp hơn hoặc cần tái sử dụng nhiều lần, một hàm độc lập hoặc functor có thể là lựa chọn tốt hơn.
  • Hiệu quả: Với các kiểu dữ liệu lớn hoặc phức tạp, hãy truyền đối số dưới dạng tham chiếu hằng (const T&) để tránh việc sao chép tốn kém.

Comments

There are no comments at the moment.