Bài 20.5: Bài tập thực hành kết hợp Set và Map trong C++

Trong C++, Thư viện Chuẩn (STL) cung cấp cho chúng ta những công cụ mạnh mẽ để quản lý và thao tác dữ liệu. Hai trong số những container phổ biến và cực kỳ hữu ích là set và map. set giúp lưu trữ các phần tử duy nhất theo thứ tự, trong khi map cho phép lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị (key-value), cũng được sắp xếp theo khóa.

Mặc dù mạnh mẽ khi đứng độc lập, sức mạnh thực sự của chúng đôi khi bộc lộ khi chúng ta kết hợp chúng để giải quyết các vấn đề phức tạp hơn. Bài viết này sẽ đi sâu vào một số bài tập thực hành, nơi việc sử dụng cả set và map một cách khéo léo sẽ mang lại hiệu quả và sự thanh lịch cho mã nguồn của bạn.

Chúng ta sẽ cùng nhau xem xét các tình huống cụ thể và cách bộ đôi set và map có thể hoạt động song hành như thế nào nhé!

Tình huống 1: Đếm Tần Suất Các Từ Duy Nhất

Hãy tưởng tượng bạn có một đoạn văn bản và muốn tìm ra tất cả các từ duy nhất xuất hiện trong đó, đồng thời đếm xem mỗi từ duy nhất đó xuất hiện bao nhiêu lần.

Đây là một bài toán cổ điển, và set cùng map chính là "cặp bài trùng" lý tưởng:

  • set sẽ giúp chúng ta dễ dàng trích xuất danh sách các từ duy nhất mà không cần lo lắng về việc trùng lặp.
  • map sẽ lưu trữ mỗi từ duy nhất (lấy từ set) làm khóa, và số lần xuất hiện của nó làm giá trị.

Chúng ta có thể thực hiện điều này bằng cách duyệt qua văn bản, trích xuất từng từ. Mỗi từ trích xuất được sẽ được dùng để cập nhật cả set (đảm bảo từ đó có trong danh sách duy nhất) và map (tăng bộ đếm cho từ đó).

Dưới đây là ví dụ minh họa:

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

int main() {
    string t = "hello world hello C++ programming world";
    map<string, int> tanSuat;
    stringstream s(t);
    string tu;

    while (s >> tu) {
        tanSuat[tu]++;
    }

    cout << "Tan suat cac tu duy nhat:" << endl;
    for (auto const& p : tanSuat) {
        cout << "'" << p.first << "': " << p.second << endl;
    }

    return 0;
}

Output:

Tan suat cac tu duy nhat:
'C++': 1
'hello': 2
'programming': 1
'world': 2

Giải thích:

  1. Chúng ta sử dụng stringstream để dễ dàng "tách" văn bản thành từng từ dựa trên khoảng trắng.
  2. Một map<string, int> tên wordFrequency được tạo ra. Khóa là từ (string), giá trị là số lần xuất hiện (int).
  3. Vòng lặp while (ss >> word) đọc từng từ một.
  4. Với mỗi từ đọc được, chúng ta truy cập wordFrequency[word].
    • Nếu word chưa tồn tại làm khóa trong map, map sẽ tự động tạo một mục mới với word làm khóa và giá trị khởi tạo mặc định cho int là 0.
    • Sau đó, toán tử ++ sẽ tăng giá trị này lên 1.
    • Nếu word đã tồn tại, toán tử [] chỉ đơn giản là trả về tham chiếu đến giá trị hiện có, và ++ tăng giá trị đó lên.
  5. Sau khi duyệt hết văn bản, wordFrequency chứa tần suất của tất cả các từ duy nhất.
  6. Vòng lặp cuối cùng duyệt qua map và in ra từng cặp khóa-giá trị.

Lưu ý: Mặc dù ví dụ này chỉ dùng map để giữ cho code ngắn gọn, nếu yêu cầu bài toán là trước hết lấy danh sách các từ duy nhất, sau đó mới đếm tần suất, thì việc dùng set để thu thập từ duy nhất trước, rồi dùng danh sách từ unique đó để đi qua văn bản lần nữa đếm với map cũng là một cách tiếp cận hợp lý, tùy thuộc vào yêu cầu cụ thể.

Tình huống 2: Quản Lý Danh Sách Học Phần Duy Nhất Cho Từng Sinh Viên

Giả sử bạn có dữ liệu về việc đăng ký học phần của sinh viên, nơi mỗi dòng ghi lại một sinh viên đăng ký một học phần nào đó. Một sinh viên có thể đăng ký nhiều học phần, và dữ liệu có thể có các dòng trùng lặp (ví dụ: báo cáo đăng ký nhiều lần cho cùng một sinh viên và học phần). Bạn muốn tạo một cấu trúc dữ liệu cho phép bạn nhanh chóng tra cứu một sinh viên và xem danh sách duy nhất các học phần mà họ đã đăng ký.

Ở đây, chúng ta cần ánh xạ từ tên sinh viên tới một tập hợp các học phần.

  • map rất phù hợp để ánh xạ tên sinh viên (khóa) tới thông tin của họ.
  • Thông tin cần lưu trữ cho mỗi sinh viên là một danh sách các học phần duy nhất. set chính là lựa chọn hoàn hảo cho điều này!

Vì vậy, cấu trúc dữ liệu lý tưởng ở đây sẽ là một map<string, set<string>>, trong đó khóa là tên sinh viên và giá trị là một set chứa tên các học phần mà sinh viên đó đăng ký.

Xem ví dụ:

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

int main() {
    vector<pair<string, string>> dky = {
        {"Alice", "Toan A1"},
        {"Bob", "Vat Ly 1"},
        {"Alice", "Lap Trinh C++"},
        {"Charlie", "Toan A1"},
        {"Bob", "Lap Trinh C++"},
        {"Alice", "Toan A1"},
        {"Alice", "Dai So Tuyen Tinh"},
        {"Bob", "Vat Ly 1"}
    };

    map<string, set<string>> svHocPhan;

    for (auto const& dk : dky) {
        string const& sv = dk.first;
        string const& hp = dk.second;
        svHocPhan[sv].insert(hp);
    }

    cout << "Danh sach hoc phan duy nhat cho tung sinh vien:" << endl;
    for (auto const& p : svHocPhan) {
        string const& tenSv = p.first;
        set<string> const& dsHp = p.second;

        cout << "Sinh vien: " << tenSv << endl;
        cout << "  Hoc phan: ";
        for (string const& h : dsHp) {
            cout << h << ", ";
        }
        cout << endl;
    }

    return 0;
}

Output:

Danh sach hoc phan duy nhat cho tung sinh vien:
Sinh vien: Alice
  Hoc phan: Dai So Tuyen Tinh, Lap Trinh C++, Toan A1, 
Sinh vien: Bob
  Hoc phan: Lap Trinh C++, Vat Ly 1, 
Sinh vien: Charlie
  Hoc phan: Toan A1,

Giải thích:

  1. Chúng ta sử dụng map<string, set<string>> có tên studentCourses. Khóa của map là tên sinh viên (string), và giá trị là một set<string> chứa các học phần của sinh viên đó.
  2. Chúng ta duyệt qua vector registrations chứa dữ liệu thô.
  3. Đối với mỗi cặp {studentName, courseName}, chúng ta truy cập studentCourses[studentName].
    • Giống như ví dụ trước, nếu studentName chưa có trong map, một entry mới sẽ được tạo, và giá trị tương ứng là một set<string> rỗng.
    • Sau đó, chúng ta gọi .insert(courseName) trên cái set này. Đặc tính của set là chỉ lưu trữ các phần tử duy nhất, nên nếu courseName đã tồn tại trong set của sinh viên đó, thao tác insert sẽ không làm gì cả. Ngược lại, nó sẽ thêm courseName vào set.
  4. Kết quả là studentCourses chứa mỗi sinh viên một lần, và set liên kết với mỗi sinh viên chỉ chứa danh sách các học phần duy nhất mà họ đã đăng ký.
  5. Vòng lặp cuối cùng duyệt qua studentCourses, in tên sinh viên và sau đó duyệt qua set các học phần của họ để in ra.

Ví dụ này minh họa rõ ràng cách sử dụng set bên trong map để quản lý các tập hợp dữ liệu duy nhất được nhóm theo một khóa nào đó.

Tình huống 3: Lọc Dữ Liệu Duy Nhất Dựa Trên Thuộc Tính

Giả sử bạn có một danh sách các sản phẩm, mỗi sản phẩm có tên và giá. Danh sách này có thể chứa các sản phẩm trùng tên nhưng có giá khác nhau (ví dụ: cùng một tên sản phẩm nhưng từ các cửa hàng khác nhau hoặc có chương trình khuyến mãi khác nhau). Bạn muốn lấy danh sách các tên sản phẩm duy nhất và hiển thị giá mới nhất (hoặc giá bất kỳ từ lần xuất hiện cuối cùng trong danh sách ban đầu) của chúng.

  • set có thể giúp chúng ta thu thập các tên sản phẩm duy nhất.
  • map có thể lưu trữ tên sản phẩm (khóa) và giá tương ứng (giá trị). Khi gặp một tên sản phẩm đã có trong map, chúng ta có thể chọn cập nhật giá (ví dụ: giá mới nhất) hoặc giữ giá cũ tùy logic bài toán. Ở đây, ta sẽ giả sử giá cuối cùng trong danh sách là giá cần lưu.

Cách làm: Duyệt qua danh sách sản phẩm. Với mỗi sản phẩm, thêm tên vào set và thêm (hoặc cập nhật) tên và giá vào map. Sau đó, duyệt qua set các tên sản phẩm duy nhất và dùng tên này làm khóa để tra cứu giá trong map.

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

struct Product {
    string name;
    double price;
};

int main() {
    vector<Product> sp = {
        {"Laptop", 1200.0},
        {"Keyboard", 75.0},
        {"Laptop", 1150.0},
        {"Mouse", 25.0},
        {"Keyboard", 80.0},
        {"Monitor", 300.0},
        {"Mouse", 20.0}
    };

    set<string> tenSP;
    map<string, double> giaSP;

    for (auto const& s : sp) {
        tenSP.insert(s.name);
        giaSP[s.name] = s.price;
    }

    cout << "Danh sach san pham duy nhat va gia cua chung:" << endl;
    for (string const& t : tenSP) {
        double gia = giaSP[t];
        cout << " - " << t << ": $" << gia << endl;
    }

    return 0;
}

Output:

Danh sach san pham duy nhat va gia cua chung:
 - Keyboard: $80
 - Laptop: $1150
 - Monitor: $300
 - Mouse: $20

Giải thích:

  1. Chúng ta định nghĩa một struct Product để lưu trữ tên và giá.
  2. Chúng ta sử dụng một set<string> tên uniqueProductNames để lưu trữ các tên sản phẩm duy nhất.
  3. Chúng ta sử dụng một map<string, double> tên productPrices để lưu trữ ánh xạ từ tên sản phẩm sang giá của nó.
  4. Chúng ta duyệt qua vector allProducts.
  5. Với mỗi product:
    • uniqueProductNames.insert(product.name): Tên sản phẩm được thêm vào set. set tự động đảm bảo rằng mỗi tên chỉ xuất hiện một lần.
    • productPrices[product.name] = product.price;: Tên sản phẩm được sử dụng làm khóa để lưu giá vào map. Nếu khóa đã tồn tại, giá trị cũ sẽ bị ghi đè bởi giá mới (product.price). Điều này đạt được yêu cầu "giá mới nhất" (nếu danh sách đầu vào được sắp xếp theo thời gian) hoặc đơn giản là giá từ lần xuất hiện cuối cùng của tên sản phẩm đó trong danh sách đầu vào.
  6. Sau khi xử lý tất cả sản phẩm, uniqueProductNames chứa danh sách tên duy nhất, và productPrices chứa giá tương ứng (theo logic ghi đè) cho mỗi tên sản phẩm duy nhất đó.
  7. Vòng lặp cuối cùng duyệt qua uniqueProductNames (đảm bảo chúng ta chỉ xử lý các tên duy nhất) và sử dụng tên đó làm khóa để lấy giá từ productPrices và in ra.

Bài tập này cho thấy cách chúng ta có thể dùng set để kiểm soát sự duy nhất của một thuộc tính (tên sản phẩm), trong khi dùng map để lưu trữ một thuộc tính khác liên quan (giá), và cách duyệt qua set có thể làm "bộ lọc" hoặc danh sách điều khiển cho việc truy xuất dữ liệu từ map.

Tình huống 4: Thống Kê Số Lượng Khách Truy Cập Duy Nhất Cho Từng Trang Web

Bạn có một tệp log ghi lại các lượt truy cập vào website, mỗi dòng chứa thông tin về trang web được truy cập và ID của khách truy cập. Dữ liệu có thể có nhiều dòng cho cùng một khách truy cập vào cùng một trang hoặc các trang khác nhau. Bạn muốn thống kê xem mỗi trang web có bao nhiêu khách truy cập duy nhất.

  • Chúng ta cần nhóm dữ liệu theo trang web. Điều này gợi ý sử dụng map với khóa là URL trang web.
  • Với mỗi trang web, chúng ta cần lưu trữ một danh sách các ID khách truy cập duy nhất. Điều này gợi ý sử dụng set để lưu trữ các ID.

Cấu trúc dữ liệu phù hợp sẽ là map<string, set<int>>, trong đó khóa là URL trang web (string) và giá trị là một set chứa các ID khách truy cập duy nhất (set<int>) cho trang đó.

Ví dụ:

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

struct Visit {
    string url;
    int visitorId;
};

int main() {
    vector<Visit> qc = {
        {"/home", 101},
        {"/products", 102},
        {"/home", 103},
        {"/products", 101},
        {"/about", 104},
        {"/home", 101},
        {"/products", 103},
        {"/home", 105},
        {"/about", 102}
    };

    map<string, set<int>> tk;

    for (auto const& v : qc) {
        string const& u = v.url;
        int id = v.visitorId;
        tk[u].insert(id);
    }

    cout << "Thong ke so luong khach truy cap duy nhat cho tung trang:" << endl;
    for (auto const& p : tk) {
        string const& url = p.first;
        set<int> const& dsId = p.second;
        cout << " - Trang '" << url << "': " << dsId.size() << " khach truy cap duy nhat" << endl;
    }

    return 0;
}

Output:

Thong ke so luong khach truy cap duy nhat cho tung trang:
 - Trang '/about': 2 khach truy cap duy nhat
 - Trang '/home': 3 khach truy cap duy nhat
 - Trang '/products': 3 khach truy cap duy nhat

Giải thích:

  1. Chúng ta định nghĩa một struct Visit để lưu URL và ID khách truy cập.
  2. Chúng ta sử dụng map<string, set<int>> tên uniqueVisitorsPerPage. Khóa là URL (string), giá trị là một set<int> chứa ID của khách truy cập.
  3. Chúng ta duyệt qua vector websiteVisits.
  4. Đối với mỗi visit:
    • Chúng ta truy cập uniqueVisitorsPerPage[pageUrl]. Nếu pageUrl chưa có trong map, một entry mới được tạo với giá trị là một set rỗng.
    • insert(visitorId) được gọi trên set này. Nhờ đặc tính của set, visitorId chỉ được thêm vào nếu nó chưa tồn tại trong tập hợp khách truy cập của trang pageUrl đó.
  5. Sau khi xử lý xong tất cả lượt truy cập, uniqueVisitorsPerPage chứa thông tin nhóm theo URL trang web, và mỗi URL liên kết với một set chỉ chứa các ID khách truy cập duy nhất vào trang đó.
  6. Để lấy số lượng khách truy cập duy nhất cho mỗi trang, chúng ta duyệt qua map và sử dụng phương thức .size() trên set liên kết với mỗi URL.

Bài tập này là một ví dụ điển hình về việc sử dụng map để phân loại dữ liệu (theo URL) và set để loại bỏ các giá trị trùng lặp (ID khách truy cập) trong mỗi nhóm.

Lưu Ý Về set, map và Các Phiên Bản Unordered

Trong tất cả các ví dụ trên, chúng ta đã sử dụng set và map, vốn là các container dựa trên cây nhị phân tìm kiếm tự cân bằng (thường là Red-Black Tree). Điều này đảm bảo các phần tử trong set được sắp xếp theo thứ tự tăng dần (hoặc thứ tự tùy chỉnh), và các cặp khóa-giá trị trong map được sắp xếp theo khóa. Thời gian trung bình cho các thao tác như chèn, xóa, tìm kiếm là O(log n), với n là số phần tử.

C++ cũng cung cấp các phiên bản unordered của chúng: unordered_set và unordered_map. Các container này dựa trên bảng băm (hash table). Chúng không duy trì thứ tự của các phần tử hoặc khóa. Tuy nhiên, thời gian trung bình cho các thao tác chèn, xóa, tìm kiếm là O(1), nhanh hơn đáng kể so với O(log n) khi n lớn. Trường hợp xấu nhất có thể là O(n) nếu hàm băm không tốt gây ra nhiều va chạm (collision).

Khi nào nên dùng phiên bản Unordered?

  • Khi bạn không cần dữ liệu được sắp xếp theo thứ tự.
  • Khi hiệu suất trung bình là ưu tiên hàng đầu và bạn có một hàm băm tốt cho kiểu dữ liệu của mình.

Ví dụ, nếu trong Tình huống 1 bạn không cần in ra các từ theo thứ tự alphabet, bạn có thể dùng unordered_map<string, int> để có hiệu suất tốt hơn khi xử lý lượng văn bản rất lớn. Tương tự, trong Tình huống 4, nếu thứ tự của các URL trong kết quả không quan trọng, bạn có thể dùng unordered_map<string, set<int>> hoặc thậm chí unordered_map<string, unordered_set<int>> nếu thứ tự các ID khách truy cập cho mỗi trang cũng không quan trọng và hiệu suất là yếu tố quyết định.

Việc lựa chọn giữa phiên bản có thứ tự (set, map) và không thứ tự (unordered_set, unordered_map) phụ thuộc vào yêu cầu cụ thể của bài toán về thứ tự dữ liệu và hiệu suất cần thiết. Khi kết hợp chúng, sự lựa chọn của một container có thể ảnh hưởng đến cách bạn tương tác với container kia.

Comments

There are no comments at the moment.