std::map

#include <map>

template < class Key,                                                 //  key_type
           class T,                                                   //  mapped_type
           class Compare = std::less<Key>,                            //  key_compare
           class Allocator = std::allocator<std::pair<const Key, T>>  //  allocator_type
         >
class map;

std::map trong C++ là một container liên kết (associative container) lưu trữ các phần tử được tạo thành từ sự kết hợp của key và value ánh xạ (mapped value), được gọi là các cặp (key-value pairs). Các phần tử trong std::map được sắp xếp theo key (duy nhất) và sử dụng cây tìm kiếm nhị phân cân bằng (thường là cây đỏ-đen) để lưu trữ, cho phép tìm kiếm, chèn và xóa phần tử một cách hiệu quả.

Tham số

`Key`

Kiểu dữ liệu của key. Key được sử dụng để sắp xếp và nhận dạng duy nhất các phần tử trong map.

`T`

Kiểu dữ liệu của value được ánh xạ.

`Compare`

Hàm so sánh (comparison function object) để xác định thứ tự sắp xếp của các key. Mặc định là std::less<Key>, tức là sắp xếp tăng dần theo key.

`Allocator`

Kiểu cấp phát bộ nhớ, mặc định là std::allocator<std::pair<const Key, T>>. Thường bạn không cần quan tâm đến tham số này.

`map`

Tên của std::map bạn muốn tạo.

Đặc điểm

Key duy nhất: std::map chỉ lưu trữ các cặp key-value với key duy nhất. Nếu bạn cố gắng chèn một phần tử có key đã tồn tại, thao tác chèn sẽ bị bỏ qua (đối với insert()) hoặc giá trị tương ứng với key đó sẽ bị ghi đè (đối với operator[]).
Phần tử được sắp xếp theo key: Các phần tử trong std::map luôn được sắp xếp theo key, mặc định là tăng dần (sử dụng std::less). Bạn có thể thay đổi thứ tự sắp xếp bằng cách cung cấp một hàm so sánh tùy chỉnh (tham số Compare).
Tìm kiếm hiệu quả: Nhờ cấu trúc cây tìm kiếm nhị phân, việc tìm kiếm phần tử trong std::map có độ phức tạp O(log n), với n là số phần tử trong map.
Truy cập theo key: std::map cho phép truy cập trực tiếp các phần tử thông qua key bằng toán tử [] hoặc hàm at().
Iterator: std::map cung cấp iterator để duyệt qua các phần tử. Iterator của std::map là BidirectionalIterator.
Iterator không bị thay đổi (invalidate) khi chèn: Không giống như std::vector, iterator của std::map không bị thay đổi (invalidate) khi bạn chèn thêm phần tử mới, trừ khi bạn xóa chính phần tử mà iterator đang trỏ tới.
Chèn và xóa: Việc chèn và xóa phần tử trong std::map có độ phức tạp trung bình O(log n).
Ưu điểm:
- Lưu trữ các phần tử theo key-value.
- Các phần tử luôn được sắp xếp theo key.
- Tìm kiếm, chèn và xóa phần tử hiệu quả.
- Dễ dàng truy cập phần tử theo key.
Nhược điểm:
- Việc sửa đổi trực tiếp giá trị của key có thể làm hỏng thứ tự sắp xếp. Bạn cần xóa đi chèn lại nếu muốn thay đổi key.
- Chi phí bộ nhớ cao hơn so với std::vector do phải lưu trữ thêm key và cấu trúc cây.
Khi nào nên sử dụng std::map:
- Khi bạn cần lưu trữ các cặp key-value.
- Khi bạn cần các phần tử luôn được sắp xếp theo key.
- Khi bạn cần thực hiện các thao tác tìm kiếm, chèn và xóa phần tử một cách hiệu quả.
- Khi bạn cần truy cập nhanh các phần tử theo key.

Phân biệt std::map và std::unordered_map

std::map: Lưu trữ các phần tử được sắp xếp theo key, sử dụng cây tìm kiếm nhị phân.
std::unordered_map: Lưu trữ các phần tử không theo thứ tự, sử dụng bảng băm (hash table). std::unordered_map thường nhanh hơn std::map trong việc chèn, xóa và tìm kiếm, nhưng không đảm bảo thứ tự của các phần tử.

Ví dụ:

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

int main() {
  // 1. Khai báo map rỗng
  std::map<std::string, int> map1;

  // 2. Chèn phần tử vào map
  map1["apple"] = 1;
  map1["banana"] = 2;
  map1["orange"] = 3;
  map1.insert(std::make_pair("grape", 4));
  map1.insert({"kiwi", 5}); // C++11 initializer list

  // 3. Truy cập phần tử theo key
  std::cout << "map1[\"banana\"]: " << map1["banana"] << '\n'; // Output: map1["banana"]: 2

  // 4. Duyệt map (các phần tử được sắp xếp theo key)
  std::cout << "map1 elements:\n";
  for (const auto& pair : map1) {
    std::cout << pair.first << ": " << pair.second << '\n';
  }
  // Output:
  // map1 elements:
  // apple: 1
  // banana: 2
  // grape: 4
  // kiwi: 5
  // orange: 3

  // 5. Tìm kiếm phần tử theo key
  auto it = map1.find("banana");
  if (it != map1.end()) {
    std::cout << "Found key \"banana\", value: " << it->second << '\n'; // Output: Found key "banana", value: 2
  }

  // 6. Xóa phần tử theo key
  map1.erase("banana");

  // 7. Kiểm tra map rỗng
  if (map1.empty()) {
    std::cout << "map1 is empty\n";
  } else {
    std::cout << "map1 is not empty\n"; // Output: map1 is not empty
  }

  // 8. Lấy kích thước map
  std::cout << "map1.size(): " << map1.size() << '\n'; // Output: map1.size(): 4

  // 9. Khai báo map với custom comparison function (sắp xếp giảm dần theo key)
  std::map<int, std::string, std::greater<int>> map2;
  map2[1] = "one";
  map2[3] = "three";
  map2[2] = "two";

  // 10. Xóa tất cả các phần tử
  map1.clear();

  // 11. Hoán đổi nội dung 2 map
  map1.swap(map2);

  // 12. Kiểm tra sự tồn tại của key
  if(map1.contains(3)) {
    // ...
  } // C++20

  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::map

lưu ý

std::map luôn lưu trữ các phần tử được sắp xếp theo key.
Mặc định, std::map sử dụng std::less để so sánh các key (sắp xếp tăng dần). Bạn có thể cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::map để thay đổi thứ tự sắp xếp.
Key trong std::map phải là duy nhất.
Khi sử dụng operator[] để truy cập một phần tử, nếu key chưa tồn tại, một phần tử mới với key đó và value mặc định sẽ được tự động thêm vào std::map.

Khai báo một std::map rỗng (sử dụng so sánh mặc định std::less cho key):

#include <map>
#include <string>

std::map<std::string, int> map1; // map rỗng, key kiểu std::string, value kiểu int, so sánh tăng dần theo key

Khai báo một std::map rỗng với hàm so sánh tùy chỉnh:

#include <map>
#include <string>
#include <functional> // std::greater

std::map<std::string, int, std::greater<std::string>> map2; // map rỗng, key kiểu std::string, value kiểu int, so sánh giảm dần theo key

Khai báo và khởi tạo từ một initializer list (C++11):

#include <map>
#include <string>

std::map<std::string, int> map3 = {
  {"apple", 1},
  {"banana", 2},
  {"orange", 3}
};

Khai báo và khởi tạo bằng cách sử dụng insert():

#include <map>
#include <string>

std::map<std::string, int> map4;
map4.insert(std::make_pair("apple", 1));
map4.insert(std::make_pair("banana", 2));
map4.insert(std::pair<std::string, int>("orange", 3)); // C++11
map4.insert({"kiwi", 4}); // C++11, initializer list

Khai báo và khởi tạo bằng cách sử dụng operator[]:

#include <map>
#include <string>

std::map<std::string, int> map5;
map5["apple"] = 1;
map5["banana"] = 2;
map5["orange"] = 3;

Khai báo và khởi tạo từ một std::map khác (copy constructor):

#include <map>
#include <string>

int main() {
    std::map<std::string, int> map6 = {{"apple", 1}, {"banana", 2}};
    std::map<std::string, int> map7(map6); // Sao chép từ map6
    return 0;
}

Khai báo và khởi tạo bằng cách sử dụng iterator range (sao chép từ container khác):

#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::pair<std::string, int>> vec = {
      {"apple", 1},
      {"banana", 2},
      {"orange", 3}
    };

    std::map<std::string, int> map8(vec.begin(), vec.end()); // Khởi tạo từ iterator range
    return 0;
}

Khai báo và khởi tạo bằng cách di chuyển (move constructor - C++11):

#include <map>
#include <string>

int main() {
    std::map<std::string, int> map9 = {{"apple", 1}, {"banana", 2}};
    std::map<std::string, int> map10(std::move(map9)); // Di chuyển từ map9 (map9 sẽ rỗng sau đó)
    return 0;
}

Các kiểu dữ liệu của std::map

std::map lưu trữ các cặp key-value, do đó chúng ta cần xem xét kiểu dữ liệu cho cả key và value.

1. Kiểu dữ liệu cho Key (Key):

Yêu cầu:
- Có thể so sánh được (Comparable): Kiểu dữ liệu của key phải hỗ trợ toán tử < (hoặc bạn phải cung cấp hàm so sánh tùy chỉnh Compare) để std::map có thể sắp xếp các phần tử theo key.
- CopyConstructible: Có copy constructor.
- CopyAssignable: Có toán tử gán operator=.
- Destructible: Có destructor.
- Thông thường, MoveConstructible và MoveAssignable cũng được khuyến khích để tối ưu hiệu suất (từ C++11).
Các kiểu dữ liệu có thể sử dụng làm Key:
- Các kiểu dữ liệu cơ bản: int, float, double, char, bool,...
- std::string: Chuỗi ký tự.
- Con trỏ: int*, char*, MyClass*,... (nhưng hãy cẩn thận, std::map sẽ so sánh địa chỉ của con trỏ chứ không phải nội dung mà nó trỏ tới).
- Các kiểu dữ liệu chuẩn có hỗ trợ toán tử <: std::pair, std::tuple (với so sánh từng thành phần), std::chrono::duration (và các kiểu thời gian khác), ...
- Kiểu dữ liệu do người dùng định nghĩa: Các class hoặc struct do bạn tự định nghĩa, miễn là bạn định nghĩa toán tử < cho chúng hoặc cung cấp hàm so sánh tùy chỉnh khi khai báo std::map.

Ví dụ về Key:

#include <map>
#include <string>
#include <functional>

// Class Person với toán tử <
class Person {
public:
  std::string name;
  int age;

  Person(std::string n, int a) : name(n), age(a) {}

  bool operator<(const Person& other) const {
    return name < other.name; // So sánh theo tên
  }
};

// Functor so sánh tùy chỉnh cho std::unique_ptr<int>
struct CompareUniquePtr {
  bool operator()(const std::unique_ptr<int>& a, const std::unique_ptr<int>& b) const {
    return *a < *b;
  }
};

int main() {
  std::map<int, std::string> map1; // Key: int
  std::map<std::string, int> map2; // Key: std::string
  std::map<Person, double> map3; // Key: Person (với toán tử < đã định nghĩa)
  std::map<std::unique_ptr<int>, std::string, CompareUniquePtr> map4; // Key: std::unique_ptr<int> (với hàm so sánh tùy chỉnh)
  std::map<std::shared_ptr<int>, std::string> map5; // Key: std::shared_ptr<int>
  std::map<int*, std::string> map6;
  return 0;
}

2. Kiểu dữ liệu cho Value (Mapped Type - T):

Yêu cầu:
- Default Constructible: Kiểu dữ liệu T phải có constructor mặc định (default constructor) không tham số. Lý do là khi bạn sử dụng operator[] với một key chưa tồn tại trong std::map, một phần tử mới sẽ được tạo ra với key đó và value được khởi tạo bằng constructor mặc định.
- CopyAssignable hoặc MoveAssignable: Để hỗ trợ gán giá trị.
- Destructible: Để std::map có thể giải phóng bộ nhớ khi các phần tử bị xóa.
Các kiểu dữ liệu có thể sử dụng làm Value:
- Hầu như mọi kiểu dữ liệu trong C++ đều có thể được sử dụng làm value trong std::map, bao gồm:
  - Các kiểu dữ liệu cơ bản: int, float, double, char, bool,...
  - Con trỏ: int*, char*, MyClass*,...
  - Các kiểu dữ liệu chuẩn: std::string, std::vector, std::list, std::set, std::map (chính nó),...
  - Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs): Miễn là chúng có constructor mặc định, copy constructor/move constructor, copy assignment operator/move assignment operator và destructor.
  - Smart pointers: std::unique_ptr, std::shared_ptr, std::weak_ptr
  - std::function, std::bind, lambda expressions (từ C++11)

Ví dụ về Value:

#include <map>
#include <string>
#include <vector>
#include <memory>

int main() {
  std::map<int, std::string> map1; // Value: std::string
  std::map<std::string, std::vector<int>> map2; // Value: std::vector<int>
  std::map<int, std::unique_ptr<int>> map3; // Value: std::unique_ptr<int>
  std::map<std::string, int*> map4; // Value: int*

  return 0;
}

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double, char, bool, ... std::map có thể chứa hầu hết các kiểu dữ liệu khác trong C++, miễn là chúng đáp ứng các yêu cầu về key và value như đã đề cập ở trên.

Con trỏ:
- Con trỏ đến các kiểu dữ liệu cơ bản: int*, float*, double*, char* (C-style strings), ...
- Con trỏ đến đối tượng của các lớp (bao gồm cả lớp tự định nghĩa): MyClass*, std::string*, std::vector<int>*, ...
- Con trỏ hàm:
```
#include <map>
#include <iostream>

int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }

int main() {
  std::map<std::string, int(*)(int, int)> math_functions;
  math_functions["add"] = add;
  math_functions["subtract"] = subtract;

  std::cout << math_functions["add"](5, 3) << std::endl; // Output: 8
  std::cout << math_functions["subtract"](5, 3) << std::endl; // Output: 2
  return 0;
}
```
  Lưu ý khi dùng con trỏ làm key
  - std::map sẽ so sánh giá trị của con trỏ (địa chỉ bộ nhớ) chứ không phải nội dung mà nó trỏ tới (trừ khi bạn cung cấp hàm so sánh tùy chỉnh).
  - Cần cẩn thận trong việc quản lý bộ nhớ để tránh memory leaks.

Smart Pointers (từ C++11):

std::unique_ptr: Cần cung cấp hàm so sánh tùy chỉnh nếu dùng làm key.
std::shared_ptr: Có thể dùng làm key mà không cần hàm so sánh tùy chỉnh (nó sẽ so sánh địa chỉ), nhưng hãy cẩn thận về ý nghĩa của việc so sánh này.

std::weak_ptr: Ít khi được sử dụng làm key.

#include <map>
#include <memory>
#include <string>

// Hàm so sánh cho unique_ptr<int> (nếu dùng làm key)
struct CompareUniquePtr {
    bool operator()(const std::unique_ptr<int>& a, const std::unique_ptr<int>& b) const {
        return *a < *b;
    }
};

int main() {
  std::map<int, std::shared_ptr<std::string>> shared_map;
  shared_map[1] = std::make_shared<std::string>("Hello");
  shared_map[2] = std::make_shared<std::string>("World");

  std::map<std::unique_ptr<int>, std::string, CompareUniquePtr> unique_map;
  unique_map.emplace(std::make_unique<int>(10), "Ten");
  unique_map.emplace(std::make_unique<int>(5), "Five");

  return 0;
}

Các kiểu dữ liệu chuẩn (Standard Library Types):
- std::string: Rất phổ biến để dùng làm key.
- Containers: std::vector, std::list, std::deque, std::array, std::set, std::map (chính nó), std::multiset, std::forward_list, ... (cần đảm bảo các container này hỗ trợ toán tử < hoặc cung cấp hàm so sánh tùy chỉnh nếu dùng làm key).
- std::pair và std::tuple: Thường được sử dụng để tạo key phức hợp (composite key).
- std::complex: Số phức.
- std::bitset: Tập hợp các bit.
- std::chrono::duration, std::chrono::time_point: Các kiểu thời gian.
- std::function, std::bind: (từ C++11) Dùng để lưu trữ hàm, functor, hoặc lambda expression.

Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
Bạn có thể sử dụng các class hoặc struct do mình định nghĩa làm key hoặc value cho std::map, miễn là:

Đối với Key: Định nghĩa toán tử < hoặc cung cấp hàm so sánh tùy chỉnh.

Đối với Value: Có constructor mặc định, copy constructor/move constructor, copy assignment operator/move assignment operator và destructor.

#include <map>
#include <string>

class Student {
public:
  std::string name;
  int id;

  Student(std::string n, int i) : name(n), id(i) {}

  // Toán tử < để so sánh Student theo ID
  bool operator<(const Student& other) const {
    return id < other.id;
  }
};

int main() {
  std::map<Student, int> studentGrades; // Key: Student, Value: int
  studentGrades.emplace(Student("Alice", 123), 90);
  studentGrades.emplace(Student("Bob", 456), 85);

  return 0;
}

Các hàm thành viên


=	Gán nội dung của một std::map khác hoặc một initializer_list cho std::map hiện tại

Trình lặp (Iterators)


begin	Trả về một iterator trỏ đến phần tử đầu tiên trong std::map
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::map
rbegin	Trả về một reverse_iterator trỏ đến phần tử cuối cùng trong std::map
rend	Trả về một reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::map
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::map
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::map
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng trong std::map
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::map

Dung lượng (Capacity)


empty	Kiểm tra xem std::map có rỗng hay không
size	Trả về số lượng phần tử (cặp `key-value`) hiện có trong std::map
max_size	Trả về số lượng phần tử (cặp `key-value`) tối đa mà std::map có thể chứa

Truy cập phần tử


[]	Truy cập phần tử có `key` tương ứng trong std::map
at	Truy cập phần tử có `key` cho trước

Thay đổi nội dung (Modifiers)


insert	Chèn một phần tử mới (cặp `key-value`) vào std::map
erase	Xóa một hoặc nhiều phần tử khỏi std::map
swap	Hoán đổi nội dung của hai std::map với nhau
clear	Xóa tất cả các phần tử khỏi std::map, làm cho std::map trở thành rỗng
emplace	Xây dựng (construct) một phần tử mới (cặp `key-value`) trực tiếp trong std::map tại vị trí thích hợp
emplace_hint	Xây dựng (construct) một phần tử mới (cặp `key-value`) trực tiếp trong std::map với một gợi ý (hint)

Quan sát (Observers)


key_comp	Trả về một bản sao của hàm so sánh được sử dụng bởi std::map để sắp xếp các `key`
value_comp	Trả về một hàm so sánh dùng để so sánh các `value_type` trong std::map

Thao tác (Operations)


find	Tìm kiếm một phần tử có `key` bằng với giá trị `key` cho trước trong std::map
count	Đếm số lượng phần tử có `key` bằng với giá trị `key` cho trước trong std::map
lower_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::map có `key` lớn hơn hoặc bằng giá trị `key` cho trước
upper_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::map có `key` lớn hơn giá trị `key` cho trước
equal_range	Trả về một cặp iterator xác định phạm vi các phần tử trong std::map có `key` bằng với giá trị `key` cho trước

Cấp phát (Allocator)


get_allocator	Trả về một bản sao của bộ cấp phát (allocator) được liên kết với std::map

Tham số​

Key​

T​

Compare​

Allocator​

map​

Đặc điểm​

Ví dụ:​

Các cách phổ biến khai báo và khởi tạo một std::map​

Khai báo một std::map rỗng (sử dụng so sánh mặc định std::less cho key):​

Khai báo một std::map rỗng với hàm so sánh tùy chỉnh:​

Khai báo và khởi tạo từ một initializer list (C++11):​

Khai báo và khởi tạo bằng cách sử dụng insert():​

Khai báo và khởi tạo bằng cách sử dụng operator[]:​

Khai báo và khởi tạo từ một std::map khác (copy constructor):​

Khai báo và khởi tạo bằng cách sử dụng iterator range (sao chép từ container khác):​

Khai báo và khởi tạo bằng cách di chuyển (move constructor - C++11):​

Các kiểu dữ liệu của std::map​

1. Kiểu dữ liệu cho Key (Key):​

Ví dụ về Key:​

2. Kiểu dữ liệu cho Value (Mapped Type - T):​

Ví dụ về Value:​

Các hàm thành viên​

Trình lặp (Iterators)​

Dung lượng (Capacity)​

Truy cập phần tử​

Thay đổi nội dung (Modifiers)​

Quan sát (Observers)​

Thao tác (Operations)​

Cấp phát (Allocator)​