hash_map — Klasa

Artykuł
06/09/2015

[!UWAGA]

Ten interfejs API jest nieaktualny.Alternatywą jest unordered_map — Klasa.

Przechowuje i pobiera dane szybko z kolekcji, w której każdy element jest para, którego wartością jest unikatowy klucz sortowania oraz wartości skojarzonych danych.

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

Parametry

Key
Typ danych klucza mają być przechowywane w hash_map.
Type
Typ elementu danych mają być przechowywane w hash_map.
Traits
Z typem, który obejmuje dwa obiekty funkcji, jednym z klasy Porównaj zdolne do porównywania dwóch wartości elementu jako klucze sortowania do określenia ich względną kolejność i wartość mieszania funkcji, który jest predykatu jednoelementowego mapowanie wartości klucza elementów do liczb całkowitych bez znaku typu size_t.Ten argument jest opcjonalny, a hash_compare<Key, mniej<Key>> jest wartością domyślną.
Allocator
Typ, który reprezentuje obiekt przechowywanych alokatora hermetyzuje szczegóły dotyczące alokacji i dezalokacji pamięci hash_map.Ten argument jest opcjonalny, a wartość domyślna to program przydzielania<para <const Key, Type>>.

Uwagi

Hash_map jest:

Skojarzeniowym kontenerem, który jest kontenerem o zmiennym rozmiarze, obsługującym efektywne pobieranie wartości elementu w oparciu o wartość skojarzonego klucza.
Odwracalny, ponieważ zapewnia dwukierunkowy iterator do dostępu do jego elementów.
O wartości skrótu, ponieważ jego elementy są pogrupowane w przedziały na podstawie wartości funkcji skrótu zastosowanej do wartości kluczy elementów.
Unikatowe w tym sensie, że każdy z jej elementów musi mieć unikatowy klucz.
Para kontenera asocjacyjnych, ponieważ jego wartości elementów danych różnią się od jej wartości klucza.
Klasą szablonową, ponieważ funkcjonalność, którą zapewnia jest generyczna i niezależna od określonego typu danych zawartych jako elementy lub klucze.Typy danych, których można użyć dla elementów i kluczy są za to określane jako parametry w szablonie klasy, wraz z funkcją porównania oraz alokatorem.

Główną zaletą tworzenia wartości skrótu nad sortowaniem jest większa wydajność; pomyślne skrócenie wykonuje wstawienia, usuwania i wyszukuje w stałym średnim czasie, w porównaniu do czasu proporcjonalnego do logarytmu liczby elementów w kontenerze dla technik sortowania.Wartość elementu w hash_map, ale nie jego skojarzony wartości klucza, mogą być zmieniane bezpośrednio.W zamian, wartości kluczy skojarzone ze starymi elementami muszą zostać usunięte, a nowe wartości klucza skojarzone ze wstawionymi elementami.

Wybór typu kontenera powinien być oparty o typ wyszukiwania i wstawiania wymagany przez aplikację.Skojarzone kontenery skrótów są zoptymalizowane dla operacji wyszukiwania, wstawiania oraz usuwania.Funkcje składowe, jawnie obsługujące te operacje są skuteczne, gdy są używane z dobrze zaprojektowaną funkcją skrótu, wykonując je w średnim stałym czasie i niezależnie od liczby elementów w kontenerze.Dobrze zaprojektowana funkcja skrótu wytwarza równomierny rozkład skrótowych wartości i minimalizuje liczbę kolizji, gdzie kolizja występuje, gdy różne wartości kluczy są mapowane do tej samej skróconej wartości.W najgorszym przypadku, z najgorszą możliwą funkcją skrótu, liczba operacji jest proporcjonalna do liczby elementów w sekwencji (czas liniowy).

Hash_map powinny być zespolone opakowania z wyboru, po spełnieniu warunków z wartości otrzymanych z klawiszy przez aplikację.Model dla tego typu konstrukcji jest uporządkowana lista jednoznacznie występujące słowa kluczowe z wartościami ciąg skojarzone dostarczanie, powiedz, definicje.Jeśli zamiast tego słowa miał więcej niż jedną definicję poprawne, tak, aby nie były unikatowe klucze, hash_multimap będzie opakowania z wyboru.Jeśli z drugiej strony, przechowywana była tylko lista wyrazów, poprawnym kontenerem będzie hash_set.Jeżeli zezwolono na wiele wystąpień wyrazów, odpowiednią strukturą kontenera będzie hash_multiset.

Hash_map zamówień sekwencji kontroluje wywołując przechowywane mieszania Traits obiekt klasy value_compare.Dostęp do tego przechowywanego obiektu można uzyskać, wywołując funkcję członkowską key_comp.Obiekt funkcji muszą zachowywać się taki sam, jak obiekt klasy hash_compare<klucz, mniej<klucz>>.W szczególności, dla wszystkich wartości Key typu Key, wywołanie Traits(Key ) daje w wyniku rozkład wartości typu size_t.

Ogólnie rzecz biorąc, elementy muszą być nieco mniej porównywalne, aby ustalić kolejność: tak aby, mając dowolne dwa elementy, można było określić, czy są one równoważne (w sensie, żaden nie jest mniejszy niż ten drugi) lub, że jeden jest mniejszy niż ten drugi.Powoduje porządkowanie między elementami nonequivalent.Ze strony bardziej technicznej, funkcja porównania jest predykatem dwuargumentowym, który wymusza ścisłe słabe porządkowanie w standardowym sensie matematycznym.Binarne f(x y) predykatu jest obiekt funkcji, która ma dwa obiekty argument x i y i wartością zwracaną true lub false.Kolejność nałożonych na hash_map jest ścisłe słaby zamawiania Jeśli predykat dwuelementowy jest niezwrotne, antysymetryczna i przechodnie i jeśli równoważność jest przechodnie, gdzie obydwa obiekty x i y są zdefiniowane jako równoważne, gdy zarówno f (x, y) i f (y, x) są fałszywe.Jeśli silniejszy warunek równości pomiędzy kluczami zastąpi ten równoważności, to porządkowanie będzie całkowite (w sensie, że wszystkie elementy są uporządkowane względem siebie), a dopasowane klucze będą od siebie nieodróżnialne.

Rzeczywista kolejność elementów w kontrolowanej sekwencji zależy od funkcji skrótu, funkcji porządkowania i bieżącego rozmiaru tabeli skrótu przechowywanej w obiekcie kontenera.Nie można określić bieżącego rozmiaru tabeli skrótu, więc nie da się ogólnie przewidzieć uporządkowania elementów w kontrolowanej sekwencji.Wstawianie elementów nie unieważnia iteratorów, a usuwanie elementów unieważnia tylko te iteratory, które w szczególności wskazywały na usunięte elementy.

Sterująca dostarczonych przez klasę hash_map jest sterująca dwukierunkowe, ale funkcje składowe klasy Wstaw i hash_map wersje, które biorą za parametry szablonu słabsze sterująca wejściowego, których wymogi dotyczące funkcjonalności są bardziej minimalne niż gwarantowana przez klasę Iteratory dwukierunkowego.Pojęcia innych iteratorów formują rodzinę powiązanych przez udoskonalenia w swoich funkcjonalnościach.Każde pojęcie sterująca ma swój własny zestaw wymagań i algorytmów, które działają z nimi musi ograniczyć ich założeń z wymaganiami określonymi przez ten rodzaj iteratora.Można założyć, że z iteratora wejściowego można usunąć odwołanie, aby odwołać się do obiektu, a także, że może ono być zwiększone do następnego iteratora w sekwencji.Jest to minimalny zestaw funkcji, ale wystarczy, aby można było mówić przydatnie o szereg Iteratory [First, Last) w kontekście funkcji elementów członkowskich klasy.

W Visual C++ .NET 2003, elementy członkowskie plików nagłówka <hash_map> i <hash_set> nie są już w przestrzeni nazw std, ale raczej zostały przeniesione do przestrzeni nazw stdext.Zobacz Przestrzeń nazw stdext, aby uzyskać więcej informacji.

Konstruktorów

hash_map

Konstruuje hash_map, który jest pusty lub jest kopią całości lub części innego hash_map.

Typedefs

allocator_type	Typ, który reprezentuje klasę allocator obiektu hash_map.
const_iterator	Typ, który dostarcza iterator dwukierunkowy, który może odczytać element const w hash_map.
const_pointer	Typ, który dostarcza wskaźnik do elementu const w hash_map.
const_reference	Typ, który dostarcza odwołanie do elementu const przechowywanego w hash_map do odczytu i wykonywania operacji const.
const_reverse_iterator	Typ, który dostarcza iterator dwukierunkowy, który może odczytać dowolny element const w hash_map.
difference_type	Typ liczby całkowitej ze znakiem, który może służyć do reprezentowania liczby elementów hash_map w zakresie pomiędzy elementami wskazywanymi przez iteratory.
iterator	Typ, który dostarcza iterator dwukierunkowy do odczytu i modyfikacji dowolnego elementu w hash_map.
key_compare	Typ, który dostarcza obiekt funkcji, która może porównać dwa klucze sortowania, aby określić względną kolejność dwóch elementów w hash_map.
key_type	Opisuje typ obiektu klucz sortowania, który stanowi każdy element hash_map.
mapped_type	Typ, który reprezentuje typ danych przechowywanych w hash_map.
wskaźnik	Typ, który zawiera wskaźnik do elementu w hash_map.
odwołanie	Typ, który zawiera odwołanie do elementu przechowywanego w hash_map.
reverse_iterator	Typ, który dostarcza iterator dwukierunkowy do odczytu i modyfikacji elementu w odwróconym hash_map.
size_type	Typ liczby całkowitej bez znaku, który może reprezentować liczbę elementów w hash_map.
value_type	Typ, który dostarcza obiekt funkcji, która może porównać dwa elementy jako klucze sortowania, aby określić ich względną kolejność w hash_map.

Funkcje członkowskie

hash_map::at	Wyszukuje element w hash_map z określoną wartością klucza.
rozpocznij	Zwraca iterator adresujący pierwszy element w hash_map.
hash_map::cbegin	Zwraca stały iterator adresujący pierwszy element w hash_map.
hash_map::cend	Zwraca stały iterator adresujący lokalizację następującą po ostatnim elemencie w hash_map.
wyczyść	Usuwa wszystkie elementy ciągu hash_map.
count	Zwraca liczbę elementów w hash_map, których klucz pasuje do klucza określonego jako parametr.
hash_map::crbegin	Zwraca stały iterator adresujący pierwszy element w odwróconym hash_map.
hash_map::crend	Zwraca stały iterator adresujący lokalizację następującą po ostatnim elemencie w odwróconej hash_map.
hash_map::emplace	Wstawia element stworzony w miejscu do hash_map.
hash_map::emplace_hint	Wstawia element stworzony w miejscu do hash_map, ze wskazówką położenia.
pusty	Sprawdza, czy hash_map jest pusty.
end	Zwraca iterator adresujący lokalizację następującą po ostatnim elemencie w hash_map.
equal_range	Zwraca parę Iteratory, odpowiednio, do pierwszego elementu w hash_map za pomocą klucza, który jest większy niż określony klucz i do pierwszego elementu w hash_map za pomocą klucza, który jest równy lub większy niż ten klucz.
wymazywanie	Usuwa element lub zakres elementów w hash_map od określonej pozycji.
znajdź	Zwraca iterator adresujący lokalizację elementu w hash_map, który ma klucz równoważny z określonym kluczem.
get_allocator	Zwraca kopię obiektu allocator użytego do stworzenia hash_map.
wstaw	Wstawia element lub zakres elementów do hash_map.
key_comp	Zwraca iterację do pierwszego elementu w hash_map z wartości klucza, który jest równy lub większy niż w przypadku określonego klucza.
lower_bound	Zwraca iterację do pierwszego elementu w hash_map z wartości klucza, który jest równy lub większy niż w przypadku określonego klucza.
maksymalny rozmiar	Zwraca maksymalną długość hash_map.
rbegin	Zwraca iterator adresujący pierwszy element w odwróconym hash_map.
rend	Zwraca iterator adresujący lokalizację następującą po ostatnim elemencie w odwróconym hash_map.
rozmiar	Zwraca liczbę elementów w hash_map.
swap	Zamienia elementy z dwóch hash_map
upper_bound	Zwraca iterator do pierwszego elementu w hash_map, gdzie wartość klucza jest większa niż określonego klucza.
value_comp	Pobiera kopię obiektu porównania użytego do uporządkowania wartości elementów w hash_map.

Operatory

operator[]	Wstawia element do hash_map z określoną wartością klucza.
hash_map::operator=	Zastępuje elementy hash_map kopią innej hash_map.