Chciałbym zapisać mapowanieinteger klucz do afloat wartość w pamięci.

Mam około 130 milionów kluczy (i odpowiednio 130 milionów wartości).

Koncentruję się na wydajności wyszukiwania - muszę wykonywać wiele, wiele milionów wyszukiwań.

Biblioteka C ++ STL mamap klasa dla tablic asocjacyjnych tego rodzaju. Mam kilka pytańmap.

Jaki jest narzut pamięci masowejmap dla zestawu danych o rozmiarze wspomnianym powyżej? Jak ogólnie skaluje się pamięć masowa zmap?

Wygląda jak podstawowa struktura danych dlamap jest czerwono-czarnym, zrównoważonym drzewem binarnym. To brzmi jak prawdziwy światwydajność na to jestO(log n) do wstawiania i pobierania.

WspominaO(1) za podpowiedź. Moje dane wejściowe są wstępnie posortowane, więc uważam, że powinienem być w stanie podać podpowiedź dotyczącą zdarzeń wstawiania. Jak zapewniłbym tę wskazówkę, używając wymienionych metodtutaj?

Czy istnieje kontener STL, który zapewnia lepszą wydajność wyszukiwania?

Czy istnieją inne publicznie dostępne struktury open source ze skojarzoną klasą tablicową, która używa podstawowej struktury danych, która działałaby lepiej niż STLmap?

Jeśli napisanie własnej klasy kontenera zapewniłoby lepszą wydajność wyszukiwania, jakie struktury danych mógłbym badać?

Do tego zadania używam GCC 4, działającego w systemie Linux lub Mac OS X.

Z góry przepraszam, jeśli są to głupie pytania. Dziękuję za radę.