Struktura danych C++ z czasem wyszukiwania O (1), podobnie jak hashmap java w STL?

Question

Czy istnieje taka struktura w standardowej bibliotece C++? Nie mam dostępu do niczego innego, więc nieużywana_mapa nie może być używana (i zwiększać itp.).

Co mam, to duża liczba niestandardowych elementów klasy 100000+, które muszę przechowywać i uzyskać do nich bardzo szybki dostęp do O (1). Nie mogę używać tablic/wektorów, ponieważ elementy będą przechowywane losowo i nie znam pozycji elementu.

Czy moja jedyna alternatywa dla implementacji własnej implementacji hashmap z dostępną tylko biblioteką standardową C++?

Answer 1

Problem polega na tym, że wyszukiwanie O (1) nie jest standardem. Nie jestem pewien, co ma na celu zwiększenie, ale niektóre implementacje STL (jak sgi) mają hash_map. Tego właśnie potrzebujesz.

Oto documentation.

Wystarczy wypróbować:

#include <hash_map> 

Pamiętaj, jeśli działa, to nie jest przenośny ... ale może na razie to jest ok, a później można znaleźć rozwiązania.

Answer 2

Dlaczego nie możesz użyć funkcji Boost? Biblioteka zbiorów Unordered to "Tylko nagłówek", co oznacza, że ​​nie musisz pobierać procesu budowania BJam i instalatora Boost. Możesz po prostu pobrać pliki .hpp i dodać je do swojego projektu.

Answer 3

Domyślny STL w aktualnym standardzie nie ma kontenerów wyszukiwania O (1).

Answer 4

Podobnie jak hash_map w niektórych listach STL, poszukaj unordered_map (jak to się nazywa i/lub jest wywoływana w wersji TR1 C++).

Answer 5

Możesz użyć kontenera unordered_map. Jest w tr1 i będzie w następnym pełnym standardzie. Visual Studio ma wdrożenie go w <unordered_map> i dokumentację można znaleźć tutaj: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 6

hash_map jest częścią rozszerzenia SGI do STL. W GCC można go użyć, wykonując następujące czynności; Nie wiem o innych wdrożeniach:

#include <ext/hash_map> 

using __gnu_cxx::hash_map; 

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

unordered_map jest częścią TR1. W GCC można go użyć, wykonując następujące czynności; Nie wiem o innych implementacjach:

#include <tr1/unordered_map> 

using std::tr1::unordered_map; 

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

Answer 7

Jeśli naprawdę ograniczone do std:: i nie można używać niczego innego, std::map jest najlepszym. Daje to tylko logarytmiczny czas wyszukiwania, a nie stały, ale w porównaniu z tablicami/wektorami będzie on niesamowicie szybki. Sądzę też, że w przypadku zaledwie 100000 elementów logarytmiczne wyszukiwanie będzie wystarczająco szybkie i nie wygrasz dużo, używając tabeli mieszania.

W związku z tym istnieje duże prawdopodobieństwo, że implementacja obejmuje już implementację tablic asocjacyjnych.Więc jeśli std::map naprawdę nie jest wystarczająco szybki, spróbuj

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

lub

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

lub nawet

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