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à:

Một phần tử không thể "nhỏ hơn" chính nó.
Nếu a "nhỏ hơn" b, thì b không thể "nhỏ hơn" a.
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:

Sử dụng hàm độc lập (Regular Function): Tạo một hàm thông thường.
Sử dụng đối tượng hàm (Functor): Tạo một class/struct và overload toán tử ().
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>

using namespace std;

bool ssGiam(int a, int b) {
    return a > b;
}

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

    cout << "Vector ban dau: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl;

    sort(so.begin(), so.end(), ssGiam);

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

    return 0;
}

Output:

Vector ban dau: 5 2 8 1 9 4 7 3 6 
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>

using namespace std;

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

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

    sort(chuoi.begin(), chuoi.end(), [](const string& a, const string& b) {
        return a.length() < b.length();
    });

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

    return 0;
}

Output:

Vector chuoi ban dau: apple banana cherry date grape fig 
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>

using namespace std;

struct SV {
    string t;
    int d;
};

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

    cout << "Danh sach Sinh Vien ban dau:" << endl;
    for (const auto& x : ds) {
        cout << x.t << " (" << x.d << ") ";
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const SV& a, const SV& b) {
        return a.d < b.d;
    });

    cout << "Danh sach Sinh Vien sau khi sap xep theo diem (tang dan):" << endl;
    for (const auto& x : ds) {
        cout << x.t << " (" << x.d << ") ";
    }
    cout << endl;

    return 0;
}

Output:

Danh sach Sinh Vien ban dau:
An (85) Binh (92) Hoa (78) Minh (95) Lan (88) 
Danh sach Sinh Vien sau khi sap xep theo diem (tang dan):
Hoa (78) An (85) Lan (88) Binh (92) Minh (95)

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.