std::unordered_set

#include <unordered_set>

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

std::unordered_set trong C++ là một container liên kết (associative container) lưu trữ các phần tử duy nhất (unique), không theo thứ tự cụ thể nào. 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_set.

`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_set`

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

Đặc điểm

Phần tử duy nhất: std::unordered_set chỉ lưu trữ các phần tử duy nhất. Nếu bạn cố gắng chèn một phần tử đã tồn tại, thao tác chèn sẽ bị bỏ qua.
Phần tử không được sắp xếp: Các phần tử trong std::unordered_set 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_set 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_set 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_set 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 unordered_set.
Chèn và xóa hiệu quả: Việc chèn và xóa phần tử trong std::unordered_set cũng có độ phức tạp trung bình O(1).
Ưu điểm:
- Lưu trữ các phần tử duy nhất.
- 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_set:
- Khi bạn cần lưu trữ một tập hợp các phần tử duy nhất.
- 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::set

std::unordered_set: Lưu trữ các phần tử không theo thứ tự, sử dụng bảng băm.
std::set: Lưu trữ các phần tử được sắp xếp, sử dụng cây tìm kiếm nhị phân.

Ví dụ:

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

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

  // 2. Chèn phần tử vào unordered_set
  set1.insert("apple");
  set1.insert("banana");
  set1.insert("orange");
  set1.insert("apple"); // Phần tử trùng lặp sẽ bị bỏ qua

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

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

  // 5. Xóa phần tử
  set1.erase("banana");

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

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

  // 8. Khai báo và khởi tạo với initializer list (C++11)
  std::unordered_set<int> set2 = {1, 2, 3, 4, 5, 1, 2}; // Các phần tử trùng lặp sẽ bị bỏ qua

  // 9. Xóa tất cả các phần tử
  set1.clear();
  
  // 10. Kiểm tra sự tồn tại của phần tử (C++20)
  if (set2.contains(3))
  {
      std::cout << "set2 contains 3\n";
  }

  // 11. Hoán đổi nội dung 2 unordered_set
  set1.swap(set2);

  // 12. Lấy số xô (bucket_count)
  set1.bucket_count();
  
  // 13. Lấy bucket mà 1 phần tử đang ở trong đó
  set1.bucket(3);

  return 0;
}

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

lưu ý

std::unordered_set 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_set chỉ lưu trữ các phần tử duy nhất. Các phần tử trùng lặp sẽ bị bỏ qua.
Khi khởi tạo std::unordered_set 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_set.
Khi khởi tạo std::unordered_set từ một initializer list, các phần tử trùng lặp sẽ bị loại bỏ.

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

#include <unordered_set>
#include <string>

std::unordered_set<std::string> set1; // unordered_set rỗng, kiểu std::string
std::unordered_set<int> set2;         // unordered_set 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_set<std::string> set3 = {"apple", "banana", "orange", "apple"}; // "apple" lặp lại sẽ bị loại bỏ
std::unordered_set<int> set4 = {3, 1, 4, 1, 5, 9, 2, 6}; // Khởi tạo và bỏ qua 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_set<std::string> set5;
set5.insert("apple");
set5.insert("banana");
set5.insert("orange");
set5.insert("apple"); // Phần tử trùng lặp sẽ bị bỏ qua

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

#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> set6 = {"apple", "banana", "orange"};
    std::unordered_set<std::string> set7(set6); // Sao chép từ set6
    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_set<std::string> set8(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_set<std::string> set9 = {"apple", "banana", "orange"};
    std::unordered_set<std::string> set10(std::move(set9)); // Di chuyển từ set9 (set9 sẽ rỗng sau đó)
    return 0;
}

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

#include <unordered_set>

std::unordered_set<int> set11(100); // Khởi tạo với ít nhất 100 xô

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

#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_set<std::string, MyHash, MyEqual> set12;
  return 0;
}

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

Ngoài các kiểu dữ liệu cơ bản như int, float, double,..., std::unordered_set 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 về so sánh bằng (toán tử == hoặc hàm so sánh tùy chỉnh), hàm băm, và các ràng buộc khác như CopyConstructible/MoveConstructible, Destructible. Khi sử dụng các kiểu dữ liệu phức tạp, hãy đảm bảo rằng bạn đã định nghĩa cách so sánh bằng và hàm băm phù hợp để std::unordered_set có thể hoạt động chính xác. Dưới đây là một số ví dụ về các kiểu dữ liệu mà std::unordered_set 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 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_set 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_set bị hủy.

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

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

std::unordered_set<std::string> names;
names.insert("Alice");
names.insert("Bob");
names.insert("Alice"); // Bị bỏ qua vì 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_set (chính nó), std::forward_list, ... (với lưu ý về việc băm và so sánh bằng).

std::unordered_set<std::vector<int>> set_of_vectors; // Cần cung cấp hàm băm và so sánh bằng cho std::vector
std::unordered_set<std::list<int>> set_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_set<std::pair<int, std::string>> set_of_pairs;   // Cần cung cấp hàm băm và so sánh bằng
std::unordered_set<std::tuple<int, float, char>> set_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_set.
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_set 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_set.
- 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_set 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_set<Person> people;
  people.insert(Person("Alice", 30));
  people.insert(Person("Bob", 25));
  people.insert(Person("Charlie", 35));
  people.insert(Person("Alice", 30)); // Bị bỏ qua vì trùng lặp

  return 0;
}
```

Smart Pointers (từ C++11):
Bạn có thể sử dụng std::unordered_set để 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_set 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_set<std::unique_ptr<int>, UniquePtrHash, UniquePtrEqual> set_of_unique_ptrs;
  set_of_unique_ptrs.insert(std::make_unique<int>(5));
  set_of_unique_ptrs.insert(std::make_unique<int>(2));

  std::unordered_set<std::shared_ptr<int>> set_of_shared_ptrs;
  set_of_shared_ptrs.insert(std::make_shared<int>(10));
  set_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_set khác hoặc một initializer_list cho std::unordered_set hiện tại

Dung lượng (Capacity)


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

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


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

Tham số​

Key​

Hash​

Pred​

Allocator​

unordered_set​

Đặc điểm​

Ví dụ:​

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

Khai báo một std::unordered_set 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_set 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 xô (buckets) 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_set​

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