Map trong C++

Trong C++, map là một container trong thư viện chuẩn (STL) mà lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị, và cung cấp cách truy cập nhanh chóng đến các phần tử dựa trên khóa. Map được triển khai dưới dạng một cây đỏ-đen tự cân bằng.

Ví dụ:

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

using namespace std;

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

    // Thêm các cặp khóa-giá trị vào map
    myMap[1] = "One";
    myMap.insert(make_pair(2, "Two"));
    myMap.insert({3, "Three"});

    // Truy cập và xuất giá trị của một phần tử trong map
    cout << "Value of key 1: " << myMap[1] << endl;

    // Duyệt qua tất cả các phần tử của map
    cout << "All elements of map:" << endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << "Key: " << it->first << ", Value: " << it->second << endl;
    }

    return 0;
}
Phân loại:

1. std::map

• Đặc điểm:

  • Cấu trúc dựa trên cây đỏ-đen (Red-Black Tree).

  • Các phần tử (key–value) được sắp xếp theo thứ tự tăng dần của key.

  • Truy xuất, chèn, xoá có độ phức tạp trung bình O(log n).

  • Không cho phép trùng key.

• Ví dụ:

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

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

    m[2] = "two";
    m[1] = "one";
    m[3] = "three";

    for (auto &p : m) {
        cout << p.first << " => " << p.second << endl;
    }
    return 0;
}

👉 Output sẽ theo thứ tự key tăng dần:

1 => one
2 => two
3 => three

2. std::multimap

• Đặc điểm:

  • Giống map nhưng cho phép trùng key.

  • Vẫn được sắp xếp theo thứ tự của key.

• Ví dụ:

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

int main() {
    multimap<int, string> mm;

    mm.insert({1, "apple"});
    mm.insert({2, "banana"});
    mm.insert({1, "orange"}); // trùng key = 1

    for (auto &p : mm) {
        cout << p.first << " => " << p.second << endl;
    }
    return 0;
}

👉 Output:

1 => apple
1 => orange
2 => banana

3. std::unordered_map

• Đặc điểm:

  • Dựa trên hash table.

  • Truy xuất, chèn, xoá trung bình O(1) (nhanh hơn map).

  • Không sắp xếp các phần tử (thứ tự ngẫu nhiên).

  • Không cho phép trùng key.

• Ví dụ:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> um;

    um["apple"] = 5;
    um["banana"] = 10;
    um["orange"] = 7;

    for (auto &p : um) {
        cout << p.first << " => " << p.second << endl;
    }
    return 0;
}

👉 Output (thứ tự ngẫu nhiên):

banana => 10
orange => 7
apple => 5

4. std::unordered_multimap

• Đặc điểm:

  • Giống unordered_map nhưng cho phép trùng key.

  • Không sắp xếp, lưu theo hash.

• Ví dụ:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_multimap<int, string> umm;

    umm.insert({1, "cat"});
    umm.insert({2, "dog"});
    umm.insert({1, "tiger"}); // trùng key = 1

    for (auto &p : umm) {
        cout << p.first << " => " << p.second << endl;
    }
    return 0;
}

👉 Output (thứ tự ngẫu nhiên):

1 => cat
1 => tiger
2 => dog

✅ Tóm lại C++ có 4 loại map chính:

1. map – có thứ tự, không trùng key

2. multimap – có thứ tự, cho phép trùng key

3. unordered_map – không có thứ tự, không trùng key

4. unordered_multimap – không có thứ tự, cho phép trùng key

Kết luận:

map trong C++ là một container hữu ích để lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị, cung cấp khả năng truy cập nhanh chóng đến các phần tử dựa trên khóa. Nó thường được sử dụng trong các tình huống khi bạn cần ánh xạ từ một khóa tới một giá trị, và đặc biệt hữu ích khi sắp xếp dữ liệu theo khóa.