Bài 32.3: Sắp xếp danh sách bằng Struct trong C++

Chào mừng các bạn quay trở lại với series bài viết về C++ của FullhouseDev!

Chúng ta đã làm quen với việc sắp xếp các kiểu dữ liệu đơn giản như số nguyên (int), số thực (double) hay chuỗi (string) bằng cách sử dụng các thuật toán có sẵn hoặc tự xây dựng. Tuy nhiên, trong thế giới lập trình thực tế, dữ liệu của chúng ta thường phức tạp hơn nhiều. Chúng ta cần quản lý thông tin về sinh viên (gồm tên, điểm, mã số), về sản phẩm (tên, giá, số lượng tồn kho), hay về nhân vật trong game (tên, cấp độ, điểm kinh nghiệm)... Làm thế nào để sắp xếp một danh sách các đối tượng phức tạp như vậy?

Đây chính là lúc Struct và khả năng tùy chỉnh việc sắp xếp phát huy sức mạnh của nó! Trong bài viết này, chúng ta sẽ khám phá cách hiệu quả để sắp xếp một danh sách (cụ thể là vector) chứa các đối tượng struct trong C++.

Tại sao cần sắp xếp danh sách Struct?

Hãy tưởng tượng bạn có một danh sách sinh viên. Bạn có thể muốn:

  • Sắp xếp danh sách đó theo điểm số từ cao đến thấp để tìm thủ khoa.
  • Sắp xếp theo tên theo thứ tự bảng chữ cái để dễ tra cứu.
  • Sắp xếp theo mã số sinh viên.

Mỗi sinh viên là một tập hợp dữ liệu (tên, điểm, mã số...). Một struct trong C++ là cách hoàn hảo để nhóm các thông tin liên quan này lại thành một đơn vị duy nhất.

Định nghĩa Struct cho dữ liệu của chúng ta

Trước hết, hãy định nghĩa một struct đơn giản để đại diện cho một Sinh Viên:

#include <string>

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;
};

Trong ví dụ này, struct SinhVien có ba thành viên: ten, diem, và maSo. Chúng ta cũng thêm một constructor để tiện khởi tạo đối tượng.

Biểu diễn danh sách Struct: vector

Cách phổ biến và linh hoạt nhất để lưu trữ một danh sách các đối tượng cùng kiểu trong C++ hiện đại là sử dụng vector.

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

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;

    void in() const {
        cout << "Ma so: " << ms << ", Ten: " << ten << ", Diem: " << d << endl;
    }
};

int main() {
    vector<SV> ds;

    ds.push_back(SV("Nguyen Van A", 8.5, 101));
    ds.push_back(SV("Le Thi B", 9.2, 105));
    ds.push_back(SV("Tran Van C", 7.8, 102));
    ds.push_back(SV("Pham Thi D", 8.5, 104));
    ds.push_back(SV("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    return 0;
}

Output:

Danh sach ban dau:
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2

Đoạn code này chỉ đơn thuần tạo một vector và thêm dữ liệu vào. Bây giờ, làm sao để sắp xếp danhSachSV theo điểm số hoặc tên?

Thử thách: sort không "biết" cách so sánh Struct của bạn!

Hàm sort trong thư viện <algorithm> là công cụ mạnh mẽ để sắp xếp. Đối với kiểu dữ liệu cơ bản, nó hoạt động mặc định vì C++ đã biết cách so sánh chúng (ví dụ: int < int, string < string).

Tuy nhiên, khi bạn gọi sort trên vector<SinhVien>, trình biên dịch sẽ "bối rối". Nó không có quy tắc mặc định nào để so sánh hai đối tượng SinhVien. Liệu SinhVien A có "nhỏ hơn" SinhVien B không? Dựa vào điểm số? Dựa vào tên? Hay mã số?

Chúng ta cần phải chỉ cho sort biết cách so sánh hai đối tượng SinhVien. Có một vài cách để làm điều này.

Phương pháp 1: Sử dụng Hàm So Sánh (Comparison Function)

Cách phổ biến và linh hoạt nhất là viết một hàm riêng biệt chỉ dùng để so sánh hai đối tượng thuộc struct của bạn. Hàm này sẽ trả về bool và nhận hai đối tượng const tham chiếu làm đối số.

  • Hàm so sánh phải có cấu trúc bool tenHam(const Kieu& a, const Kieu& b).
  • Hàm sẽ trả về true nếu a nên đứng trước b trong danh sách đã sắp xếp, và false nếu ngược lại.
Ví dụ: Sắp xếp theo điểm số từ cao đến thấp

Để sắp xếp theo điểm giảm dần, chúng ta muốn sinh viên có điểm cao hơn đứng trước.

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

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;

    void in() const {
        cout << "Ma so: " << ms << ", Ten: " << ten << ", Diem: " << d << endl;
    }
};

bool ssDiemGiam(const SV& s1, const SV& s2) {
    return s1.d > s2.d;
}

int main() {
    vector<SV> ds;
    ds.push_back(SV("Nguyen Van A", 8.5, 101));
    ds.push_back(SV("Le Thi B", 9.2, 105));
    ds.push_back(SV("Tran Van C", 7.8, 102));
    ds.push_back(SV("Pham Thi D", 8.5, 104));
    ds.push_back(SV("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    sort(ds.begin(), ds.end(), ssDiemGiam);

    cout << "Danh sach sau khi sap xep theo diem giam dan:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    return 0;
}

Output:

Danh sach ban dau:
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2

Danh sach sau khi sap xep theo diem giam dan:
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 103, Ten: Hoang Van E, Diem: 9.2
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 102, Ten: Tran Van C, Diem: 7.8

Giải thích:

  • Chúng ta định nghĩa hàm ssDiemGiam nhận hai const SV& (s1 và s2).
  • return s1.d > s2.d; nghĩa là: nếu điểm của s1 lớn hơn điểm của s2, hàm trả về true. Điều này báo cho sort biết rằng s1 nên đứng trước s2 trong kết quả cuối cùng (sắp xếp giảm dần).
  • Chúng ta truyền tên hàm ssDiemGiam làm đối số thứ ba cho sort.

Kết quả sẽ là danh sách sinh viên được sắp xếp từ điểm cao nhất đến thấp nhất.

Phương pháp 2: Sử dụng Biểu thức Lambda (Lambda Expression)

Trong C++ hiện đại (từ C++11 trở lên), lambda expression là một cách rất tiện lợi để viết các hàm nhỏ, ẩn danh (không có tên) ngay tại chỗ cần sử dụng. Điều này rất hữu ích cho các hàm so sánh chỉ dùng một lần.

Lambda expression có cấu trúc [capture](parameters) -> return_type { body }. Đối với hàm so sánh cho sort, nó thường có dạng [](const Kieu& a, const Kieu& b){ return ...; }.

Ví dụ: Sắp xếp theo điểm số từ thấp đến cao bằng Lambda
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;

    void in() const {
        cout << "Ma so: " << ms << ", Ten: " << ten << ", Diem: " << d << endl;
    }
};

int main() {
    vector<SV> ds;
    ds.push_back(SV("Nguyen Van A", 8.5, 101));
    ds.push_back(SV("Le Thi B", 9.2, 105));
    ds.push_back(SV("Tran Van C", 7.8, 102));
    ds.push_back(SV("Pham Thi D", 8.5, 104));
    ds.push_back(SV("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

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

    cout << "Danh sach sau khi sap xep theo diem tang dan (bang lambda):" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const SV& s1, const SV& s2) {
        return s1.ten < s2.ten;
    });

    cout << "Danh sach sau khi sap xep theo ten tang dan (bang lambda):" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    return 0;
}

Output:

Danh sach ban dau:
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2

Danh sach sau khi sap xep theo diem tang dan (bang lambda):
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2
Ma so: 105, Ten: Le Thi B, Diem: 9.2

Danh sach sau khi sap xep theo ten tang dan (bang lambda):
Ma so: 103, Ten: Hoang Van E, Diem: 9.2
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 102, Ten: Tran Van C, Diem: 7.8

Giải thích:

  • Thay vì định nghĩa một hàm riêng, chúng ta viết lambda expression [](const SV& s1, const SV& s2) { return s1.d < s2.d; } ngay tại vị trí đối số thứ ba của sort.
  • [] là capture clause (ở đây trống vì lambda không cần truy cập biến bên ngoài).
  • (const SV& s1, const SV& s2) là danh sách tham số, giống như hàm thông thường.
  • { return s1.d < s2.d; } là thân hàm, chứa logic so sánh. s1.d < s2.d trả về true nếu điểm của s1 nhỏ hơn s2, tức là s1 nên đứng trước (sắp xếp tăng dần).
  • Lambda expression thường làm cho code ngắn gọn và dễ đọc hơn khi hàm so sánh chỉ được sử dụng một lần duy nhất.

Phương pháp 3: Nạp chồng toán tử < (Operator Overloading)

Nếu struct của bạn có một tiêu chí sắp xếp tự nhiên hoặc mặc định (ví dụ: luôn muốn sắp xếp sinh viên theo mã số tăng dần), bạn có thể nạp chồng (overload) toán tử so sánh < cho struct đó.

Khi bạn nạp chồng operator< bên trong struct, bạn đang chỉ cho C++ cách so sánh hai đối tượng cùng kiểu đó một cách mặc định. Sau đó, bạn có thể gọi sort mà không cần cung cấp đối số thứ ba.

Ví dụ: Sắp xếp theo mã số tăng dần bằng nạp chồng operator<
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;

    void in() const {
        cout << "Ma so: " << ms << ", Ten: " << ten << ", Diem: " << d << endl;
    }

    bool operator<(const SV& khac) const {
        return this->ms < khac.ms;
    }
};

int main() {
    vector<SV> ds;
    ds.push_back(SV("Nguyen Van A", 8.5, 101));
    ds.push_back(SV("Le Thi B", 9.2, 105));
    ds.push_back(SV("Tran Van C", 7.8, 102));
    ds.push_back(SV("Pham Thi D", 8.5, 104));
    ds.push_back(SV("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    sort(ds.begin(), ds.end());

    cout << "Danh sach sau khi sap xep theo ma so tang dan (bang operator<):" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    return 0;
}

Output:

Danh sach ban dau:
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2

Danh sach sau khi sap xep theo ma so tang dan (bang operator<):
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 103, Ten: Hoang Van E, Diem: 9.2
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2

Giải thích:

  • Chúng ta định nghĩa hàm thành viên bool operator<(const SV& khac) const bên trong struct SV.
  • Hàm này nhận một tham chiếu const đến một đối tượng SV khác (khac).
  • return this->ms < khac.ms; so sánh ms của đối tượng hiện tại (this->ms) với ms của đối tượng khac. Nó trả về true nếu ms của đối tượng hiện tại nhỏ hơn (<) của đối tượng kia. Điều này định nghĩa thứ tự "nhỏ hơn" mặc định dựa trên mã số.
  • Từ khóa const cuối hàm cho biết hàm này không thay đổi trạng thái của đối tượng hiện tại, rất quan trọng cho tính const-correctness.
  • Khi bạn gọi sort(ds.begin(), ds.end()); mà không có đối số thứ ba, sort sẽ tự động tìm và sử dụng operator< đã được nạp chồng cho kiểu SV.

Lưu ý quan trọng: Nạp chồng operator< chỉ định nghĩa một tiêu chí sắp xếp mặc định duy nhất. Nếu bạn thường xuyên cần sắp xếp theo các tiêu chí khác nhau (lúc theo điểm, lúc theo tên), thì sử dụng hàm so sánh riêng hoặc lambda là linh hoạt hơn. Nạp chồng operator< phù hợp khi có một thứ tự "tự nhiên" cho kiểu dữ liệu của bạn.

Sắp xếp theo nhiều tiêu chí

Thường thì việc sắp xếp cần phức tạp hơn một chút. Ví dụ: Sắp xếp sinh viên theo điểm giảm dần, nhưng nếu hai sinh viên có cùng điểm, thì sắp xếp họ theo tên tăng dần theo thứ tự bảng chữ cái.

Logic này cần được xây dựng bên trong hàm so sánh (hoặc lambda):

  1. So sánh tiêu chí chính (điểm).
  2. Nếu tiêu chí chính bằng nhau, chuyển sang so sánh tiêu chí phụ (tên).
Ví dụ: Sắp xếp theo Điểm giảm dần, sau đó theo Tên tăng dần

Sử dụng lambda expression sẽ rất gọn gàng trong trường hợp này:

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

struct SV {
    string ten;
    double d;
    int ms;

    SV(string t, double diem, int ma) : ten(t), d(diem), ms(ma) {}
    SV() = default;

    void in() const {
        cout << "Ma so: " << ms << ", Ten: " << ten << ", Diem: " << d << endl;
    }
};

int main() {
    vector<SV> ds;
    ds.push_back(SV("Nguyen Van A", 8.5, 101));
    ds.push_back(SV("Le Thi B", 9.2, 105));
    ds.push_back(SV("Tran Van C", 7.8, 102));
    ds.push_back(SV("Pham Thi D", 8.5, 104));
    ds.push_back(SV("Hoang Van E", 9.2, 103));

    cout << "Danh sach ban dau:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const SV& s1, const SV& s2) {
        if (s1.d != s2.d) {
            return s1.d > s2.d;
        }
        return s1.ten < s2.ten;
    });

    cout << "Danh sach sau khi sap xep theo Diem giam dan, Ten tang dan:" << endl;
    for (const auto& sv : ds) {
        sv.in();
    }
    cout << endl;

    return 0;
}

Output:

Danh sach ban dau:
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 102, Ten: Tran Van C, Diem: 7.8
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 103, Ten: Hoang Van E, Diem: 9.2

Danh sach sau khi sap xep theo Diem giam dan, Ten tang dan:
Ma so: 103, Ten: Hoang Van E, Diem: 9.2
Ma so: 105, Ten: Le Thi B, Diem: 9.2
Ma so: 101, Ten: Nguyen Van A, Diem: 8.5
Ma so: 104, Ten: Pham Thi D, Diem: 8.5
Ma so: 102, Ten: Tran Van C, Diem: 7.8

Giải thích:

  • Lambda expression trước hết kiểm tra xem điểm của hai sinh viên có khác nhau không (s1.d != s2.d).
  • Nếu điểm khác nhau, nó trả về kết quả so sánh điểm theo thứ tự giảm dần (s1.d > s2.d).
  • Nếu điểm bằng nhau, khối if bị bỏ qua, và hàm sẽ chuyển sang câu lệnh return s1.ten < s2.ten;. Lệnh này so sánh tên theo thứ tự tăng dần (bảng chữ cái). Tên nào "nhỏ hơn" (đứng trước trong bảng chữ cái) thì s1 sẽ đứng trước s2.
  • Logic này đảm bảo tiêu chí điểm được ưu tiên trước, và tên chỉ được dùng để phân xử khi điểm trùng nhau.

Bài tập ví dụ: C++ Bài 19.A3: Messi vs Ronaldo

Messi vs Ronaldo

FullHouse Dev đang tổ chức một cuộc tranh luận về ai là cầu thủ xuất sắc hơn giữa Messi và Ronaldo. Họ quyết định so sánh điểm số của hai cầu thủ này trong mùa giải hiện tại.

Ở FullHouseLand, một cầu thủ bóng đá nhận được 2 điểm cho mỗi bàn thắng và 1 điểm cho mỗi đường kiến tạo.

Messi có A bàn thắng và B đường kiến tạo mùa này, trong khi Ronaldo có X bàn thắng và Y đường kiến tạo. Hãy giúp FullHouse Dev xác định cầu thủ nào có nhiều điểm hơn trong mùa giải này.

INPUT FORMAT

  • Dòng đầu tiên và duy nhất chứa bốn số nguyên cách nhau bởi dấu cách A, B, X và Y, lần lượt là số bàn thắng và đường kiến tạo của Messi, và số bàn thắng và đường kiến tạo của Ronaldo.

OUTPUT FORMAT

In ra một dòng duy nhất chứa:

  • Messi, nếu Messi có nhiều điểm hơn Ronaldo.
  • Ronaldo, nếu Ronaldo có nhiều điểm hơn Messi.
  • Equal, nếu cả hai có số điểm bằng nhau.

Bạn có thể in mỗi ký tự in hoa hoặc in thường. Ví dụ, các chuỗi Messi, MESSI, messi và MeSSi được coi là giống nhau.

CONSTRAINTS

  • 0 ≤ A, B, X, Y ≤ 100
Ví dụ

Input 1

40 30 50 10

Output 1

Equal

Giải thích 1: Messi có 40 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 40 2 + 30 = 110. Ronaldo có 50 bàn thắng và 10 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 50 2 + 10 = 110. Cả hai đều có 110 điểm.

Input 2

91 22 60 30

Output 2

Messi

Giải thích 2: Messi có 91 bàn thắng và 22 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 91 2 + 22 = 204. Ronaldo có 60 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 60 2 + 30 = 150. Messi có 204 điểm, trong khi Ronaldo có 150 điểm.

Input 3

60 30 80 20

Output 3

Ronaldo

Giải thích 3: Messi có 60 bàn thắng và 30 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 60 2 + 30 = 150. Ronaldo có 80 bàn thắng và 20 đường kiến tạo. Vì vậy, tổng điểm của anh ấy là 80 2 + 20 = 180. Messi có 150 điểm, trong khi Ronaldo có 180 điểm.

#include <iostream>

int main() {
    int a, b, x, y;
    cin >> a >> b >> x >> y;

    int dm = a * 2 + b;
    int dr = x * 2 + y;

    if (dm > dr) {
        cout << "Messi" << endl;
    } else if (dr > dm) {
        cout << "Ronaldo" << endl;
    } else {
        cout << "Equal" << endl;
    }

    return 0;
}

Output cho Input 1:

Equal

Output cho Input 2:

Messi

Output cho Input 3:

Ronaldo

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

Comments

There are no comments at the moment.