std::map và std::unordered_map

std::map và std::unordered_map lưu trữ dữ liệu dưới dạng cặp khóa-giá trị (key-value), tương tự khái niệm dictionary trong nhiều ngôn ngữ - cho phép tra cứu giá trị nhanh chóng thông qua khóa thay vì chỉ số.

std::map: có thứ tự theo khóa

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

int main() {
    std::map<std::string, int> ages;

    ages["Alice"] = 25; // Thêm hoặc cập nhật một cặp khóa-giá trị
    ages["Bob"] = 30;
    ages["Charlie"] = 22;

    std::cout << ages["Alice"] << std::endl; // 25

    return 0;
}

std::map tự động sắp xếp các phần tử theo thứ tự của khóa (dùng cây nhị phân tìm kiếm cân bằng bên dưới):

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> ages = {{"Charlie", 22}, {"Alice", 25}, {"Bob", 30}};

    for (const auto& [name, age] : ages) { // Structured bindings (C++17)
        std::cout << name << ": " << age << std::endl;
    }
    // Alice: 25
    // Bob: 30
    // Charlie: 22
    // (Luôn theo thứ tự alphabet của khóa, dù thứ tự khởi tạo khác)

    return 0;
}

Kiểm tra khóa có tồn tại không

Truy cập một khóa không tồn tại bằng [] sẽ tự động tạo khóa đó với giá trị mặc định - đây là một cạm bẫy phổ biến. Dùng .find() hoặc .count() để kiểm tra an toàn:

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> ages = {{"Alice", 25}};

    // Cách kiểm tra AN TOÀN
    if (ages.find("Bob") != ages.end()) {
        std::cout << "Bob co trong map" << std::endl;
    } else {
        std::cout << "Bob khong co trong map" << std::endl;
    }

    if (ages.count("Alice") > 0) {
        std::cout << "Alice co trong map" << std::endl;
    }

    // ages["Bob"]; // NGUY HIỂM nếu chỉ để kiểm tra! Sẽ tự động tạo "Bob": 0

    return 0;
}

Xóa phần tử

std::map<std::string, int> ages = {{"Alice", 25}, {"Bob", 30}};
ages.erase("Alice");
std::cout << ages.size() << std::endl; // 1

std::unordered_map: nhanh hơn, không có thứ tự

std::unordered_map dùng bảng băm (hash table) thay vì cây nhị phân, cho tốc độ tra cứu trung bình nhanh hơn (O(1) so với O(log n) của map), nhưng không đảm bảo thứ tự của các phần tử:

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> scores;
    scores["Alice"] = 90;
    scores["Bob"] = 85;

    std::cout << scores["Alice"] << std::endl; // 90

    // Thứ tự khi duyệt KHÔNG đảm bảo giống thứ tự thêm vào

    return 0;
}

Khi nào dùng map, khi nào dùng unordered_map?

	std::map	std::unordered_map
Cấu trúc bên dưới	Cây nhị phân cân bằng	Bảng băm (hash table)
Thứ tự phần tử	Tự động theo khóa	Không đảm bảo
Tốc độ tra cứu	O(log n)	O(1) trung bình
Khi nào dùng	Cần duyệt theo thứ tự	Chỉ cần tra cứu nhanh, không quan tâm thứ tự

Trong đa số trường hợp chỉ cần tra cứu nhanh, unordered_map là lựa chọn phù hợp hơn; chọn map khi thứ tự của khóa thực sự quan trọng với bài toán.

Tổng kết

• map/unordered_map lưu dữ liệu dạng cặp khóa-giá trị, tra cứu thông qua khóa
• Dùng .find() hoặc .count() để kiểm tra khóa tồn tại an toàn - tránh dùng [] chỉ để kiểm tra
• map có thứ tự theo khóa nhưng chậm hơn; unordered_map nhanh hơn nhưng không đảm bảo thứ tự
• Structured bindings (for (const auto& [key, value] : map)) là cách hiện đại để duyệt qua các cặp khóa-giá trị