std::map trong C++: khóa, giá trị, tra cứu và thêm phần tử

Tra cứu theo khóa

vector rất tốt khi bạn truy cập theo vị trí: phần tử 0, phần tử 1, v.v. Nhưng nhiều khi bạn không có vị trí; bạn có một cái tên và muốn lấy thứ gắn với nó: tên người dùng và điểm số, một từ và số lần xuất hiện, mã quốc gia và thủ đô. Quét qua vector để tìm phần tử khớp tốn O(n) và chậm đi rất nhanh.

std::map giải quyết chuyện này. Nó lưu các cặp khóa và giá trị (key-value), giữ chúng được sắp xếp theo khóa, và cho phép tra cứu giá trị theo khóa trong thời gian O(log n). Hãy include <map> để dùng:

#include <iostream>
#include <map>
#include <string>
using namespace std;

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

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> đọc là "một map từ khóa kiểu string sang giá trị kiểu int." Khóa là duy nhất: gán vào cùng một khóa hai lần thì giá trị thứ hai thắng. Bên trong, map là một cây nhị phân tìm kiếm cân bằng, đó là lý do mọi thứ luôn được sắp xếp và tra cứu có độ phức tạp logarit chứ không phải hằng số.

Thêm phần tử

Có vài cách để thêm phần tử, và khác biệt giữa chúng là quan trọng. Cách phổ biến nhất là operator[], tạo khóa nếu chưa có và trả về một tham chiếu để bạn gán giá trị:

#include <iostream>
#include <map>
#include <string>
using namespace std;

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

    inventory["apples"] = 12;     // create + assign
    inventory["apples"] += 3;     // read-modify-write, now 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Nếu bạn muốn thêm phần tử nhưng không ghi đè khóa đã có, hãy dùng insert hoặc emplace. Cả hai đều trả về một pair mà .second là một bool cho biết việc thêm có thực sự diễn ra hay không:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada already exists
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, unchanged
}

Dùng [] khi bạn muốn "lần ghi cuối thắng", và dùng insert/emplace khi khóa đã có cần được giữ nguyên.

Bẫy operator[]: đọc cũng thêm khóa

Đây là bug map phổ biến nhất. operator[] không chỉ đơn thuần đọc: nếu khóa chưa có, nó âm thầm thêm khóa với giá trị khởi tạo mặc định (0 với int, "" với string, v.v.) và trả về tham chiếu tới giá trị đó. Vì vậy chỉ cần kiểm tra một khóa bằng [] là map đã bị thay đổi:

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: this just created "maybe" -> 0
    // ...
}
cout << m.size();        // 1, not 0 - you inserted a key by accident

Lỗi này còn gây khó với const map, khi operator[] thậm chí không biên dịch được vì có thể cần thêm phần tử. Để đọc mà không thêm, hãy dùng find, count/contains, hoặc at (hàm này ném ngoại lệ thay vì thêm khóa khi khóa không tồn tại):

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: returns an iterator, == end() if absent
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) or count (any version)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: throws std::out_of_range if missing - never inserts
    cout << "a = " << m.at("a") << "\n";
}

Quy tắc chung: nếu bạn muốn đọc, đừng bao giờ dùng []. Dùng at khi khóa chắc chắn phải tồn tại, và find/contains khi nó có thể không có.

Duyệt theo thứ tự đã sắp xếp

Vì map được xây dựng trên cây, duyệt nó sẽ đi qua các khóa theo thứ tự tăng dần, luôn luôn và không tốn thêm gì. Mỗi phần tử là một pair<const Key, Value>, nên hãy dùng structured binding để tách khóa và giá trị gọn gàng:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // missing keys start at 0, then ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Để ý khóa trong binding là const: bạn có thể đổi giá trị qua vòng lặp với auto&, nhưng không bao giờ đổi được khóa tại chỗ (làm vậy sẽ phá vỡ thứ tự sắp xếp). Đầu ra theo thứ tự bảng chữ cái (blue, sea, sky) mà không cần bước sắp xếp nào, chính vì thế người ta chọn map thay vì bảng băm khi cần duyệt có thứ tự.

Idiom wordCount[w]++ đó cũng là cách dùng chuẩn mực của hành vi thêm khi truy cập: ở đây bạn muốn một khóa chưa có bắt đầu từ 0, nên [] là công cụ đúng.

Xóa phần tử và kích thước

Xóa theo khóa bằng erase, hàm này trả về số phần tử đã bị xóa (0 hoặc 1 với map). Bạn cũng có thể xóa qua một iterator lấy từ find. Kiểm tra trạng thái của container bằng size() và empty():

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (wasn't there)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Một cái bẫy khi xóa trong vòng lặp: m.erase(it) làm iterator it mất hiệu lực, nên bạn không thể ++it sau đó. Cách an toàn từ C++11 là it = m.erase(it), trả về iterator trỏ tới phần tử kế tiếp. Để xóa có điều kiện trên toàn bộ map chỉ trong một lần, std::erase_if(m, predicate) (C++20) gọn hơn.

Tiếp theo: unordered_map

std::map cho bạn khóa được sắp xếp và các thao tác O(log n) dễ đoán, nhưng bạn trả giá cho thứ tự đó ở mỗi lần tra cứu. Khi bạn không quan tâm thứ tự khóa và chỉ muốn tra cứu nhanh nhất có thể, unordered_map đổi cây sắp xếp lấy bảng băm, với truy cập trung bình O(1). Tiếp theo, chúng ta sẽ xem nó hoạt động ra sao, khi nào thời gian hằng số trung bình của nó thắng độ phức tạp logarit của map, và các bẫy về hàm băm (kiểu khóa tùy chỉnh, va chạm trong trường hợp xấu nhất) đi kèm.