Bài 21.2: Hàm so sánh cho sort trong C++

Chào mừng trở lại với series blog về C++! Trong bài viết hôm nay, chúng ta sẽ khám phá một khía cạnh cực kỳ quan trọng khi làm việc với việc sắp xếp dữ liệu trong C++: Hàm so sánh (Comparator) cho hàm sort.

sort là một công cụ vô cùng mạnh mẽ và hiệu quả trong Thư viện Chuẩn C++ (STL) để sắp xếp các phần tử trong một phạm vi (range). Mặc định, sort sẽ sắp xếp các phần tử theo thứ tự tăng dần (ascending order) dựa trên toán tử operator< của kiểu dữ liệu. Tuy nhiên, cuộc sống lập trình không phải lúc nào cũng đơn giản như vậy. Sẽ có rất nhiều trường hợp bạn cần sắp xếp dữ liệu theo một tiêu chí khác hoàn toàn, ví dụ như:

Sắp xếp theo thứ tự giảm dần (descending order).
Sắp xếp các chuỗi dựa trên chiều dài thay vì thứ tự từ điển.
Sắp xếp các đối tượng phức tạp (struct, class) dựa trên một thuộc tính cụ thể của chúng.
Sắp xếp các cặp (pair) dựa trên phần tử thứ hai thay vì phần tử thứ nhất.

Đây chính là lúc mà hàm so sánh tùy chỉnh phát huy tác dụng!

`sort` Mặc Định Hoạt Động Như Thế Nào?

Trước khi đi sâu vào hàm so sánh, hãy xem lại cách sort hoạt động với hành vi mặc định của nó. Nó sử dụng operator< để xác định xem một phần tử có nên đứng trước phần tử khác hay không.

#include <iostream>
#include <vector>
#include <algorithm> // Thư viện chứa sort
#include <string>

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

    // Sắp xếp mặc định (tăng dần)
    sort(numbers.begin(), numbers.end());

    cout << "Mang sau khi sap xep tang dan: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    vector<string> words = {"banana", "apple", "orange", "kiwi"};

    // Sắp xếp mặc định (theo thứ tự từ điển)
    sort(words.begin(), words.end());

    cout << "Vector chuoi sau khi sap xep tu dien: ";
    for (const string& word : words) {
        cout << word << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Trong ví dụ đầu, sort sắp xếp vector numbers theo thứ tự tăng dần vì kiểu int có operator< được định nghĩa sẵn.
Trong ví dụ thứ hai, sort sắp xếp vector words theo thứ tự từ điển vì kiểu string cũng có operator< được định nghĩa sẵn cho phép so sánh theo thứ tự từ điển.

Khi Nào Cần Hàm So Sánh Tùy Chỉnh?

Bất cứ khi nào bạn muốn sắp xếp dữ liệu theo một tiêu chí không phải là thứ tự tăng dần dựa trên operator<, bạn cần cung cấp một hàm so sánh tùy chỉnh. Hàm này cho sort biết cách xác định thứ tự của bất kỳ hai phần tử nào trong phạm vi cần sắp xếp.

Hàm so sánh này phải tuân thủ một số quy tắc nhất định (được gọi là Strict Weak Ordering), nhưng về cơ bản, nó là một hàm nhận hai đối số cùng kiểu với các phần tử trong phạm vi và trả về một giá trị bool.

Nếu hàm trả về true, điều đó có nghĩa là đối số đầu tiên được coi là nhỏ hơn (hoặc nên đứng trước) đối số thứ hai theo tiêu chí sắp xếp của bạn.
Nếu hàm trả về false, điều đó có nghĩa là đối số đầu tiên không được coi là nhỏ hơn đối số thứ hai.

Các Cách Cung Cấp Hàm So Sánh

Có ba cách phổ biến để cung cấp hàm so sánh cho sort trong C++:

Sử dụng Con trỏ hàm (Function Pointer)
Sử dụng Đối tượng hàm (Function Object / Functor)
Sử dụng Biểu thức Lambda (Lambda Expression) - _Cách hiện đại và phổ biến nhất_

Chúng ta hãy đi qua từng cách với ví dụ cụ thể.

1. Sử Dụng Con Trỏ Hàm

Bạn có thể viết một hàm độc lập nhận hai đối số cùng kiểu và trả về bool, sau đó truyền tên hàm đó (thực chất là địa chỉ của hàm) cho sort.

Ví dụ: Sắp xếp vector int theo thứ tự giảm dần.

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

// Hàm so sánh cho thứ tự giảm dần
bool compareDescending(int a, int b) {
    // Trả về true nếu 'a' nên đứng trước 'b'
    // Trong sắp xếp giảm dần, 'a' nên đứ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};

    // Truyền tên hàm so sánh vào sort
    sort(numbers.begin(), numbers.end(), compareDescending);

    cout << "Mang sau khi sap xep giam dan (func pointer): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Hàm compareDescending(int a, int b) nhận hai số nguyên a và b.
Nó trả về true nếu a > b. Điều này nói với sort rằng "theo tiêu chí của tôi, nếu a lớn hơn b, thì a nên được đặt trước b". Đây chính là định nghĩa của sắp xếp giảm dần.

2. Sử Dụng Đối Tượng Hàm (Functor)

Đối tượng hàm là một lớp hoặc cấu trúc (struct) mà bạn nạp chồng (overload) toán tử gọi hàm operator(). Điều này cho phép bạn sử dụng một đối tượng như một hàm. Ưu điểm là đối tượng hàm có thể chứa trạng thái (dữ liệu thành viên), điều mà con trỏ hàm không làm được.

Ví dụ: Sắp xếp vector int theo thứ tự giảm dần sử dụng functor.

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

// Định nghĩa một struct đóng vai trò là Functor
struct CompareDescendingFunctor {
    // Nạp chồng toán tử gọi hàm
    bool operator()(int a, int b) const {
        // Trả về true nếu 'a' nên đứng trước 'b'
        return a > b;
    }
};

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

    // Tạo một đối tượng của Functor và truyền vào sort
    sort(numbers.begin(), numbers.end(), CompareDescendingFunctor());

    cout << "Mang sau khi sap xep giam dan (functor): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Struct CompareDescendingFunctor định nghĩa operator() nhận hai int và trả về bool a > b.
Khi gọi sort, chúng ta tạo một đối tượng tạm thời của struct này (CompareDescendingFunctor()) và truyền nó vào. sort sẽ gọi operator() của đối tượng này để thực hiện so sánh.

3. Sử Dụng Biểu Thức Lambda (Cách Hiện Đại và Phổ Biến)

Biểu thức lambda là một tính năng của C++11 trở lên, cho phép bạn định nghĩa một hàm ẩn danh (anonymous function) ngay tại chỗ cần sử dụng nó. Lambda rất gọn gàng và thường là lựa chọn tốt nhất cho các hàm so sánh đơn giản.

Ví dụ: Sắp xếp vector int theo thứ tự giảm dần sử dụng lambda.

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

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

    // Sử dụng lambda expression làm hàm so sánh
    sort(numbers.begin(), numbers.end(), [](int a, int b){
        // Trả về true nếu 'a' nên đứng trước 'b'
        return a > b; // Đối với giảm dần, 'a' > 'b'
    });

    cout << "Mang sau khi sap xep giam dan (lambda): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Cú pháp [](int a, int b){ return a > b; } định nghĩa một lambda.
[] là capture clause (chúng ta sẽ tìm hiểu sau, ở đây để trống vì không cần bắt giữ biến bên ngoài).
(int a, int b) là danh sách tham số, giống như một hàm thông thường.
{ return a > b; } là thân hàm lambda.
Lambda này được truyền trực tiếp như đối số thứ ba cho sort. Nó thực hiện chính xác logic so sánh giảm dần tương tự như hai cách trên.

Lambda thường được ưa chuộng vì tính ngắn gọn và đọc hiểu khi logic so sánh không quá phức tạp.

Các Ví Dụ Nâng Cao Hơn

Hãy xem thêm một vài ví dụ sử dụng lambda để sắp xếp các kiểu dữ liệu phức tạp hơn hoặc theo tiêu chí đặc biệt.

Ví dụ 1: Sắp xếp string theo chiều dài.

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

int main() {
    vector<string> words = {"banana", "apple", "kiwi", "orange", "grape"};

    // Sắp xếp theo chiều dài tăng dần
    sort(words.begin(), words.end(), [](const string& s1, const string& s2) {
        return s1.length() < s2.length(); // true nếu s1 ngắn hơn s2
    });

    cout << "Chuoi sau khi sap xep theo chieu dai tang dan: ";
    for (const string& word : words) {
        cout << word << " ";
    }
    cout << endl;

     // Sắp xếp theo chiều dài giảm dần
    sort(words.begin(), words.end(), [](const string& s1, const string& s2) {
        return s1.length() > s2.length(); // true nếu s1 dài hơn s2
    });

    cout << "Chuoi sau khi sap xep theo chieu dai giam dan: ";
    for (const string& word : words) {
        cout << word << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Lambda nhận hai tham chiếu hằng đến string.
Nó so sánh .length() của hai chuỗi. s1.length() < s2.length() trả về true nếu s1 ngắn hơn s2, dẫn đến sắp xếp tăng dần theo chiều dài. s1.length() > s2.length() cho sắp xếp giảm dần.

Ví dụ 2: Sắp xếp pair<int, int> dựa trên phần tử thứ hai.

#include <iostream>
#include <vector>
#include <utility> // for pair
#include <algorithm>

int main() {
    vector<pair<int, int>> data = {{1, 5}, {3, 2}, {2, 8}, {4, 1}, {5, 2}};

    // Sắp xếp dựa trên phần tử thứ hai (second element) tăng dần
    sort(data.begin(), data.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
        return p1.second < p2.second; // true nếu p1.second nhỏ hơn p2.second
    });

    cout << "Vector pair sau khi sap xep theo phan tu thu hai: ";
    for (const auto& p : data) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;

    // Lưu ý: Nếu p1.second == p2.second, thứ tự ban đầu của chúng được giữ nguyên
    // (sort là stable sort, nhưng comparator chỉ cần strict weak ordering)
    // Nếu muốn sắp xếp phụ (secondary sort key) dựa trên first element khi second element bằng nhau,
    // chúng ta cần bổ sung logic:
     sort(data.begin(), data.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
        if (p1.second != p2.second) {
            return p1.second < p2.second; // Sort by second element first
        }
        return p1.first < p2.first; // If second elements are equal, sort by first element
    });
    cout << "Vector pair sau khi sap xep theo phan tu thu hai, roi thu nhat: ";
     for (const auto& p : data) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Lambda nhận hai tham chiếu hằng đến pair<int, int>.
Trong ví dụ đầu, nó chỉ so sánh p1.second và p2.second.
Trong ví dụ thứ hai, nó thể hiện cách xử lý sắp xếp với nhiều tiêu chí (secondary sort key). Đầu tiên so sánh second, nếu bằng nhau thì mới so sánh first.

Ví dụ 3: Sắp xếp một vector các đối tượng struct tùy chỉnh.

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

struct SinhVien {
    string ten;
    int diem;
    int tuoi;
};

int main() {
    vector<SinhVien> danhSach = {
        {"Alice", 85, 20},
        {"Bob", 92, 21},
        {"Charlie", 78, 20},
        {"David", 92, 22} // David có cùng điểm với Bob
    };

    // Sắp xếp theo điểm số tăng dần
    sort(danhSach.begin(), danhSach.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        return sv1.diem < sv2.diem; // true nếu sv1.diem nhỏ hơn sv2.diem
    });

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

    // Sắp xếp theo điểm số giảm dần, nếu điểm bằng nhau thì sắp xếp theo tuổi tăng dần
     sort(danhSach.begin(), danhSach.end(), [](const SinhVien& sv1, const SinhVien& sv2) {
        if (sv1.diem != sv2.diem) {
            return sv1.diem > sv2.diem; // Sắp xếp điểm giảm dần (true nếu sv1.diem LỚN HƠN sv2.diem)
        }
        return sv1.tuoi < sv2.tuoi; // Nếu điểm bằng nhau, sắp xếp tuổi tăng dần (true nếu sv1.tuoi NHỎ HƠN sv2.tuoi)
    });

    cout << "Danh sach sau khi sap xep theo diem (giam), roi tuoi (tang):" << endl;
    for (const auto& sv : danhSach) {
        cout << sv.ten << " (" << sv.diem << " diem, " << sv.tuoi << " tuoi)" << endl;
    }
    cout << endl;

    return 0;
}

Giải thích:

Ví dụ này minh họa việc sắp xếp các đối tượng struct SinhVien.
Lambda trong ví dụ đầu so sánh trực tiếp thuộc tính diem của hai sinh viên.
Lambda thứ hai cho thấy logic sắp xếp phức tạp hơn: ưu tiên sắp xếp giảm dần theo diem, nếu hai sinh viên có cùng điểm, sẽ sắp xếp tăng dần theo tuoi.

Lưu Ý Quan Trọng Về Hàm So Sánh

Kiểu trả về: Phải là bool.
Số lượng đối số: Phải là hai đối số cùng kiểu với các phần tử trong container (hoặc kiểu có thể chuyển đổi được).
Tính Hằng: Đối số của hàm so sánh nên là tham chiếu hằng (const &) để tránh sao chép và đảm bảo không làm thay đổi các phần tử trong quá trình sắp xếp.
Strict Weak Ordering: Đây là yêu cầu kỹ thuật cốt lõi. Hàm so sánh comp(a, b) phải thỏa mãn:
- Bất đối xứng (Asymmetry): Nếu comp(a, b) là true, thì comp(b, a) phải là false.
- Bắc cầu (Transitivity): Nếu comp(a, b) là true và comp(b, c) là true, thì comp(a, c) cũng phải là true.
- Tính tương đương (Equivalence): Nếu !comp(a, b) và !comp(b, a) cùng đúng, thì a và b được coi là "tương đương" về mặt thứ tự (không nhất thiết phải bằng nhau).
- Vi phạm các quy tắc này có thể dẫn đến kết quả sắp xếp không chính xác hoặc thậm chí gây ra hành vi không xác định (undefined behavior).

Trong hầu hết các trường hợp phổ biến (sắp xếp tăng/giảm đơn giản, sắp xếp theo một thuộc tính, sắp xếp theo chiều dài...), việc sử dụng operator< hoặc operator> hoặc so sánh các thuộc tính đơn giản (a.prop < b.prop) sẽ tự động đáp ứng yêu cầu Strict Weak Ordering. Chỉ khi logic so sánh trở nên rất phức tạp, bạn mới cần cẩn thận kiểm tra điều này.

Bài tập ví dụ: C++ Bài 10.A5: Ứng cử viên sáng giá

Một cuộc bầu cử đang diễn ra.

Có \(N\) người đã bỏ phiếu. Người thứ \(i\) (\(1 \leq i \leq N\)) đã bỏ phiếu cho ứng cử viên tên là \(S_i\).

Tìm tên của ứng cử viên nhận được nhiều phiếu nhất. Đầu vào đảm bảo rằng có một ứng cử viên duy nhất nhận được nhiều phiếu nhất.

Ràng buộc

\(1 \leq N \leq 100\) \(S_i\) là một chuỗi có độ dài từ \(1\) đến \(10\) (bao gồm) và gồm các chữ cái tiếng Anh viết thường. \(N\) là một số nguyên. Có một ứng cử viên duy nhất nhận được nhiều phiếu nhất.

Đầu vào

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

\(N\) \(S_1\) \(S_2\) \(\vdots\) \(S_N\)

Đầu ra

In tên của ứng cử viên nhận được nhiều phiếu nhất.

Ví dụ:

Ví dụ 1

Đầu vào

5
snuke
snuke
takahashi
takahashi
takahashi

Đầu ra

takahashi

\(takahashi\) nhận được \(3\) phiếu, và \(snuke\) nhận được \(2\), vì vậy chúng ta in \(takahashi\).

Ví dụ 2

Đầu vào

5
takahashi
takahashi
aoki
takahashi
snuke

Đầu ra

takahashi

Ví dụ 3

Đầu vào

1
a

Đầu ra

Giải thích ví dụ mẫu

Tính số phiếu cho mỗi ứng cử viên và chọn ứng cử viên có số phiếu nhiều nhất.

<br>

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House Chào bạn, đây là hướng dẫn giải bài "Ứng cử viên sáng giá" bằng C++ sử dụng thư viện chuẩn (std):

Phân tích bài toán:

Bài toán yêu cầu chúng ta đếm số phiếu bầu cho từng ứng cử viên và tìm ra ứng cử viên nhận được nhiều phiếu nhất. Đầu vào là số lượng phiếu bầu N và sau đó là N tên ứng cử viên (mỗi tên là một phiếu bầu). Đảm bảo có một ứng cử viên duy nhất có số phiếu cao nhất.

Ý tưởng giải:

Đếm số phiếu: Chúng ta cần một cách để lưu trữ tên của từng ứng cử viên cùng với số phiếu bầu mà họ nhận được. Khi đọc từng phiếu bầu, chúng ta sẽ tăng số đếm cho ứng cử viên tương ứng.
Tìm ứng cử viên có phiếu cao nhất: Sau khi đếm xong tất cả các phiếu, chúng ta sẽ duyệt qua danh sách các ứng cử viên và số phiếu của họ để tìm ra ứng cử viên có số phiếu lớn nhất.

Lựa chọn cấu trúc dữ liệu:

Để lưu trữ cặp (tên ứng cử viên, số phiếu), một cấu trúc dữ liệu phù hợp là ánh xạ (map), nơi khóa (key) là tên ứng cử viên (kiểu string) và giá trị (value) là số phiếu bầu (kiểu int). Trong C++, map hoặc unordered_map là lựa chọn tốt từ thư viện chuẩn.

map: Duy trì các khóa theo thứ tự sắp xếp. Việc truy cập/chèn thường là O(log K), với K là số lượng ứng cử viên duy nhất.
unordered_map: Sử dụng bảng băm, việc truy cập/chèn trung bình là O(1), nhưng có thể O(K) trong trường hợp xấu nhất.

Với giới hạn N <= 100, cả hai đều hoạt động hiệu quả. map đơn giản hơn về mặt lý thuyết và đảm bảo hiệu suất O(log K). Ta sẽ ưu tiên sử dụng map hoặc unordered_map tùy thuộc vào sở thích.

Các bước thực hiện (Hướng dẫn giải):

Bao gồm các thư viện cần thiết: Bạn sẽ cần thư viện cho nhập/xuất (iostream), xử lý chuỗi (string) và ánh xạ (map hoặc unordered_map).
Đọc đầu vào:
- Đọc số nguyên N.
- Tạo một đối tượng map, ví dụ: map<string, int> vote_counts;.
- Sử dụng vòng lặp để đọc N chuỗi (tên ứng cử viên).
- Trong mỗi lần lặp, với mỗi tên ứng cử viên đọc được (ví dụ: candidate_name), hãy cập nhật số phiếu trong map. Cách đơn giản nhất là dùng vote_counts[candidate_name]++;. Nếu candidate_name chưa tồn tại trong map, nó sẽ được thêm vào với giá trị mặc định là 0 trước khi tăng lên 1.
Tìm người thắng cuộc:
- Khởi tạo hai biến: một biến để lưu số phiếu tối đa tìm được cho đến nay (ví dụ: max_votes = 0) và một biến để lưu tên ứng cử viên tương ứng (ví dụ: winner_name = "").
- Duyệt qua tất cả các phần tử trong map vote_counts. Mỗi phần tử là một cặp (tên ứng cử viên, số phiếu). Bạn có thể dùng vòng lặp for (const auto& pair : vote_counts) để duyệt map.
- Trong mỗi lần duyệt, so sánh số phiếu của ứng cử viên hiện tại (pair.second) với max_votes.
- Nếu số phiếu hiện tại lớn hơn max_votes:
  - Cập nhật max_votes bằng số phiếu hiện tại.
  - Cập nhật winner_name bằng tên ứng cử viên hiện tại (pair.first).
In kết quả: In ra chuỗi winner_name.

Lưu ý khi viết code:

Sử dụng cin để đọc đầu vào và cout để in kết quả.
Đảm bảo bạn bao gồm đúng các header files (iostream, string, map hoặc unordered_map).
Có thể thêm return 0; ở cuối hàm main để chỉ báo chương trình kết thúc thành công.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.