Bài 19.1: Khái niệm và sử dụng Map trong C++

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

Bạn đã bao giờ nghĩ về cách lưu trữ thông tin theo kiểu "từ điển" hay "danh bạ điện thoại" chưa? Nơi mà mỗi mục đều có một "tên" duy nhất (key) và tương ứng với nó là một "giá trị" cụ thể (value). Ví dụ, trong danh bạ, tên người là key và số điện thoại là value. Trong từ điển, từ cần tra là key và nghĩa của nó là value.

Trong lập trình, cấu trúc dữ liệu mạnh mẽ giúp chúng ta làm điều này được gọi là Map, Dictionary, hoặc Associative Array. Và trong Thư viện Chuẩn C++ (Standard Template Library - STL), chúng ta có một "ứng cử viên" sáng giá cho nhiệm vụ này: map.

Bài viết này sẽ đưa bạn đi sâu vào thế giới của map, hiểu nó là gì, tại sao nó lại hữu ích, và quan trọng nhất là cách sử dụng nó trong các chương trình C++ của bạn.

`map` là gì?

Đơn giản mà nói, map là một container kết hợp (associative container) lưu trữ các cặp key-value, trong đó mỗi key là duy nhất và được sắp xếp theo thứ tự tăng dần.

Hãy phân tích một chút:

Container kết hợp (Associative Container): Khác với các container tuần tự (sequential) như vector hay list mà bạn truy cập các phần tử bằng vị trí (index), map cho phép bạn truy cập các phần tử dựa trên key của chúng.
Cặp Key-Value: Mỗi phần tử trong map là một cặp gồm một key và một value đi kèm. Key dùng để định danh phần tử đó, còn value là dữ liệu mà bạn muốn lưu trữ tương ứng với key đó.
Key Duy nhất: Mỗi key trong một map chỉ xuất hiện một lần duy nhất. Nếu bạn cố gắng chèn một phần tử có key đã tồn tại, thao tác chèn sẽ bị bỏ qua (nếu dùng insert) hoặc giá trị cũ sẽ bị ghi đè (nếu dùng toán tử []).
Sắp xếp theo Key: Các phần tử trong map luôn được giữ ở trạng thái được sắp xếp theo thứ tự của key. Mặc định, map sử dụng toán tử < của kiểu key để sắp xếp theo thứ tự tăng dần.

Bên trong "cỗ máy": Thông thường, map được triển khai dựa trên cấu trúc dữ liệu cây tìm kiếm nhị phân cân bằng (như Red-Black Tree). Điều này mang lại hiệu quả cao cho các thao tác tìm kiếm, chèn và xóa (thường là O(log n), với n là số phần tử).

Tại sao nên sử dụng `map`?

map là lựa chọn tuyệt vời khi bạn cần:

Tìm kiếm nhanh theo Key: Khi bạn cần truy xuất một giá trị cực nhanh dựa trên một mã định danh (key) duy nhất.
Lưu trữ dữ liệu Key-Value: Khi dữ liệu của bạn có cấu trúc tự nhiên dạng cặp key-value.
Đảm bảo Key là Duy nhất: Map tự động xử lý việc chỉ cho phép mỗi key xuất hiện một lần.
Dữ liệu được Sắp xếp: Khi bạn cần duyệt qua các phần tử theo thứ tự được sắp xếp của key.

Khi nào có thể không dùng map? Nếu bạn không cần dữ liệu được sắp xếp theo key và cần tốc độ truy xuất trung bình nhanh hơn nữa (gần như O(1) trong trường hợp tốt nhất), unordered_map (dựa trên bảng băm - hash table) có thể là lựa chọn tốt hơn. Tuy nhiên, map vẫn là một trong những container phổ biến và mạnh mẽ nhất của STL.

Sử dụng `map`: Các Thao Tác Cơ Bản

Để sử dụng map, bạn cần include header <map>.

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

int main() {
    map<string, int> svTuoi;
    return 0;
}

Cú pháp khai báo cơ bản là map<KiểuKey, KiểuValue> tên_map;.

Bây giờ, hãy khám phá các thao tác phổ biến nhất!

1. Chèn (Inserting) Phần Tử

Có nhiều cách để thêm các cặp key-value vào map:

Sử dụng toán tử []: Đây là cách tiện lợi nhất. Nếu key chưa tồn tại, nó sẽ được chèn vào map cùng với giá trị mặc định của KiểuValue (ví dụ: 0 cho int, chuỗi rỗng cho string), sau đó giá trị bạn gán sẽ được lưu. Nếu key đã tồn tại, giá trị cũ sẽ bị ghi đè.

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

int main() {
    map<string, int> svTuoi;

    svTuoi["Alice"] = 20;
    svTuoi["Bob"] = 22;
    svTuoi["Alice"] = 21; // Alice: 21

    for (auto const& [ten, tuoi] : svTuoi) {
        cout << ten << ": " << tuoi << endl;
    }

    return 0;
}

Output:

Alice: 21
Bob: 22

Sử dụng phương thức insert(): Phương thức insert() không ghi đè nếu key đã tồn tại. Nó sẽ trả về một cặp (pair<iterator, bool>), trong đó bool cho biết liệu việc chèn có diễn ra hay không (true nếu chèn thành công, false nếu key đã tồn tại).

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

int main() {
    map<string, int> svTuoi;

    svTuoi.insert(pair<string, int>("Alice", 20));
    svTuoi.insert({"Bob", 22});

    auto kq = svTuoi.insert({"Alice", 25}); // Thu chen key da ton tai
    if (!kq.second) {
        cout << "Key 'Alice' da ton tai. Khong chen them duoc." << endl;
    }

    for (auto const& [ten, tuoi] : svTuoi) {
        cout << ten << ": " << tuoi << endl;
    }

    return 0;
}

Output:

Key 'Alice' da ton tai. Khong chen them duoc.
Alice: 20
Bob: 22

Giải thích: Cách dùng insert với pair hoặc initializer list là cách rõ ràng cho thấy bạn đang chèn một cặp key-value. Nó cũng an toàn hơn nếu bạn không muốn ghi đè dữ liệu hiện có.

2. Truy cập (Accessing) Giá Trị

Để lấy giá trị tương ứng với một key:

Sử dụng toán tử []: Giống như khi chèn, bạn có thể dùng [] để truy cập. studentAges["Bob"] sẽ trả về giá trị (tuổi) của Bob. Tuy nhiên, cẩn thận! Nếu key không tồn tại, toán tử [] sẽ tự động chèn key đó vào map với một giá trị mặc định, điều này có thể gây ra hành vi không mong muốn.

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 20;
    svTuoi["Bob"] = 22;

    cout << "Tuoi Alice: " << svTuoi["Alice"] << endl;

    // CAN THAN: Key "Charlie" khong ton tai, map se them "Charlie" voi 0
    cout << "Tuoi Charlie (mac dinh 0): " << svTuoi["Charlie"] << endl;
    cout << "So phan tu sau truy cap Charlie: " << svTuoi.size() << endl;

    return 0;
}

Output:

Tuoi Alice: 20
Tuoi Charlie (mac dinh 0): 0
So phan tu sau truy cap Charlie: 3

Sử dụng phương thức at(): Phương thức at() cũng trả về giá trị tương ứng với key, nhưng nếu key không tồn tại, nó sẽ ném ra một ngoại lệ (out_of_range). Cách này an toàn hơn khi bạn mong đợi key phải tồn tại và muốn chương trình báo lỗi nếu không tìm thấy.
```
#include <iostream>
#include <map>
#include <string>

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 20;
    svTuoi["Bob"] = 22;

    try {
        cout << "Tuoi Bob: " << svTuoi.at("Bob") << endl;
        cout << "Tuoi David: " << svTuoi.at("David") << endl; // Bao loi
    } catch (const out_of_range& e) {
        cerr << "Loi: " << e.what() << endl;
    }

    return 0;
}
```
Output:
```
Tuoi Bob: 22
Loi: map::at
```
Giải thích: Chọn at() khi bạn muốn kiểm tra chặt chẽ sự tồn tại của key. Chọn [] khi bạn chắc chắn key tồn tại, hoặc khi bạn muốn chèn mới nếu nó chưa có.

3. Kiểm Tra Sự Tồn Tại của Key

Trước khi truy cập, bạn có thể muốn kiểm tra xem một key có tồn tại trong map hay không:

Sử dụng phương thức count(): Đối với map (với key duy nhất), count(key) sẽ trả về 1 nếu key tồn tại và 0 nếu không.

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 20;
    svTuoi["Bob"] = 22;

    if (svTuoi.count("Alice")) {
        cout << "Alice co trong DS." << endl;
    } else {
        cout << "Alice khong co trong DS." << endl;
    }

    if (svTuoi.count("Charlie")) {
         cout << "Charlie co trong DS." << endl;
    } else {
        cout << "Charlie khong co trong DS." << endl;
    }

    return 0;
}

Output:

Alice co trong DS.
Charlie khong co trong DS.

Sử dụng phương thức find(): Phương thức find(key) sẽ trả về một iterator trỏ đến phần tử nếu tìm thấy, và trả về studentAges.end() nếu không tìm thấy. Cách này hiệu quả hơn nếu bạn cần lấy iterator sau khi kiểm tra sự tồn tại (để truy cập giá trị hoặc xóa phần tử).

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 20;
    svTuoi["Bob"] = 22;

    auto it = svTuoi.find("Bob");
    if (it != svTuoi.end()) {
        cout << "Tim thay Bob! Tuoi: " << it->second << endl;
    } else {
        cout << "Khong tim thay Bob." << endl;
    }

    auto it_c = svTuoi.find("Charlie");
    if (it_c != svTuoi.end()) {
        cout << "Tim thay Charlie!" << endl;
    } else {
        cout << "Khong tim thay Charlie." << endl;
    }

    return 0;
}

Output:

Tim thay Bob! Tuoi: 22
Khong tim thay Charlie.

Giải thích: count() đơn giản và dễ đọc cho mục đích chỉ kiểm tra sự tồn tại. find() linh hoạt hơn khi bạn muốn làm gì đó với phần tử tìm được (ví dụ: in giá trị hoặc xóa).

4. Lặp (Iterating) Qua Map

Bạn có thể duyệt qua tất cả các phần tử trong map. Vì map sắp xếp theo key, việc lặp sẽ duyệt qua các phần tử theo thứ tự key tăng dần. Mỗi phần tử khi lặp là một pair với .first là key và .second là value.

Sử dụng Range-based for loop (C++11 trở lên): Cách hiện đại và gọn gàng.

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Charlie"] = 23;
    svTuoi["Alice"] = 21;
    svTuoi["Bob"] = 22;

    cout << "DS SV va tuoi (sap xep theo ten):" << endl;
    for (const auto& [ten, tuoi] : svTuoi) {
        cout << ten << ": " << tuoi << endl;
    }

    return 0;
}

Output:

DS SV va tuoi (sap xep theo ten):
Alice: 21
Bob: 22
Charlie: 23

Giải thích: auto& pair khai báo pair là một tham chiếu đến cặp key-value hiện tại. Dùng const& để tránh sao chép và đảm bảo không thay đổi map khi duyệt.

Sử dụng Iterator tường minh: Cách truyền thống, cung cấp quyền kiểm soát chi tiết hơn.

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Charlie"] = 23;
    svTuoi["Alice"] = 21;
    svTuoi["Bob"] = 22;

    cout << "DS SV va tuoi (su dung iterator):" << endl;
    for (auto it = svTuoi.begin(); it != svTuoi.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    return 0;
}

Output:

DS SV va tuoi (su dung iterator):
Alice => 21
Bob => 22
Charlie => 23

Giải thích: studentAges.begin() trả về iterator trỏ đến phần tử đầu tiên (theo thứ tự key). studentAges.end() trả về một iterator sau phần tử cuối cùng. Vòng lặp chạy cho đến khi iterator hiện tại bằng end(). *it truy cập cặp key-value, it->first và it->second truy cập thành viên của cặp đó.

5. Xóa (Erasing) Phần Tử

Có nhiều cách để xóa các cặp key-value khỏi map:

Xóa theo Key: Xóa phần tử có key cụ thể.

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 21;
    svTuoi["Bob"] = 22;
    svTuoi["Charlie"] = 23;

    cout << "Map truoc xoa: " << svTuoi.size() << " ptu." << endl;

    size_t slXoa = svTuoi.erase("Bob"); // Xoa "Bob"
    cout << "SL ptu da xoa (Bob): " << slXoa << endl;
    cout << "Map sau xoa Bob: " << svTuoi.size() << " ptu." << endl;

    slXoa = svTuoi.erase("David"); // Xoa key khong ton tai
    cout << "SL ptu da xoa (David): " << slXoa << endl;
    cout << "Map sau xoa David: " << svTuoi.size() << " ptu." << endl;

    return 0;
}

Output:

Map truoc xoa: 3 ptu.
SL ptu da xoa (Bob): 1
Map sau xoa Bob: 2 ptu.
SL ptu da xoa (David): 0
Map sau xoa David: 2 ptu.

Giải thích: erase(key) trả về số lượng phần tử đã bị xóa (đối với map là 1 nếu tìm thấy và xóa, 0 nếu không tìm thấy).

Xóa theo Iterator: Xóa phần tử mà iterator đang trỏ tới. Thường dùng sau khi tìm kiếm bằng find().

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 21;
    svTuoi["Bob"] = 22;
    svTuoi["Charlie"] = 23;

    auto itXoa = svTuoi.find("Alice");
    if (itXoa != svTuoi.end()) {
        svTuoi.erase(itXoa); // Xoa
        cout << "Da xoa Alice." << endl;
    }

    cout << "Map sau xoa Alice:" << endl;
    for (const auto& [ten, tuoi] : svTuoi) {
        cout << ten << ": " << tuoi << endl;
    }

    return 0;
}

Output:

Da xoa Alice.
Map sau xoa Alice:
Bob: 22
Charlie: 23

Giải thích: Xóa theo iterator thường hiệu quả hơn xóa theo key nếu bạn đã có iterator sẵn.

6. Kích thước và Trạng Thái Rỗng

size(): Trả về số lượng phần tử hiện có trong map.

empty(): Trả về true nếu map rỗng (không có phần tử nào), ngược lại trả về false.

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

int main() {
    map<string, int> svTuoi;
    cout << "Map rong? " << (svTuoi.empty() ? "Co" : "Khong") << endl;
    cout << "Kich thuoc: " << svTuoi.size() << endl;

    svTuoi["Alice"] = 20;
    cout << "Map rong sau them? " << (svTuoi.empty() ? "Co" : "Khong") << endl;
    cout << "Kich thuoc sau them: " << svTuoi.size() << endl;

    return 0;
}

Output:

Map rong? Co
Kich thuoc: 0
Map rong sau them? Khong
Kich thuoc sau them: 1

7. Xóa Toàn Bộ Map

Để xóa tất cả các phần tử trong map, sử dụng phương thức clear().

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

int main() {
    map<string, int> svTuoi;
    svTuoi["Alice"] = 21;
    svTuoi["Bob"] = 22;

    cout << "Kich thuoc truoc clear: " << svTuoi.size() << endl;
    svTuoi.clear();
    cout << "Kich thuoc sau clear: " << svTuoi.size() << endl;
    cout << "Map rong sau clear? " << (svTuoi.empty() ? "Co" : "Khong") << endl;

    return 0;
}

Output:

Kich thuoc truoc clear: 2
Kich thuoc sau clear: 0
Map rong sau clear? Co

Một Ví Dụ Thực Tế Hơn: Đếm Tần Suất Từ

Hãy xem một ví dụ nhỏ nhưng khá thực tế về việc sử dụng map để đếm số lần xuất hiện của mỗi từ trong một câu văn.

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

int main() {
    string cau = "this is a test sentence this sentence is a test";
    map<string, int> demTu;

    stringstream ss(cau);
    string tu;

    while (ss >> tu) {
        demTu[tu]++;
    }

    cout << "Tan suat cac tu:" << endl;
    for (const auto& [tu, soLan] : demTu) {
        cout << "'" << tu << "': " << soLan << endl;
    }

    return 0;
}

Output:

Tan suat cac tu:
'a': 2
'is': 2
'sentence': 2
'test': 2
'this': 2

Giải thích:

Chúng ta khai báo một map<string, int> tên là wordCounts. Key là string (từ), Value là int (số lần xuất hiện).
stringstream giúp chúng ta dễ dàng "bóc tách" câu văn thành từng từ một.
Vòng lặp while (ss >> word) đọc từng từ từ stringstream vào biến word.
Dòng wordCounts[word]++; là điểm mấu chốt. Khi word là "this" lần đầu tiên, wordCounts["this"] chưa tồn tại. Toán tử [] sẽ chèn "this" vào map với giá trị mặc định là 0, sau đó ++ tăng giá trị lên 1. Lần thứ hai gặp "this", wordCounts["this"] đã tồn tại với giá trị là 1, và ++ sẽ tăng nó lên 2. Cứ như vậy cho tất cả các từ.
Cuối cùng, chúng ta duyệt qua wordCounts. Vì map sắp xếp theo key (từ), kết quả in ra sẽ theo thứ tự bảng chữ cái của các từ.

Ví dụ này cho thấy sức mạnh và sự tiện lợi của map trong việc quản lý dữ liệu có mối quan hệ key-value và cần đếm tần suất hoặc nhóm dữ liệu.

Comments

There are no comments at the moment.