Map là một cấu trúc dữ liệu rất phổ biến và được hầu hết các ngôn ngữ lập trình hỗ trợ tích hợp sẵn trong thư viện. Ưu điểm của nó là đưa ra được một giải pháp giúp tổ chức tốt dữ liệu dạng tập hợp, cách cài đặt đơn giản nhưng mang lại hiệu năng sử dụng tốt. Với C++, Map đã được tích hợp sẵn trong thư viện chuẩn và cho thấy mức độ sử dụng thường xuyên của nó. Bài viết hôm nay chúng ta cùng nhau tìm hiểu xem Map trong C++ là gì và làm quen với các thao tác cơ bản trong Map bằng ví dụ cụ thể nhé.
Map trong C++ là gì?
Map là một cấu trúc dữ liệu mà trong đó mỗi phần tử là ánh xạ giữa khóa – key sang giá trị – value của khóa đó. Map được cài đặt sẵn trong STL (Standard Template Library – Thư viện mẫu chuẩn) của C++, sử dụng dưới dạng container lưu trữ dữ liệu như một từ điển. Như ở ví dụ hình dưới đây, các cặp 1-Maps, 2-in, 3-C++ là những phần tử trong một Map, với 1, 2, 3 là các khóa và Maps, in, C++ là các giá trị tương ứng. Để truy cập đến giá trị trong Map, chúng ta cần biết và thông qua các khóa.
Cú pháp khai báo Map trong C++:
#include <map> map<key_data_type, value_data_type> map_name; map<int, int> a; map<char, int> b;
Trong đó:
- include <map>: khai báo thêm thư viện map vào chương trình
- key_data_type: kiểu dữ liệu cho khóa
- value_data_type: kiểu dữ liệu cho giá trị
Tính chất ràng buộc của Map trong C++:
- Các key trong một Map là duy nhất, không được tồn tại 2 keys trùng nhau
- Map không hỗ trợ truy cập thông qua chỉ số như mảng hay string
- Mỗi phần trong trong Map chính là một Pair (kiểu container lưu trữ dữ liệu theo cặp trong C++)
- Map được mặc định sắp xếp theo thứ tự tăng dần giá trị key
Các thao tác cơ bản của Map
- size(): trả về kích thước của Map
- empty(): kiểm tra map có rỗng hay không
- insert(): thêm phần tử vào Map
- clear(): xóa toàn bộ phần tử trong Map
- map[key]: truy cập giá trị của khóa key
- erase(): xóa phần tử trong Map
- map[key] = newValue: sửa giá trị gắn với key
Cách sử dụng:
map<int, int> mp; mp.insert(make_pair(2, 4)); //ok mp.insert(make_pair(1, 2)); //ok mp.insert(make_pair(3, 5)); //ok mp.insert(make_pair(2, 2)); //not ok cout << mp.size() << endl; //3 cout << mp.empty() << endl; //0 cout << mp[2] << endl; // 4 mp.clear(); cout << mp.size() << endl; //0 cout << mp.empty() << endl; //1
Ở ví dụ trên:
- Hàm make_pair sử dụng để tạo ra một cặp giá trị (first, second) cũng chính là một phần tử của Map
- Trường hợp thực hiện hàm insert với giá trị key đã tồn tại trong Map thì thao tác này sẽ không thực hiện được. Lúc này giá trị của key = 2 không bị thay đổi mà vẫn là giá trị cũ value = 4
- Hàm size trả về đúng kích thước hiện có của Map, sau khi gọi hàm clear thì Map sẽ trở thành rỗng có kích thước = 0
Thao tác duyệt Map
Duyệt Map là một trong những thao tác cơ bản, thường được sử dụng nhất trong quá trình viết code. Ý tưởng cơ bản là dùng các vòng lặp để thực hiện việc duyệt qua giá trị của tất cả các phần tử trong Map, đồng thời lấy ra kết quả theo yêu cầu. Một số thao tác duyệt Map thường dùng gồm:
1. Duyệt tuần tự – Range-based for loop
Range-based for loop là vòng lặp giúp bạn duyệt qua các phần tử trong Map container một cách tuần tự từ đầu đến cuối. Nó cũng được gọi là for-each loop, được bổ sung từ phiên bản C++ 11.
map<int, int> mp; mp.insert(make_pair(1, 2)); // ok mp.insert(make_pair(2, 4)); // ok mp.insert(make_pair(3, 5)); // ok for(pair<int, int> it : mp){ cout << "key = " << it.first << ", value = " << it.second << endl; } // Output // key = 1, value = 2 // key = 2, value = 4 // key = 3, value = 5
2. Duyệt với vòng lặp
Sử dụng vòng lặp for với chỉ số bắt đầu từ begin, kết thúc ở end là cách phổ biến nhất để duyệt qua tất cả phần tử trong Map.
map<int, int> mp; mp.insert(make_pair(1, 2)); // ok mp.insert(make_pair(2, 4)); // ok mp.insert(make_pair(3, 5)); // ok map<int,int>::iterator it; for(it = mp.begin(); it != mp.end(); it++){ cout << "key = " << (*it).first << ", value = " << (*it).second << endl; } // Output // key = 1, value = 2 // key = 2, value = 4 // key = 3, value = 5
3. Duyệt ngược
Trong một số trường hợp, nếu bạn cần duyệt ngược từ cuối Map lên đầu thì chúng ta có thể sử dụng trình lặp đảo reverse_iterator để chuyển các phần tử trong Map vào 1 Vector. Từ đó sử dụng các phương thức rbegin, rend để duyệt ngược các phần tử.
map<int, int> mp; mp.insert(make_pair(1, 2)); // ok mp.insert(make_pair(2, 4)); // ok mp.insert(make_pair(3, 5)); // ok map<int,int>::reverse_iterator it; for(it = mp.rbegin(); it != mp.rend(); it++){ cout << "key = " << (*it).first << ", value = " << (*it).second << endl; } // Output // key = 3, value = 5 // key = 2, value = 4 // key = 1, value = 2
So sánh Map và các kiểu dữ liệu khác trong C++
Trong C++, ngoài Map thì chúng ta còn có một số kiểu dữ liệu lưu trữ khác thường được sử dụng và dễ nhầm lẫn với Map như Set, unordered_map, multimap, … Chúng ta cùng so sánh cách sử dụng để tránh bị nhầm lẫn và lựa chọn phù hợp với bài toán nhé:
- Set: khác với Map, mỗi phần tử trong Set chỉ lưu một giá trị là khóa, hay nói cách khác thì Set là tập hợp các key, trong khi Map là tập hợp của các cặp key-value
- Unordered_set/ Unordered_map: tương ứng với Set và Map, 2 dạng dữ liệu unordered này được sinh ra để khi thêm các phần tử vào tập hợp sẽ không có thứ tự. Việc này giúp tăng hiệu năng khi thực hiện thêm phần tử, nhưng sẽ làm giảm hiệu năng trong quá trình tìm kiếm
- Multimap: là kiểu Map nhưng cho phép các key có thể có giá trị giống nhau. Điều này dẫn đến việc bạn không thể truy cập giá trị thông qua khóa một cách bình thường như với Map.
Kết bài
Qua bài viết này, chúng ta đã cùng nhau tìm hiểu về kiểu dữ liệu Map trong C++ cùng với các thao tác cơ bản trên cấu trúc này. Map, Set và các kiểu dữ liệu mảng, tập hợp khác thường xuyên được sử dụng trong các bài toán thực tế, vì vậy bạn cần nắm chắc được cách khai báo và thao tác để lấy đúng dữ liệu yêu cầu. Hy vọng bài viết hữu ích dành cho bạn và hẹn gặp lại trong các bài viết tiếp theo của mình.
Tác giả: Phạm Minh Khoa
Xem thêm:
- Microsoft Visual C++ là gì? Các tính năng của Microsoft Visual C++
- Cấu trúc chương trình C/C++, file .c, .cpp
- C++ algorithm: Những thuật toán cơ bản trong C++
Xem ngay tin đăng tuyển lập trình viên đãi ngộ tốt trên TopDev
