map trong C++

Map giải quyết bài toán cốt lõi mà các container tuyến tính khác (array, vector, list) không thể làm tốt: Tra cứu, thêm và chỉnh sửa dữ liệu của một khóa - Key với tốc độ rất nhanh O(1) hoặc O(logN).

Sự khác biệt đó được thể hiện qua các điểm sau

1. Truy cập các phần tử theo index (array/vector) với truy cập theo khóa Key

• Vector/Array chỉ cho phép ta truy cập một phần tử dựa theo giá trị index. Nếu ta muốn tìm một giá trị nào đó trong tập hợp thì cần phải duyệt tất cả các phần tử để tìm ra nó, tốn thời gian O(N). Với số lượng phần tử tăng lên thì thời gian tìm kiếm cũng tăng theo.
• Còn map thì khác. Map cho phép ta dùng bất cứ cái gì để làm Key - int, string hay một class (Object). Khi ta truyền khóa key vào thì Map sẽ nhảy đến nơi chứa dữ liệu đó ngay lập tức, rất nhanh O(1) mà không cần duyệt qua tất cả các phần tử

2. Liên kết dữ liệu (Key-Value Association) Các container như vector hay set chỉ lưu giá trị đơn lẻ. Còn map lưu trữ theo cặp Key-Value

• Khóa Key: đại diện cho định danh
• Value: Dữ liệu gắn liền với định danh đó.

3. Các hàm tiện ích

• contains(key): Kiểm tra một key trong map có tồn tại hay không. Trả về true nếu tồn tại và false nếu ngược lại.

I. Khái niệm

• Map không cho phép trùng Key
• Các phần tử trong map luôn được sắp xếp tự động dựa vào Key

Ví dụ

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

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

    numbers[0] = "zero";
    numbers[1] = "one";
    numbers[2] = "two";
    numbers[3] = "three";
    numbers[4] = "four";

    for(auto& number : numbers) {
        std::cout << number.first << " " << number.second << std::endl;
    }
    return 0;
}

Các hoạt động thao tác

1. Thêm

    map<int, string> numbers = {{2, "Two"}, {3, "Three"}};

    // Inserting a key value pair
    numbers.insert({1, "One"});

2. Truy cập

Dùng [] or at()

std::cout << numbers[1];
std::cout << numbers.at(2);

3. Update

    numbers[0] = "One";
    numbers.at(1) = "Zero";

Find()

Tìm khóa key có trong map, nếu tìm thấy trả về iterator đến key đó, nếu không có thì trả về end()

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

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

    numbers[0] = "zero";
    numbers[1] = "one";
    numbers[2] = "two";
    numbers[3] = "three";
    numbers[4] = "four";

    auto it = numbers.find(1);

    if(it != numbers.end()) {
        std::cout << it->first << " " << it->second;
    } else {
        std::cout << "Không tìm thấy key";
    }

    return 0;
}