std::unordered_multiset

#include <unordered_set>

template < class Key,                         // unordered_multiset::key_type/value_type
           class Hash = std::hash<Key>,       // unordered_multiset::hasher
           class Pred = std::equal_to<Key>,   // unordered_multiset::key_equal
           class Alloc = std::allocator<Key>  // unordered_multiset::allocator_type
         > class unordered_multiset;

std::unordered_multiset trong C++ là một container liên kết (associative container) lưu trữ các phần tử không theo thứ tự cụ thể nào. Khác với std::unordered_set, std::unordered_multiset cho phép lưu trữ các phần tử trùng lặp. Nó được triển khai bằng bảng băm (hash table), cho phép tìm kiếm, chèn và xóa phần tử với độ phức tạp trung bình là hằng số (O(1)), tuy nhiên trong trường hợp xấu nhất có thể lên tới tuyến tính (O(n)).

Tham số

`Key`

Kiểu dữ liệu của các phần tử trong std::unordered_multiset.

`Hash`

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

`Pred`

Hàm so sánh (comparison function object) để kiểm tra xem hai phần tử 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<Key>. Thường bạn không cần quan tâm đến tham số này.

`unordered_multiset`

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

Đặc điểm

Phần tử trùng lặp: std::unordered_multiset cho phép lưu trữ các phần tử trùng lặp.
Phần tử không được sắp xếp: Các phần tử trong std::unordered_multiset 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 hoặc xóa.
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::unordered_multiset bằng chỉ số như mảng hay vector. Thay vào đó, bạn phải sử dụng iterator.
Iterator có thể bị thay đổi (invalidate) khi thay đổi cấu trúc: Không giống như std::set, iterator của std::unordered_multiset 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_multiset 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(m), với n là số phần tử trong multiset.
Chèn và xóa hiệu quả: Việc chèn và xóa phần tử trong std::unordered_multiset cũng có độ phức tạp trung bình O(1).
Ưu điểm:
- Cho phép lưu trữ các phần tử 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)).
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).
- Không thể truy cập phần tử theo chỉ số.
- Iterator có thể bị thay đổi (invalidate) khi thay đổi cấu trúc.
Khi nào nên sử dụng std::unordered_multiset:
- Khi bạn cần lưu trữ một tập hợp các phần tử, cho phép 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_set và std::unordered_multiset

std::unordered_set: Lưu trữ các phần tử duy nhất, không cho phép trùng lặp.
std::unordered_multiset: Cho phép lưu trữ các phần tử trùng lặp.

Ví dụ:

#include <iostream>
#include <unordered_set>
#include <string>

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

  // 2. Chèn phần tử vào unordered_multiset
  umset1.insert("apple");
  umset1.insert("banana");
  umset1.insert("orange");
  umset1.insert("apple"); // Phần tử trùng lặp được cho phép

  // 3. Duyệt unordered_multiset (thứ tự không xác định)
  std::cout << "umset1 elements:";
  for (const std::string& str : umset1) {
    std::cout << ' ' << str;
  }
  std::cout << '\n'; // Output: umset1 elements: orange apple apple banana (thứ tự có thể khác)

  // 4. Tìm kiếm phần tử
  if (umset1.find("banana") != umset1.end()) {
    std::cout << "Found element 'banana'\n"; // Output: Found element 'banana'
  }

  // 5. Xóa phần tử
  umset1.erase("apple"); // Xóa tất cả phần tử "apple"

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

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

  // 8. Khai báo và khởi tạo với initializer list (C++11)
  std::unordered_multiset<int> umset2 = {1, 2, 3, 4, 5, 1, 2};

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

  // 10. Kiểm tra sự tồn tại của phần tử (C++20)
  if (umset2.contains(3)) {
    std::cout << "umset2 contains 3\n";
  }

  // 11. Hoán đổi nội dung 2 unordered_multiset
  umset1.swap(umset2);

  // 12. Lấy số xô (bucket_count)
  umset1.bucket_count();

  // 13. Lấy bucket mà 1 phần tử đang ở trong đó
  umset1.bucket(3);

  // 14. Lấy số phần tử trong 1 bucket
  umset1.bucket_size(0);
  
  // 15. equal_range()
  auto range = umset1.equal_range(3);
  for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
  }
  std::cout << '\n';
    
  // 16. count()
  std::cout << umset1.count(3) << '\n';

  return 0;
}

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

lưu ý

std::unordered_multiset 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_multiset cho phép lưu trữ các phần tử trùng lặp.
Khi khởi tạo std::unordered_multiset 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_multiset.
Khi khởi tạo std::unordered_multiset từ một initializer list, các phần tử trùng lặp vẫn được thêm vào.

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

#include <unordered_set>
#include <string>

std::unordered_multiset<std::string> umset1; // unordered_multiset rỗng, kiểu std::string
std::unordered_multiset<int> umset2;         // unordered_multiset rỗng, kiểu int

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

#include <unordered_set>
#include <string>

std::unordered_multiset<std::string> umset3 = {"apple", "banana", "orange", "apple"}; // "apple" xuất hiện 2 lần
std::unordered_multiset<int> umset4 = {3, 1, 4, 1, 5, 9, 2, 6, 3}; // Khởi tạo và cho phép phần tử trùng lặp

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

#include <unordered_set>
#include <string>

std::unordered_multiset<std::string> umset5;
umset5.insert("apple");
umset5.insert("banana");
umset5.insert("orange");
umset5.insert("apple"); // Chèn thêm "apple"

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

#include <unordered_set>
#include <string>

int main() {
    std::unordered_multiset<std::string> umset6 = {"apple", "banana", "orange", "apple"};
    std::unordered_multiset<std::string> umset7(umset6); // Sao chép từ umset6
    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_set>
#include <string>
#include <vector>

int main() {
  std::vector<std::string> vec = {"apple", "banana", "orange", "apple"};
  std::unordered_multiset<std::string> umset8(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_set>
#include <string>

int main() {
    std::unordered_multiset<std::string> umset9 = {"apple", "banana", "orange", "apple"};
    std::unordered_multiset<std::string> umset10(std::move(umset9)); // Di chuyển từ umset9 (umset9 sẽ rỗng sau đó)
    return 0;
}

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

#include <unordered_set>
#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_multiset<std::string, MyHash, MyEqual> umset12;
  return 0;
}

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

Ngoài các kiểu dữ liệu cơ bản như int, float, double, ..., std::unordered_multiset 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. Dưới đây là một số ví dụ về các kiểu dữ liệu mà std::unordered_multiset có thể chứa:

Con trỏ:
- int*, float*, double*
- char* (C-style strings) - Cần cẩn thận với việc so sánh, băm (hash) 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 sử dụng con trỏ

std::unordered_multiset 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 và hàm băm 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::unordered_multiset bị hủy.

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

std::string: Chuỗi ký tự.

std::unordered_multiset<std::string> names;
names.insert("Alice");
names.insert("Bob");
names.insert("Alice"); // Cho phép trùng lặp

Containers: Bao gồm std::vector, std::list, std::deque, std::array, std::set, std::map, std::multiset, std::multimap, std::unordered_multiset (chính nó), std::forward_list, ... (với lưu ý về việc băm và so sánh bằng).

std::unordered_multiset<std::vector<int>> umset_of_vectors; // Cần cung cấp hàm băm và so sánh bằng cho std::vector
std::unordered_multiset<std::list<int>> umset_of_lists;     // Cần cung cấp hàm băm và so sánh bằng cho std::list

std::pair và std::tuple: (với lưu ý về việc băm và so sánh bằng).

std::unordered_multiset<std::pair<int, std::string>> umset_of_pairs;   // Cần cung cấp hàm băm và so sánh bằng
std::unordered_multiset<std::tuple<int, float, char>> umset_of_tuples; // Cần cung cấp hàm băm và so sánh bằng

Các kiểu khác: std::complex, std::bitset,...

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

Bạn cần cung cấp hàm băm (hash function) và hàm so sánh bằng (equality comparison function) tùy chỉnh cho các kiểu dữ liệu này nếu muốn sử dụng chúng làm phần tử trong std::unordered_multiset.
Thư viện chuẩn C++ cung cấp mặc định cho std::pair và std::tuple (từ C++11) một hàm băm std::hash (trong <functional>) và một hàm so sánh bằng std::equal_to (trong <utility> và <tuple>) dựa vào std::hash và == của từng thành phần tương ứng, theo thứ tự.
Một số container như std::list và std::forward_list không có hash function mặc định, bạn phải cung cấp.

Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs): Bạn có thể tạo std::unordered_multiset 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ằng (Equality Comparable): 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 bằng tùy chỉnh (equality comparison function object) khi khai báo std::unordered_multiset.
- Phải có hàm băm (Hashable): Bạn cần cung cấp một hàm băm (hash function) tùy chỉnh để std::unordered_multiset có thể tính toán giá trị băm cho các đối tượng của bạn.
- CopyConstructible: Có copy constructor.
- Destructible: Có destructor.
- MoveConstructible (từ C++11): Nên có, để tối ưu hiệu suất.
- MoveAssignable (từ C++11): Nên có, để tối ưu hiệu suất.
- CopyAssignable: Nên có, để tối ưu hiệu suất.
```
#include <unordered_set>
#include <string>
#include <functional>

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
  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_multiset<Person> people;
  people.insert(Person("Alice", 30));
  people.insert(Person("Bob", 25));
  people.insert(Person("Charlie", 35));
  people.insert(Person("Alice", 30)); // Thêm trùng lặp

  return 0;
}
```

Smart Pointers (từ C++11): Bạn có thể sử dụng std::unordered_multiset để 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 bằng và hàm băm tùy chỉnh.
Với std::shared_ptr: std::shared_ptr có hỗ trợ hash function mặc định std::hash và so sánh bằng, nên bạn có thể sử dụng std::unordered_multiset với std::shared_ptr mà không cần cung cấp gì thêm (nhưng hãy cẩn thận về ý nghĩa của việc so sánh này, thường là so sánh địa chỉ).

#include <unordered_set>
#include <memory>
#include <iostream>

// Hàm so sánh bằng cho unique_ptr<int>
struct UniquePtrEqual {
  bool operator()(const std::unique_ptr<int>& a, const std::unique_ptr<int>& b) const {
    return *a == *b;
  }
};

// Hàm băm cho unique_ptr<int>
struct UniquePtrHash {
  std::size_t operator()(const std::unique_ptr<int>& ptr) const {
    return std::hash<int>()(*ptr);
  }
};

int main() {
  std::unordered_multiset<std::unique_ptr<int>, UniquePtrHash, UniquePtrEqual> umset_of_unique_ptrs;
  umset_of_unique_ptrs.insert(std::make_unique<int>(5));
  umset_of_unique_ptrs.insert(std::make_unique<int>(2));
  umset_of_unique_ptrs.insert(std::make_unique<int>(5));

  std::unordered_multiset<std::shared_ptr<int>> umset_of_shared_ptrs;
  umset_of_shared_ptrs.insert(std::make_shared<int>(10));
  umset_of_shared_ptrs.insert(std::make_shared<int>(3));
  umset_of_shared_ptrs.insert(std::make_shared<int>(3));

  return 0;
}

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


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

Dung lượng (Capacity)


empty	Kiểm tra xem std::unordered_multiset có rỗng hay không
size	Trả về số lượng phần tử hiện có trong std::unordered_multiset
max_size	Trả về số lượng phần tử tối đa mà std::unordered_multiset 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_multiset
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_multiset
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::unordered_multiset
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_multiset

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


find	Tìm kiếm một phần tử có giá trị bằng với giá trị cho trước trong std::unordered_multiset
count	Đếm số lượng phần tử có giá trị bằng với giá trị cho trước trong std::unordered_multiset
equal_range	Trả về một cặp iterator xác định phạm vi các phần tử trong std::unordered_multiset có giá trị 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 trực tiếp trong std::unordered_multiset
emplace_hint	Xây dựng (construct) một phần tử mới trực tiếp trong std::unordered_multiset với một gợi ý (hint)
insert	Chèn một hoặc nhiều phần tử mới vào std::unordered_multiset
erase	Xóa một hoặc nhiều phần tử khỏi std::unordered_multiset
clear	Xóa tất cả các phần tử khỏi std::unordered_multiset
swap	Hoán đổi nội dung của hai std::unordered_multiset 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_multiset
max_bucket_count	Trả về số lượng bucket tối đa mà std::unordered_multiset 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_multiset
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_multiset
rehash	Thiết lập số lượng bucket trong bảng băm của std::unordered_multiset thành ít nhất `count`
reserve	Yêu cầu thay đổi số lượng phần tử mà std::unordered_multiset 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_multiset
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_multiset để 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_multiset


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

Tham số​

Key​

Hash​

Pred​

Allocator​

unordered_multiset​

Đặc điểm​

Ví dụ:​

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

Khai báo một std::unordered_multiset 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_multiset 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:​

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

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)​