Chuyển tới nội dung chính

std::unordered_map

#include <unordered_map>

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

std::unordered_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). Điểm đặc biệt của std::unordered_map là nó không lưu trữ các phần tử theo một thứ tự cụ thể nào (khác với std::map được sắp xếp theo key). Thay vào đó, nó sử dụng bảng băm (hash table) để tổ chức các phần tử, cho phép truy cập, chèn và xóa phần tử rất nhanh, với độ phức tạp trung bình là hằng số (O(1)).

Tham số​

Key​

  • Kiểu dữ liệu của key. Key phải là duy nhất và được sử dụng để truy cập đến value tương ứng.

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

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

Đặc điểm​

  1. Key duy nhất: std::unordered_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() và emplace()), hoặc value sẽ bị ghi đè (đối với operator[]).
  2. Phần tử không được sắp xếp: Các phần tử trong std::unordered_map 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.
  3. 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_map 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 map.
  4. Truy cập theo key: std::unordered_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().
  5. Iterator: std::unordered_map cung cấp iterator để duyệt qua các phần tử. Iterator của std::unordered_map là ForwardIterator.
  6. 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_map có thể bị thay đổi (invalidate) khi bạn chèn, xóa phần tử hoặc rehash.
  7. Chèn và xóa: Việc chèn và xóa phần tử trong std::unordered_map có độ phức tạp trung bình O(1).
  8. Ưu điểm:
    • Lưu trữ các phần tử theo key-value.
    • 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.
  9. 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).
  10. Khi nào nên sử dụng std::unordered_map:
    • Khi bạn cần lưu trữ các cặp key-value.
    • 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ả.
    • Khi bạn cần truy cập nhanh các phần tử theo key.
Phân biệt std::unordered_map và std::map
  • std::unordered_map: Lưu trữ các phần tử không theo thứ tự, sử dụng bảng băm.
  • 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.

Ví dụ:​

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

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

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

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

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

  // 5. 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
  }

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

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

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

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

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

  // 11. Hoán đổi nội dung 2 unordered_map
  umap1.swap(umap2);
    
  // 12. Kiểm tra sự tồn tại của key
  if(umap1.contains(3)) { // C++20
    // ...
  }

  // 13. Lấy số xô (bucket_count)
  umap1.bucket_count();
  
  // 14. Lấy bucket mà 1 key đang ở trong đó
  umap1.bucket(3);

  // 15. Lấy số phần tử trong 1 bucket
  umap1.bucket_size(0);

  // 16. equal_range()
  auto range = umap1.equal_range(3);
  for (auto it = range.first; it != range.second; ++it) {
      std::cout << it->first << ": " << it->second << '\n';
  }
  
  // 17. count()
  std::cout << umap1.count(3) << '\n';

  // 18. emplace() (C++11)
  umap1.emplace(4, "four");

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

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

  // 21. reserve() thay đổi capacity
  umap1.reserve(1000);

  return 0;
}

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

lưu ý
  • std::unordered_map 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.
  • Key trong std::unordered_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::unordered_map.
  • Khi khởi tạo std::unordered_map 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_map.
  • Khi khởi tạo std::unordered_map từ một initializer list, các key trùng lặp sẽ bị loại bỏ (giữ lại phần tử cuối cùng có key đó).

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

    #include <unordered_map>
    #include <string>

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

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

    #include <unordered_map>
    #include <string>

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

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

    #include <unordered_map>
    #include <string>

    std::unordered_map<std::string, int> umap3;
    umap3.insert(std::make_pair("apple", 1));
    umap3.insert(std::pair<std::string, int>("banana", 2)); // C++98
    umap3.insert({"orange", 3}); // C++11 initializer list trong hàm insert

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

    #include <unordered_map>
    #include <string>

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

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

    #include <unordered_map>
    #include <string>

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

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

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

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

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

    #include <unordered_map>

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

  9. 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_map<std::string, int, MyHash, MyEqual> umap11;
        return 0;
    }

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

std::unordered_map trong C++ là một container rất linh hoạt và có thể chứa nhiều kiểu dữ liệu khác nhau cho cả key và value, ngoài các kiểu dữ liệu cơ bản như int, float, double, ... . Dưới đây là phân tích chi tiết về các kiểu dữ liệu mà std::unordered_map có thể chứa:

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 (xem ví dụ bên dưới).
    • 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/MoveConstructible: Có copy constructor hoặc move constructor
    • Destructible: Có destructor
  • 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_map 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ớ).
    • std::pair và std::tuple: (từ C++11) Thư viện chuẩn C++ cung cấp mặc định cho std::pair và std::tuple 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ự.
    • Các kiểu dữ liệu chuẩn có hỗ trợ hàm băm và so sánh bằng: std::complex, std::bitset, 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.

Ví dụ về Key:​

#include <unordered_map>
#include <string>
#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_map<int, std::string> map1; // Key: int
  std::unordered_map<std::string, int> map2; // Key: std::string
  std::unordered_map<Person, double> map3; // Key: Person (với toán tử == và hàm băm đã định nghĩa)
  // std::unordered_map<std::vector<int>, int> map4; // Lỗi, std::vector không có hàm băm mặc định
  // std::unordered_map<std::list<int>, int> map5;   // Lỗi, std::list không có hàm băm mặc định

  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::unordered_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::unordered_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::unordered_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::unordered_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 và copy constructor (hoặc move constructor).
      • 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 <unordered_map>
#include <string>
#include <vector>
#include <memory>

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

  return 0;
}

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

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

Dung lượng (Capacity)​

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

Trình lặp (Iterators)​

beginTrả về một iterator trỏ đến phần tử đầu tiên trong std::unordered_map
endTrả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_map
cbeginTrả về một const_iterator trỏ đến phần tử đầu tiên trong std::unordered_map
cendTrả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::unordered_map

Truy cập phần tử​

[]Truy cập phần tử có key tương ứng
atTruy cập phần tử có key cho trước

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

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

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

emplaceXây dựng (construct) một phần tử mới (cặp key-value) trực tiếp trong std::unordered_map tại vị trí thích hợp
emplace_hintXây dựng (construct) một phần tử mới (cặp key-value) trực tiếp trong std::unordered_map với một gợi ý (hint)
insertChèn một phần tử mới (cặp key-value) vào std::unordered_map
eraseXóa một hoặc nhiều phần tử khỏi std::unordered_map
clearXóa tất cả các phần tử khỏi std::unordered_map
swapHoán đổi nội dung của hai std::unordered_map với nhau

Buckets​

bucket_countTrả về số lượng bucket (hay còn gọi là giỏ) hiện tại trong std::unordered_map
max_bucket_countTrả về số lượng bucket tối đa mà std::unordered_map có thể có
bucket_sizeTrả về số lượng phần tử hiện có trong một bucket cụ thể
bucketTrả 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_factorTrả về hệ số tải (load factor) hiện tại của std::unordered_map
max_load_factorTruy vấn hoặc thiết lập hệ số tải tối đa (maximum load factor) của std::unordered_map
rehashThiết lập số lượng bucket trong bảng băm của std::unordered_map thành ít nhất count
reserveThay đổi số lượng phần tử mà std::unordered_map có thể chứa mà không cần phải rehash

Quan sát (Observers)​

hash_functionTrả về một bản sao của hàm băm đang được sử dụng bởi std::unordered_map
key_eqTrả về một bản sao của hàm so sánh bằng được sử dụng bởi std::unordered_map để kiểm tra xem hai key có bằng nhau hay không
get_allocatorTrả về một bản sao của bộ cấp phát (allocator) được liên kết với std::unordered_map

Toán tử quan hệCác toán tử quan hệ trong std::unordered_map
Cập nhật lần cuối vào bởi yutijang

 2025 © cppDocs. Built with Docusaurus.