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 đó.