std::unordered_multimap

#include <unordered_map>

template < class Key,                                               // unordered_multimap::key_type
           class T,                                                 // unordered_multimap::mapped_type
           class Hash = std::hash<Key>,                             // unordered_multimap::hasher
           class Pred = std::equal_to<Key>,                         // unordered_multimap::key_equal
           class Alloc = std::allocator< std::pair<const Key, T> >  // unordered_multimap::allocator_type
         > class unordered_multimap;

std::unordered_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::unordered_map, std::unordered_multimap không lưu trữ các phần tử theo một thứ tự cụ thể nào. Tuy nhiên, std::unordered_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.

Tham số

`Key`

Kiểu dữ liệu của key.

`T`

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

`Hash`

Hàm băm (hash function object) để băm giá trị của các key. Mặc định là std::hash<Key>.

`Pred`

Hàm so sánh (comparison function object) để kiểm tra xem hai key có bằng nhau hay không. Mặc định là std::equal_to<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.

`unordered_multimap`

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

Đặc điểm

Key không cần duy nhất: std::unordered_multimap cho phép lưu trữ các cặp key-value có key trùng lặp.
Phần tử không được sắp xếp: Các phần tử trong std::unordered_multimap không được sắp xếp theo một thứ tự cụ thể nào. Thứ tự của các phần tử có thể thay đổi sau mỗi lần chèn, xóa hoặc rehash.
Truy cập theo key: std::unordered_multimap cho phép truy cập trực tiếp các phần tử thông qua key (nhưng không hỗ trợ operator[]).
Iterator: std::unordered_multimap cung cấp iterator để duyệt qua các phần tử. Iterator của std::unordered_multimap là ForwardIterator.
Iterator có thể bị thay đổi (invalidate) khi thay đổi cấu trúc: Không giống như std::map, iterator của std::unordered_multimap có thể bị thay đổi (invalidate) khi bạn chèn, xóa phần tử hoặc rehash.
Tìm kiếm hiệu quả: Nhờ cấu trúc bảng băm, việc tìm kiếm phần tử trong std::unordered_multimap có độ phức tạp trung bình O(1) (thời gian hằng số). Tuy nhiên, trong trường hợp xấu nhất (khi xảy ra đụng độ hash nhiều), độ phức tạp có thể lên tới O(n), với n là số phần tử trong multimap.
Chèn và xóa: Việc chèn và xóa phần tử trong std::unordered_multimap có độ phức tạp trung bình O(1).
Ưu điểm:
- 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ử rất hiệu quả (trung bình O(1)).
- Dễ dàng truy cập phần tử theo key.
Nhược điểm:
- Các phần tử không được sắp xếp.
- Hiệu suất trong trường hợp xấu nhất có thể là O(n).
- Iterator có thể bị thay đổi (invalidate) khi thay đổi cấu trúc.
- Chi phí bộ nhớ có thể cao hơn std::map trong một số trường hợp (do bảng băm cần dự trữ không gian cho các bucket trống).
Khi nào nên sử dụng std::unordered_multimap:
- Khi bạn cần lưu trữ các cặp key-value.
- Khi bạn cho phép các key trùng lặp.
- Khi bạn không quan tâm đến thứ tự của các phần tử.
- 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::unordered_map và std::unordered_multimap

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

Ví dụ:

#include <iostream>
#include <unordered_map>
#include <string>

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

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

  // 3. Duyệt unordered_multimap (thứ tự không xác định)
  std::cout << "ummap1 elements:\n";
  for (const auto& pair : umap1) {
    std::cout << pair.first << ": " << pair.second << '\n';
  }
  // Output:
  // ummap1 elements:
  // orange: 3
  // banana: 2
  // apple: 1
  // apple: 4
  // (thứ tự có thể khác)

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

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

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

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

  // 8. Khai báo và khởi tạo với initializer list (C++11)
  std::unordered_multimap<int, std::string> ummap2 = {
    {1, "one"},
    {2, "two"},
    {3, "three"},
    {2, "another two"}
  };

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

  // 10. Hoán đổi nội dung 2 unordered_multimap
  ummap1.swap(ummap2);
  
  // 11. equal_range()
  auto range = ummap2.equal_range(2);
  for (auto it = range.first; it != range.second; ++it) {
      std::cout << it->first << ": " << it->second << '\n';
  }
  // Output:
  // 2: two
  // 2: another two
    
  // 12. count()
  std::cout << "so luong key = 2: " << ummap2.count(2) << '\n'; // Output: 2

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

  // 14. emplace_hint() (C++11)
  auto it2 = ummap1.emplace_hint(ummap1.begin(), 2, "second");
  ummap1.emplace_hint(it2, 3, "three");

  // 15. rehash() thay đổi số lượng bucket
  ummap1.rehash(100);

  // 16. reserve() thay đổi capacity
  ummap1.reserve(1000);

  return 0;
}

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

lưu ý

std::unordered_multimap không lưu trữ các phần tử theo một thứ tự cụ thể nào. Thứ tự duyệt qua các phần tử có thể thay đổi.
std::unordered_multimap cho phép lưu trữ các key trùng lặp.
Khi khởi tạo std::unordered_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::unordered_multimap.
Khi khởi tạo std::unordered_multimap từ một initializer list, các key trùng lặp vẫn được thêm vào.

Khai báo một std::unordered_map rỗng:

#include <unordered_map>
#include <string>

std::unordered_multimap<std::string, int> ummap1; // unordered_multimap rỗng, key kiểu std::string, value kiểu int

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

#include <unordered_map>
#include <string>

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

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

#include <unordered_map>
#include <string>

std::unordered_multimap<std::string, int> ummap3;
ummap3.insert(std::make_pair("apple", 1));
ummap3.insert(std::pair<std::string, int>("banana", 2)); // C++98
ummap3.insert({"orange", 3}); // C++11 initializer list trong hàm insert
ummap3.insert(std::make_pair("apple", 4)); // Chèn thêm giá trị cho key "apple"

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

#include <unordered_map>
#include <string>

int main() {
    std::unordered_multimap<std::string, int> ummap4 = {{"apple", 1}, {"banana", 2}, {"apple", 3}};
    std::unordered_multimap<std::string, int> ummap5(ummap4); // Sao chép từ ummap4
    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 <unordered_map>
#include <string>
#include <vector>

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

    std::unordered_multimap<std::string, int> ummap6(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 <unordered_map>
#include <string>

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

Chỉ định số lượng bucket (xô) ban đầu:

#include <unordered_map>

std::unordered_multimap<int, int> ummap9(100); // Khởi tạo với ít nhất 100 bucket

Chỉ định hash function và key equal function tùy chỉnh (ít dùng):

#include <unordered_map>
#include <string>

// Hash function tùy chỉnh
struct MyHash {
  std::size_t operator()(const std::string& s) const {
    return std::hash<std::string>()(s) * 2; // Ví dụ, nhân đôi hash mặc định
  }
};

// Key equal function tùy chỉnh
struct MyEqual {
  bool operator()(const std::string& s1, const std::string& s2) const {
    return s1.length() == s2.length(); // Ví dụ, so sánh độ dài chuỗi
  }
};

int main() {
    std::unordered_multimap<std::string, int, MyHash, MyEqual> ummap10;
    return 0;
}

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

std::unordered_multimap cũng giống như std::unordered_map, nó là một container liên kết (associative container) lưu trữ các phần tử dưới dạng cặp key-value. Do đó, nó có thể chứa các kiểu dữ liệu tương tự như std::unordered_map, bao gồm cả kiểu dữ liệu cho key và kiểu dữ liệu cho value.

Về cơ bản, std::unordered_multimap có thể chứa hầu hết các kiểu dữ liệu cho cả key và value, miễn là chúng đáp ứng các yêu cầu sau:

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

Yêu cầu:
- Có thể băm được (Hashable): Kiểu dữ liệu của key phải hỗ trợ hàm băm (hash function). Thư viện chuẩn C++ cung cấp std::hash cho các kiểu dữ liệu cơ bản và nhiều kiểu dữ liệu chuẩn khác. Đối với các kiểu dữ liệu tự định nghĩa, bạn cần phải cung cấp hàm băm riêng.
- Có thể so sánh bằng (Equality 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 bằng (equality comparison function) tùy chỉnh.
- CopyConstructible: Có copy constructor.
- 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, long, short,...
- std::string: Chuỗi ký tự.
- Con trỏ: int*, char*, MyClass*, ... (nhưng hãy cẩn thận, std::unordered_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à nó trỏ tới, và việc băm con trỏ thường dựa trên địa chỉ bộ nhớ).
- Các kiểu dữ liệu chuẩn có hỗ trợ hàm băm và so sánh bằng: 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), std::shared_ptr (có thể băm và so sánh địa chỉ), std::thread‌::id, std::type_index, std::unique_ptr (băm và so sánh con trỏ),...
- 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 cung cấp hàm băm và toán tử == (hoặc hàm so sánh bằng tùy chỉnh) cho chúng.

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

Yêu cầu:
- CopyAssignable hoặc MoveAssignable: value có thể được sao chép hoặc di chuyển.
- Destructible: Để std::unordered_multimap 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::unordered_multimap, 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::unordered_multimap (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ó 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ề các kiểu dữ liệu mà std::unordered_multimap có thể chứa:

#include <unordered_map>
#include <string>
#include <vector>
#include <memory>
#include <functional>

// Class Person với toán tử == và hàm băm
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 && age == other.age;
  }
};

// Định nghĩa hàm băm cho Person
namespace std {
  template <>
  struct hash<Person> {
    std::size_t operator()(const Person& p) const {
      size_t res = 17;
      res = res * 31 + std::hash<std::string>()(p.name);
      res = res * 31 + std::hash<int>()(p.age);
      return res;
    }
  };
}

int main() {
  std::unordered_multimap<int, std::string> mmap1;           // Key: int, Value: std::string
  std::unordered_multimap<std::string, int> mmap2;           // Key: std::string, Value: int
  std::unordered_multimap<Person, double> mmap3;            // Key: Person, Value: double
  std::unordered_multimap<int, std::vector<int>> mmap4;     // Key: int, Value: std::vector<int>
  std::unordered_multimap<int, std::unique_ptr<int>> mmap5; // Key: int, Value: std::unique_ptr<int>
  std::unordered_multimap<int, int*> mmap6;                  // Key: int, Value: int*

  // Key là con trỏ hàm, Value là std::string (mục đích minh họa, không khuyến khích)
  using FunctionPtr = int(*)(int, int);
  std::unordered_multimap<FunctionPtr, std::string> mmap7;

  return 0;
}

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


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

Dung lượng (Capacity)


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

Trình lặp (Iterators)


begin	Trả về một iterator trỏ đến phần tử đầu tiên trong std::unordered_multimap
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_multimap
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::unordered_multimap
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_multimap

Tra cứu phần tử (Element lookup)


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

Thay đổi nội dung (Modifiers)


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

Buckets


bucket_count	Trả về số lượng bucket (hay còn gọi là giỏ) hiện tại trong std::unordered_multimap
max_bucket_count	Trả về số lượng bucket tối đa mà std::unordered_multimap có thể có
bucket_size	Trả về số lượng phần tử hiện có trong một bucket cụ thể
bucket	Trả về chỉ số của bucket mà phần tử có key bằng với giá trị key cho trước được lưu trữ

Hash policy


load_factor	Trả về hệ số tải (load factor) hiện tại của std::unordered_multimap
max_load_factor	Truy vấn hoặc thiết lập hệ số tải tối đa (maximum load factor) của std::unordered_multimap
rehash	Thiết lập số lượng bucket trong bảng băm của std::unordered_multimap thành ít nhất count
reserve	Thay đổi số lượng phần tử mà std::unordered_multimap có thể chứa mà không cần phải rehash

Quan sát (Observers)


hash_function	Trả về một bản sao của hàm băm đang được sử dụng bởi std::unordered_multimap
key_eq	Trả về một bản sao của hàm so sánh bằng được sử dụng bởi std::unordered_multimap để kiểm tra xem hai key có bằng nhau hay không
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::unordered_multimap


Toán tử quan hệ	Các toán tử quan hệ trong std::unordered_multimap

Tham số​

Key​

T​

Hash​

Pred​

Allocator​

unordered_multimap​

Đặc điểm​

Ví dụ:​

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

Khai báo một std::unordered_map rỗng:​

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 từ một std::unordered_multimap 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):​

Chỉ định số lượng bucket (xô) ban đầu:​

Chỉ định hash function và key equal function tùy chỉnh (ít dùng):​

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

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

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

Ví dụ về các kiểu dữ liệu mà std::unordered_multimap có thể chứa:​

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

Dung lượng (Capacity)​

Trình lặp (Iterators)​

Tra cứu phần tử (Element lookup)​

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

Buckets​

Hash policy​

Quan sát (Observers)​