Bài 28.4: Kết hợp chuỗi ký tự với set và map trong C++

Trong hành trình chinh phục C++, chúng ta đã làm quen với chuỗi ký tự (string) và các cấu trúc dữ liệu container mạnh mẽ như set (set) và map (map). Mỗi thứ đều có vai trò riêng, nhưng sức mạnh thực sự thường bộc lộ khi chúng ta kết hợp chúng lại với nhau. Bài viết này sẽ đi sâu vào cách string hoạt động tuyệt vời với set và map, mở ra nhiều cách giải quyết vấn đề một cách hiệu quả và sáng tạo.

Set là tập hợp các phần tử duy nhất, được lưu trữ có thứ tự. Map là cấu trúc lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị (key-value), trong đó khóa là duy nhất và được lưu trữ có thứ tự. Khi string trở thành phần tử của set hoặc khóa của map, chúng ta có thể thực hiện nhiều thao tác mạnh mẽ liên quan đến xử lý và tổ chức dữ liệu chuỗi.

1. Set và Chuỗi Ký Tự (set<string>)

Khi sử dụng set để lưu trữ string, bạn đang tạo ra một tập hợp các chuỗi ký tự duy nhất. Set sẽ tự động sắp xếp các chuỗi này theo thứ tự từ điển (lexicographical order). Điều này cực kỳ hữu ích khi bạn cần lọc ra các chuỗi độc nhất từ một danh sách có thể chứa các chuỗi lặp lại, hoặc khi bạn cần kiểm tra sự tồn tại của một chuỗi một cách nhanh chóng.

Hãy xem một ví dụ đơn giản: Lấy ra danh sách các tên duy nhất từ một tập hợp tên.

#include <iostream>
#include <string>
#include <set>
#include <vector> // Chỉ để lưu trữ dữ liệu ban đầu

int main() {
    // Danh sách các tên có thể lặp lại
    vector<string> danh_sach_ten = {
        "Alice", "Bob", "Charlie", "Alice", "David", "Bob", "Eve"
    };

    // Sử dụng set để lưu trữ các tên duy nhất
    set<string> ten_duy_nhat;

    cout << "Danh sach ten ban dau: ";
    for (const auto& ten : danh_sach_ten) {
        cout << ten << " ";
        // Them ten vao set. Set se tu dong xu ly cac ten trung lap
        ten_duy_nhat.insert(ten);
    }
    cout << endl;

    cout << "\nCac ten duy nhat (da sap xep):" << endl;
    // Duyet qua set. Cac ten da duoc luu tru duy nhat va co thu tu
    for (const auto& ten : ten_duy_nhat) {
        cout << ten << endl;
    }

    // Kiem tra su ton tai cua mot ten
    string ten_can_tim = "Charlie";
    if (ten_duy_nhat.count(ten_can_tim)) { // count() tra ve 1 neu co, 0 neu khong
        cout << "\nTen \"" << ten_can_tim << "\" CO ton tai trong danh sach duy nhat." << endl;
    } else {
        cout << "\nTen \"" << ten_can_tim << "\" KHONG ton tai trong danh sach duy nhat." << endl;
    }

    ten_can_tim = "Frank";
    if (ten_duy_nhat.find(ten_can_tim) != ten_duy_nhat.end()) { // find() tra ve iterator den phan tu hoac .end() neu khong tim thay
         cout << "Ten \"" << ten_can_tim << "\" CO ton tai trong danh sach duy nhat." << endl;
    } else {
        cout << "Ten \"" << ten_can_tim << "\" KHONG ton tai trong danh sach duy nhat." << endl;
    }

    return 0;
}

Giải thích:

  • Chúng ta khai báo một set<string> tên là ten_duy_nhat.
  • Khi chúng ta sử dụng insert() để thêm các chuỗi từ danh_sach_ten vào ten_duy_nhat, set sẽ tự động bỏ qua các chuỗi đã tồn tại. Kết quả là set chỉ chứa các chuỗi độc nhất.
  • Khi duyệt qua set (bằng vòng lặp for dựa trên range), các chuỗi được in ra theo thứ tự từ điển: Alice, Bob, Charlie, David, Eve.
  • Các phương thức như count() hoặc find() cho phép kiểm tra sự tồn tại của một chuỗi trong set một cách rất hiệu quả (thường là độ phức tạp O(log n), với n là số phần tử trong set).

Đây là một cách đơn giản và hiệu quả để loại bỏ các bản sao và duy trì một tập hợp các chuỗi độc nhất được sắp xếp.

2. Map và Chuỗi Ký Tự (map<string, ...>)

map là nơi mà string tỏa sáng với vai trò làm khóa. Khi string là khóa, bạn có thể tạo ra các mối liên kết giữa một chuỗi (khóa) và một giá trị bất kỳ (số nguyên, số thực, một chuỗi khác, hoặc thậm chí là một cấu trúc dữ liệu khác). Map cũng tự động sắp xếp các khóa chuỗi theo thứ tự từ điển.

Một trong những ứng dụng phổ biến nhất của map<string, int> là đếm tần suất xuất hiện của các chuỗi.

2.1. Đếm tần suất từ

Hãy lấy ví dụ về việc đếm số lần xuất hiện của mỗi từ trong một câu.

#include <iostream>
#include <string>
#include <map>
#include <sstream> // De tach tu
#include <algorithm> // De chuyen thanh chu thuong

int main() {
    string cau = "Lap trinh C++ that tuyet voi. C++ la ngon ngu manh me va linh hoat.";

    // map de luu tru tan suat xuat hien cua moi tu
    map<string, int> tan_suat_tu;

    // Sử dụng stringstream để tách các từ
    stringstream ss(cau);
    string tu;

    while (ss >> tu) {
        // Co the xu ly tu truoc khi dem (vd: chuyen thanh chu thuong, loai bo dau cau)
        // Don gian hoa: chuyen tu thanh chu thuong
        transform(tu.begin(), tu.end(), tu.begin(), ::tolower);

        // Them tu vao map hoac tang bien dem
        // Neu tu chua co, no se duoc them vao voi gia tri mac dinh la 0, sau do tang len 1
        // Neu tu da co, gia tri cua no se duoc tang len 1
        tan_suat_tu[tu]++; 
    }

    cout << "Tan suat xuat hien cua cac tu trong cau:" << endl;
    // Duyet qua map. Cac khoa (tu) da duoc sap xep theo thu tu tu dien
    for (const auto& pair : tan_suat_tu) {
        cout << "\"" << pair.first << "\": " << pair.second << endl;
    }

    return 0;
}

Giải thích:

  • Chúng ta khai báo một map<string, int> tên là tan_suat_tu. Khóa là string (từ), giá trị là int (số lần xuất hiện).
  • Sử dụng stringstream là một cách thanh lịch để tách câu thành từng từ.
  • Vòng lặp while (ss >> tu) đọc từng từ một.
  • transform được dùng để chuyển mỗi từ thành chữ thường, giúp đếm "C++" và "c++" là một. (Đây là một bước xử lý đơn giản, thực tế có thể phức tạp hơn như loại bỏ dấu câu).
  • Phép toán tan_suat_tu[tu]++ là điểm mấu chốt:
    • Nếu tu chưa tồn tại làm khóa trong map, nó sẽ được thêm vào map với giá trị int mặc định là 0, sau đó ++ sẽ tăng giá trị đó lên 1.
    • Nếu tu đã tồn tại, nó sẽ truy cập đến giá trị hiện tại của khóa đó và tăng giá trị đó lên 1.
  • Khi duyệt qua map, các cặp khóa-giá trị được in ra. Các từ (khóa) được sắp xếp theo thứ tự từ điển.

Kết quả sẽ cho bạn biết mỗi từ xuất hiện bao nhiêu lần trong câu. Đây là cơ sở cho nhiều ứng dụng xử lý ngôn ngữ tự nhiên đơn giản.

2.2. Lưu trữ thông tin liên kết với chuỗi

Bạn cũng có thể dùng map để lưu trữ các thông tin khác liên kết với một chuỗi. Ví dụ, lưu trữ điểm của học sinh dựa trên tên, hoặc lưu trữ định nghĩa của một từ.

#include <iostream>
#include <string>
#include <map>

int main() {
    // map luu tru diem cua hoc sinh (Ten -> Diem)
    map<string, double> diem_hoc_sinh;

    diem_hoc_sinh["Alice"] = 8.5;
    diem_hoc_sinh["Bob"] = 7.0;
    diem_hoc_sinh["Charlie"] = 9.2;
    diem_hoc_sinh["Bob"] = 7.5; // Cap nhat diem cho Bob

    cout << "Danh sach diem hoc sinh (theo ten da sap xep):" << endl;
    for (const auto& pair : diem_hoc_sinh) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // Tra cuu diem cua mot hoc sinh
    string ten_can_tra_cuu = "Charlie";
    if (diem_hoc_sinh.count(ten_can_tra_cuu)) {
        cout << "\nDiem cua " << ten_can_tra_cuu << " la: " << diem_hoc_sinh[ten_can_tra_cuu] << endl;
    } else {
        cout << "\nKhong tim thay hoc sinh co ten " << ten_can_tra_cuu << endl;
    }

    ten_can_tra_cuu = "David";
     if (diem_hoc_sinh.find(ten_can_tra_cuu) != diem_hoc_sinh.end()) {
        cout << "Diem cua " << ten_can_tra_cuu << " la: " << diem_hoc_sinh[ten_can_tra_cuu] << endl;
    } else {
        cout << "Khong tim thay hoc sinh co ten " << ten_can_tra_cuu << endl;
    }

    return 0;
}

Giải thích:

  • Ở đây, map<string, double> lưu trữ tên học sinh (khóa string) và điểm của họ (giá trị double).
  • Chúng ta thêm các cặp khóa-giá trị mới hoặc cập nhật giá trị cho khóa đã tồn tại bằng cách sử dụng [] hoặc insert.
  • Map tự động duy trì thứ tự dựa trên tên học sinh (khóa).
  • Việc tra cứu điểm của một học sinh dựa vào tên là rất nhanh chóng.

3. Kết hợp linh hoạt hơn

Sức mạnh của set và map không chỉ dừng lại ở việc sử dụng chúng độc lập với chuỗi, mà còn ở khả năng kết hợp chúng hoặc lồng ghép chúng. Ví dụ, bạn có thể có một map mà giá trị của nó là một set hoặc một vector chứa các chuỗi.

Ví dụ: Lưu trữ danh sách các con phố theo từng thành phố.

#include <iostream>
#include <string>
#include <map>
#include <vector> // Gia tri la vector cac chuoi
#include <algorithm> // De sap xep vector

int main() {
    // map luu tru danh sach cac con pho theo thanh pho (Thanh pho -> Danh sach pho)
    map<string, vector<string>> pho_theo_thanh_pho;

    // Them du lieu
    pho_theo_thanh_pho["Hanoi"].push_back("Hoan Kiem");
    pho_theo_thanh_pho["Hanoi"].push_back("Ba Dinh");
    pho_theo_thanh_pho["Saigon"].push_back("Nguyen Hue");
    pho_theo_thanh_pho["Hanoi"].push_back("Tay Ho");
    pho_theo_thanh_pho["Saigon"].push_back("Dong Khoi");

    // Duyet va in ra
    cout << "Danh sach pho theo thanh pho:" << endl;
    for (auto& pair : pho_theo_thanh_pho) { // Su dung auto& de co the chinh sua vector (neu can)
        cout << pair.first << ":" << endl;

        // Tuy chon: Sap xep danh sach pho trong moi thanh pho truoc khi in
        sort(pair.second.begin(), pair.second.end());

        for (const auto& pho : pair.second) {
            cout << "  - " << pho << endl;
        }
    }

    return 0;
}

Giải thích:

  • Ở đây, chúng ta dùng map<string, vector<string>>. Khóa là tên thành phố (string), giá trị là một vector<string> chứa tên các con phố.
  • Chúng ta dễ dàng thêm tên phố vào vector tương ứng với mỗi thành phố. Nếu thành phố chưa có trong map, nó sẽ được thêm vào cùng với một vector rỗng ban đầu.
  • Khi duyệt map, các thành phố (khóa) được sắp xếp. Bên trong mỗi thành phố, chúng ta có thể duyệt qua vector các con phố. Thậm chí có thể sắp xếp vector các con phố để hiển thị gọn gàng hơn.

Việc kết hợp này cho phép bạn xây dựng các cấu trúc dữ liệu phức tạp hơn để mô hình hóa các mối quan hệ dữ liệu trong thế giới thực, nơi chuỗi ký tự đóng vai trò là các định danh hoặc phân loại.

Tại sao việc kết hợp này lại quan trọng?

  • Hiệu quả: set và map cung cấp các thao tác tìm kiếm, chèn, xóa với độ phức tạp thời gian logarithmic (O(log n)), nhanh hơn nhiều so với duyệt tuần tự một danh sách lớn (O(n)). Khi làm việc với số lượng lớn chuỗi, sự khác biệt này là đáng kể.
  • Tính duy nhất và sắp xếp: set tự động đảm bảo tính duy nhất và sắp xếp, giúp bạn tránh trùng lặp và dễ dàng trình bày dữ liệu theo thứ tự. map cũng duy trì thứ tự khóa, giúp bạn truy cập dữ liệu theo một cấu trúc logic.
  • Tổ chức dữ liệu: map là một công cụ mạnh mẽ để liên kết các chuỗi với dữ liệu khác, giúp tổ chức thông tin một cách rõ ràng và dễ quản lý.
  • Giải quyết vấn đề thực tế: Rất nhiều bài toán thực tế liên quan đến xử lý văn bản, phân tích dữ liệu, xây dựng từ điển, quản lý thông tin... đều cần đến khả năng làm việc hiệu quả với các chuỗi độc nhất hoặc các cặp chuỗi-dữ liệu.

Kết hợp string với set và map không chỉ là một kỹ thuật lập trình, mà là một cách mạnh mẽ để tiếp cận và giải quyết nhiều vấn đề phức tạp trong lập trình C++. Nắm vững cách sử dụng chúng cùng nhau sẽ là một bước tiến lớn trên con đường trở thành lập trình viên C++ xuất sắc.

Bài tập ví dụ: C++ Bài 16.B1: Thời tiết mùa hè

Thời tiết mùa hè

Đề bài

FullHouse Dev thích uống lassi xoài khi trời nóng, và chỉ khi trời nóng. Nếu (và chỉ nếu) nhiệt độ trong một ngày nhất định cao hơn 35 độ, FullHouse Dev sẽ uống lassi xoài.

FullHouse Dev thấy rằng nhiệt độ hôm nay là X độ Celsius. Anh ấy có uống lassi xoài hôm nay không?

In ra "YES" nếu anh ấy sẽ uống, và "NO" nếu không (không có dấu ngoặc kép).

Input

  • Dòng đầu tiên chứa một số nguyên T - số lượng test case.
  • T dòng tiếp theo, mỗi dòng chứa một số nguyên X, biểu thị nhiệt độ của ngày hôm đó.

Output

Với mỗi test case, in ra "YES" nếu FullHouse Dev sẽ uống lassi xoài ngày hôm đó, và "NO" nếu không (không có dấu ngoặc kép).

Constraints

  • 1 ≤ T ≤ 1000
  • 1 ≤ X ≤ 50

Sample

Input Output
2
35 NO
38 YES

Giải thích

  • Test case 1: Nhiệt độ hôm nay là 35, không cao hơn 35 độ Celsius. Vì vậy, FullHouse Dev sẽ không uống lassi xoài hôm nay.
  • Test case 2: Nhiệt độ hôm nay là 38, cao hơn 35 độ Celsius. Vì vậy, FullHouse Dev sẽ uống lassi xoài hôm nay. Tuyệt vời! Đây là hướng dẫn giải bài tập này bằng C++ một cách ngắn gọn và sử dụng các thành phần chuẩn của C++.

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

  1. Điều kiện uống Lassi: FullHouse Dev chỉ uống lassi khi nhiệt độ cao hơn 35 độ C. Lưu ý từ "cao hơn" (strict inequality >), không phải "lớn hơn hoặc bằng".
  2. Input: Bạn sẽ nhận một số lượng test case T, sau đó là T dòng, mỗi dòng chứa một nhiệt độ X.
  3. Output: Với mỗi nhiệt độ X, bạn cần in ra "YES" hoặc "NO" trên một dòng riêng biệt.
  4. Ràng buộc: T và X nằm trong phạm vi nhỏ, không cần lo lắng về hiệu suất quá mức.

Hướng dẫn giải:

  1. Thư viện cần thiết: Để đọc input và ghi output, bạn cần bao gồm thư viện iostream.
  2. Xử lý nhiều Test Case: Đọc số lượng test case T. Sau đó, sử dụng một vòng lặp (ví dụ while hoặc for) chạy đúng T lần.
  3. Trong mỗi Test Case:
    • Đọc giá trị nhiệt độ X.
    • Kiểm tra điều kiện: nếu X lớn hơn 35.
    • Nếu điều kiện đúng (X > 35), in ra "YES".
    • Nếu điều kiện sai (nghĩa là X <= 35), in ra "NO".
  4. Output: Đảm bảo sau mỗi lần in "YES" hoặc "NO", bạn in kèm ký tự xuống dòng (\n hoặc endl) để kết quả của mỗi test case nằm trên một dòng riêng biệt.
  5. Tối ưu (tùy chọn nhưng nên dùng trong lập trình thi đấu): Để tăng tốc độ đọc ghi, bạn có thể thêm hai dòng sau ở đầu hàm main:
    ios_base::sync_with_stdio(false);
cin.tie(NULL);
    Điều này giúp tách biệt luồng nhập/xuất của C++ với C stdio và không đồng bộ cin với cout.

Cách triển khai logic kiểm tra:

  • Cách thông thường là sử dụng câu lệnh if-else.
  • Cách ngắn gọn hơn (phù hợp với yêu cầu "short code") là sử dụng toán tử điều kiện bậc ba (?:). Biểu thức (condition ? value_if_true : value_if_false) có thể được đưa trực tiếp vào cout.

Hãy áp dụng các bước này để viết chương trình của bạn. Bạn chỉ cần tập trung vào việc đọc input T, tạo vòng lặp T lần, bên trong vòng lặp đọc X, so sánh X với 35, và in kết quả tương ứng cùng với ký tự xuống dò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.