Hashtable trong C++?

Question

Tôi thường sử dụng bản đồ stdlib C++ bất cứ khi nào tôi cần lưu trữ một số dữ liệu được liên kết với một loại giá trị cụ thể (giá trị khóa - ví dụ: một chuỗi hoặc đối tượng khác). Việc triển khai bản đồ stdlib dựa trên các cây cung cấp hiệu suất tốt hơn (O (log n)) so với mảng tiêu chuẩn hoặc vector stdlib.

Câu hỏi của tôi là, bạn có biết bất kỳ triển khai có thể thực hiện nào có hiệu năng tốt hơn (O (1)) của C++ "chuẩn" hay không. Một cái gì đó tương tự như những gì có sẵn trong lớp Hashtable từ API Java.

Answer 1

Nếu bạn đang sử dụng C++ 11, bạn có quyền truy cập vào các tiêu đề <unordered_map> và <unordered_set>. Chúng cung cấp các lớp học std::unordered_map và std::unordered_set.

Nếu bạn đang sử dụng C++ 03 với TR1, bạn có quyền truy cập vào các lớp std::tr1::unordered_map và std::tr1::unordered_set, sử dụng các tiêu đề tương tự (trừ khi bạn đang sử dụng GCC, trong trường hợp các tiêu đề là <tr1/unordered_map> và <tr1/unordered_set> thay).

Trong mọi trường hợp, cũng có các loại tương ứng unordered_multimap và unordered_multiset.

Answer 2

std::hash_map

Answer 3

Xem std::hash_map từ SGI.

Điều này cũng được bao gồm trong phân phối STLPort.

Answer 4

Có một đối tượng hash_map như nhiều ở đây đã đề cập, nhưng nó không phải là một phần của stl. Nó là một phần mở rộng SGI, vì vậy nếu bạn đang tìm kiếm một cái gì đó trong STL, tôi nghĩ rằng bạn đang ra khỏi may mắn.

Answer 5

Visual Studio có lớp stdext::hash_map trong tiêu đề <hash_map> và gcc có lớp __gnu_cxx::hash_map trong cùng một tiêu đề.

Answer 6

hash_map cũng được hỗ trợ trong GNU libstdc++.

Dinkumware cũng supports điều này, có nghĩa là nhiều triển khai sẽ có hash_map (tôi nghĩ ngay cả Visual C++ cung cấp với Dinkumware).

Answer 7

Nếu bạn chưa có unordered_map hoặc unordered_set, chúng là một phần của boost.
Here's the documentation for both.

Answer 8

Nếu bạn có phần mở rộng TR1 có sẵn cho trình biên dịch yor, hãy sử dụng chúng. Nếu không, boost.org có một phiên bản khá giống ngoại trừ std :: namespace. Trong trường hợp đó, hãy đưa vào khai báo sử dụng để bạn có thể chuyển sang std :: later.

Answer 9

std :: tr1 :: unordered_map, trong <unordered_map>

nếu bạn không có tr1, có tăng, và sử dụng boost :: unordered_map trong <boost/unordered_map.hpp>