Cấu trúc dữ liệu C++ với tra cứu O (1), như hashmap của java trong stl?

Question

Có cấu trúc như vậy trong thư viện chuẩn C++ không? Tôi không có quyền truy cập vào bất cứ điều gì khác để unordered_map trong tr1 cant được sử dụng (và tăng vv).

Điều tôi có là số lượng lớn các thành phần lớp tùy chỉnh 100000+ mà tôi cần lưu trữ và truy cập chúng rất nhanh O (1) trên mức độ trung bình. Tôi không thể sử dụng mảng/vectơ vì các phần tử sẽ được lưu trữ ngẫu nhiên và tôi không biết vị trí của phần tử.

Là lựa chọn duy nhất của tôi để triển khai thực hiện băm bản đồ của riêng bạn chỉ với thư viện chuẩn C++?

Answer 1

Vấn đề là tra cứu O (1) không phải là tiêu chuẩn. Tôi không chắc chắn về những gì tăng có, nhưng một số triển khai STL (như sgi) có hash_map. Đó là những gì bạn cần.

Đây là documentation.

Chỉ cần thử:

#include <hash_map> 

Hãy ghi nhớ nếu công trình này, nó không phải là cầm tay ... nhưng có lẽ bây giờ đó là ok, và sau đó bạn có thể tìm cách giải quyết.

Answer 2

Tại sao bạn không thể sử dụng Boost? Thư viện bộ sưu tập Unordered là "Header only", nghĩa là bạn không phải kéo quá trình xây dựng và cài đặt BJam của Boost. Bạn chỉ có thể lấy các tệp .hpp và thêm chúng vào dự án của bạn.

Answer 3

Mặc định STL trong tiêu chuẩn hiện tại không có O (1) container tra cứu.

Answer 4

Cũng như hash_map trong một số STL, hãy tìm kiếm unordered_map (đó là những gì nó sẽ được gọi và/hoặc được gọi trong phiên bản TR1 của C++).

Answer 5

Bạn có thể sử dụng vùng chứa unordered_map. Của nó trong tr1 và sẽ được trong tiêu chuẩn đầy đủ tiếp theo. Visual Studio có một thực hiện của nó trong <unordered_map> và tài liệu có thể được tìm thấy ở đây: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 6

hash_map là một phần của phần mở rộng SGI cho STL. Trong GCC, bạn có thể sử dụng nó bằng cách làm như sau; Tôi không biết về các triển khai khác:

#include <ext/hash_map> 

using __gnu_cxx::hash_map; 

hash_map<int,string> foo; // or whatever 

unordered_map là một phần của TR1. Trong GCC, bạn có thể sử dụng nó bằng cách làm như sau; Tôi không biết về hiện thực khác:

#include <tr1/unordered_map> 

using std::tr1::unordered_map; 

unordered_map<int,string> foo; // or whatever 

Answer 7

Nếu bạn đang thực sự hạn chế std:: và không thể sử dụng bất cứ điều gì khác, std::map là đặt cược tốt nhất của bạn. Điều này chỉ cung cấp cho bạn thời gian tra cứu logarit, không phải là hằng số, nhưng so với mảng/vec-tơ, nó sẽ nhanh hơn. Ngoài ra tôi đoán cho chỉ 100000 yếu tố tra cứu logarit sẽ được đủ nhanh và bạn sẽ không giành chiến thắng nhiều bằng cách sử dụng một bảng băm.

Điều đó đang được nói, rất có thể là việc triển khai của bạn đã bao gồm một số triển khai bảng băm.Vì vậy, nếu std::map thực sự là không đủ nhanh, hãy thử

#include <tr1/unordered_map> 
std::tr1::unordered_map<int,int> test; 

hoặc

#include <hash_map> 
stdext::hash_map<int,int> test; 

hoặc thậm chí

#include <boost/tr1/unordered_map.hpp> 
std::tr1::unordered_map<int,int> test;