std::multimap

#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 multimap;

std::multimap 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). Tương tự như std::map, các phần tử trong std::multimap được sắp xếp theo key. Tuy nhiên, std::multimap cho phép các key trùng lặp, nghĩa là nhiều phần tử có thể có cùng một key. Giống như std::map, std::multimap thường được triển khai bằng cây tìm kiếm nhị phân cân bằng (thường là cây đỏ-đen), 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 các phần tử trong multimap.

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.

multimap

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

Đặc điểm

1. Key không cần duy nhất: std::multimap cho phép lưu trữ các cặp key-value có key trùng lặp.
2. Phần tử được sắp xếp theo key: Các phần tử trong std::multimap 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).
3. Chèn và xóa: Việc chèn và xóa phần tử trong std::multimap có độ phức tạp trung bình O(log n).
4. Không hỗ trợ truy cập theo chỉ số: Bạn không thể truy cập các phần tử trong std::multimap bằng chỉ số như mảng hay vector. Thay vào đó, bạn phải sử dụng iterator.
5. Iterator không bị thay đổi (invalidate) khi chèn: Không giống như std::vector, iterator của std::multimap 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.
6. 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::multimap có độ phức tạp O(log n), với n là số phần tử trong multimap.
7. Ư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.
   • Cho phép lưu trữ các key trùng lặp.
   • Tìm kiếm, chèn và xóa phần tử tương đối hiệu quả.
8. Nhược điểm:
   • Không thể truy cập phần tử theo chỉ số.
   • 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.
9. Khi nào nên sử dụng std::multimap:
   • 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 cho phép các key trùng lặp.
   • 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ả.

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

• std::map: Lưu trữ các phần tử với key duy nhất.
• std::multimap: Cho phép lưu trữ các phần tử với key trùng lặp.

Ví dụ:

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

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

  // 2. Chèn phần tử vào multimap
  mmap1.insert(std::make_pair("apple", 1));
  mmap1.insert(std::make_pair("banana", 2));
  mmap1.insert(std::make_pair("orange", 3));
  mmap1.insert(std::make_pair("banana", 4)); // Chèn thêm một phần tử có key "banana"

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

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

  // 5. Xóa phần tử theo key
  mmap1.erase("banana"); // Xóa tất cả phần tử có key là "banana"

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

  // 7. Lấy kích thước multimap
  std::cout << "mmap1.size(): " << mmap1.size() << '\n'; // Output: mmap1.size(): 2

  // 8. Khai báo multimap với custom comparison function (sắp xếp giảm dần theo key)
  std::multimap<int, std::string, std::greater<int>> mmap2;
  mmap2.insert(std::make_pair(1,"one"));
  mmap2.insert(std::make_pair(3,"three"));
  mmap2.insert(std::make_pair(3,"third"));
  mmap2.insert(std::make_pair(2,"two"));

  std::cout << "mmap2 elements:\n";
  for (const auto& pair : mmap2) {
      std::cout << pair.first << ": " << pair.second << '\n';
  }
  // Output:
  // mmap2 elements:
  // 3: three
  // 3: third
  // 2: two
  // 1: one

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

  // 10. Hoán đổi nội dung 2 multimap
  mmap1.swap(mmap2);

  // 11. equal_range()
  auto range = mmap2.equal_range(3);
  for (auto it = range.first; it != range.second; ++it) {
      std::cout << it->first << ": " << it->second << '\n';
  }
  // Output:
  // 3: three
  // 3: third
    
  // 12. count()
  std::cout << "so luong key = 3: " << mmap2.count(3) << '\n';

  // 13. emplace() (C++11)
  mmap1.emplace(4, "four");
  mmap1.emplace(4, "forth");

  // 14. emplace_hint() (C++11)
  auto it2 = mmap1.emplace_hint(mmap1.begin(), 2, "second");
  mmap1.emplace_hint(it2, 3, "three");
  
  // 15. merge() (C++17)
  mmap1.merge(mmap2);

  return 0;
}

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

lưu ý

• std::multimap luôn lưu trữ các phần tử được sắp xếp theo key.
• Mặc định, std::multimap 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::multimap để thay đổi thứ tự sắp xếp.
• std::multimap cho phép lưu trữ các key trùng lặp.
• Khi khởi tạo std::multimap từ một range hoặc một container khác, các phần tử sẽ được sao chép vào std::multimap và sau đó được sắp xếp.
• Khi khởi tạo std::multimap từ một initializer list, các phần tử sẽ được sắp xếp.

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

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

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

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

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

   #include <map>
   #include <string>
   
   std::multimap<std::string, int> mmap3 = {
     {"apple", 1},
     {"banana", 2},
     {"orange", 3},
     {"apple", 4} // Chấp nhận key trùng lặp
   };

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

   #include <map>
   #include <string>
   
   std::multimap<std::string, int> mmap4;
   mmap4.insert(std::make_pair("apple", 1));
   mmap4.insert(std::make_pair("banana", 2));
   mmap4.insert(std::make_pair("orange", 3));
   mmap4.insert(std::make_pair("apple", 4)); // Chèn thêm giá trị cho key "apple"
   mmap4.insert({"kiwi", 4}); // C++11, initializer list

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

   #include <map>
   #include <string>
   
   int main() {
       std::multimap<std::string, int> mmap5 = {{"apple", 1}, {"banana", 2}, {"apple", 3}};
       std::multimap<std::string, int> mmap6(mmap5); // Sao chép từ mmap5
       return 0;
   }

6. 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},
         {"apple", 4}
       };
   
       std::multimap<std::string, int> mmap7(vec.begin(), vec.end()); // Khởi tạo từ iterator range
       return 0;
   }

7. 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::multimap<std::string, int> mmap8 = {{"apple", 1}, {"banana", 2}, {"apple", 3}};
       std::multimap<std::string, int> mmap9(std::move(mmap8)); // Di chuyển từ mmap8 (mmap8 sẽ rỗng sau đó)
       return 0;
   }

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

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double, ..., std::multimap 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 một số yêu cầu nhất định tương tự như std::map.

1. Con trỏ:

   • int*, float*, double*

   • char* (C-style strings) - Cần cẩn thận với việc so sánh và quản lý bộ nhớ.

   • Con trỏ đến các đối tượng của lớp tự định nghĩa

   • Con trỏ hàm

     Lưu ý khi dùng con trỏ làm key

     • std::multimap sẽ so sánh giá trị của con trỏ (địa chỉ bộ nhớ) chứ không phải so sánh nội dung mà con trỏ trỏ tới (trừ khi bạn cung cấp hàm so sánh tùy chỉnh).
     • Bạn cần đảm bảo rằng việc quản lý bộ nhớ cho các đối tượng được trỏ đến là chính xác để tránh rò rỉ bộ nhớ hoặc lỗi khi std::multimap bị hủy.

2. Các kiểu dữ liệu chuẩn (Standard Library Types):

   • std::string: Chuỗi ký tự. std::multimap sẽ so sánh các chuỗi theo thứ tự từ điển.

     std::multimap<std::string, int> studentScores;
     studentScores.insert({"Alice", 90});
     studentScores.insert({"Bob", 85});
     studentScores.insert({"Alice", 95}); // Thêm điểm cho Alice

   • Containers: Bao gồm std::vector, std::list, std::deque, std::array, std::set, std::map, std::multiset, std::multimap (chính nó), std::forward_list,...

     std::multimap<int, std::vector<std::string>> studentCourses;
     std::multimap<int, std::list<int>> groupMembers;

   • std::pair và std::tuple:

     std::multimap<std::pair<int, int>, std::string> pointNames; // Key là một cặp số nguyên
     std::multimap<int, std::tuple<std::string, int, double>> studentRecords;

   • Các kiểu khác: std::complex, std::bitset, std::chrono::duration, std::chrono::time_point,...

     Lưu ý khi sử dụng container, std::pair, std::tuple làm key

     • Bạn cần đảm bảo rằng các kiểu dữ liệu này hỗ trợ toán tử < (hoặc cung cấp hàm so sánh tùy chỉnh) để std::multimap có thể sắp xếp chúng.
     • Với std::pair và std::tuple, toán tử < mặc định sẽ so sánh từng thành phần tương ứng theo thứ tự từ trái sang phải.

3. Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
   Bạn có thể tạo std::multimap chứa các đối tượng của bất kỳ lớp (class) hoặc cấu trúc (struct) nào do bạn định nghĩa, miễn là chúng thỏa mãn các yêu cầu sau:

   • Phải có cách so sánh: Bạn cần định nghĩa toán tử < cho lớp/struct của mình, hoặc cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::multimap. Cách này giúp std::multimap biết cách sắp xếp các đối tượng.
   • Key phải CopyConstructible và CopyAssignable: Vì key luôn phải được copy khi insert() vào std::multimap
   • Value phải CopyConstructible và CopyAssignable: value có thể được copy khi insert() và 1 số thao tác khác.
   • Nên có MoveConstructor và MoveAssignable để tối ưu khi dùng với các hàm như insert()
   • Destructible: Có destructor để giải phóng tài nguyên khi std::multimap bị hủy

     class Person {
     public:
       std::string name;
       int age;
     
       Person(std::string n, int a) : name(n), age(a) {}
     
       // Định nghĩa toán tử < để so sánh Person theo tuổi
       bool operator<(const Person& other) const {
         return age < other.age;
       }
     };
     
     int main() {
       std::multimap<Person, std::string> personRoles; // Key: Person, Value: std::string
       personRoles.insert(std::make_pair(Person("Alice", 30), "Manager"));
       personRoles.insert(std::make_pair(Person("Bob", 25), "Developer"));
       personRoles.insert(std::make_pair(Person("Charlie", 35), "Manager"));
       personRoles.insert(std::make_pair(Person("Alice", 30), "Leader")); // Thêm vai trò khác cho Alice
     
       return 0;
     }

4. Smart Pointers (từ C++11):
   Bạn có thể sử dụng std::multimap để lưu trữ các smart pointers như std::unique_ptr hoặc std::shared_ptr.

   • Với std::unique_ptr: Bạn cần cung cấp hàm so sánh tùy chỉnh, vì std::unique_ptr không hỗ trợ toán tử < mặc định.
   • Với std::shared_ptr: std::shared_ptr hỗ trợ toán tử < (so sánh địa chỉ), nên bạn có thể sử dụng std::multimap với std::shared_ptr mà không cần hàm so sánh tùy chỉnh (nhưng hãy cẩn thận về ý nghĩa của việc so sánh này).

     #include <map>
     #include <memory>
     #include <iostream>
     
     // 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::multimap<int, std::shared_ptr<std::string>> shared_map;
       shared_map.insert(std::make_pair(1, std::make_shared<std::string>("Hello")));
       shared_map.insert(std::make_pair(2, std::make_shared<std::string>("World")));
       shared_map.insert(std::make_pair(1, std::make_shared<std::string>("Hello Again")));
     
       std::multimap<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");
       unique_map.emplace(std::make_unique<int>(10), "Ten Again");
     
         for (const auto& pair : unique_map) {
             std::cout << *pair.first << " ";
         }
         std::cout << std::endl;
     
         for (const auto& pair : shared_map) {
             std::cout << *pair.second << " ";
         }
         std::cout << std::endl;
         
       return 0;
     }

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

=	Gán nội dung của một std::multimap khác hoặc một initializer_list cho std::multimap 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::multimap
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::multimap
rbegin	Trả về một reverse_iterator trỏ đến phần tử cuối cùng trong std::multimap
rend	Trả về một reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::multimap
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::multimap
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::multimap
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng trong std::multimap
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::multimap

Dung lượng (Capacity)

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

Thay đổi nội dung (Modifiers)

insert	Chèn một phần tử mới (cặp key-value) vào std::multimap
erase	Xóa một hoặc nhiều phần tử khỏi std::multimap
swap	Hoán đổi nội dung của hai std::multimap với nhau
clear	Xóa tất cả các phần tử khỏi std::multimap
emplace	Xây dựng (construct) một phần tử mới trực tiếp trong std::multimap tại vị trí thích hợp
emplace_hint	Xây dựng (construct) một phần tử mới trực tiếp trong std::multimap 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::multimap để 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::multimap

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::multimap
count	Đếm số lượng phần tử có key bằng với giá trị key cho trước trong std::multimap
lower_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::multimap 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::multimap 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::multimap 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::multimap