hash_multimap — Klasa

Artykuł
06/09/2015

[!UWAGA]

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

Klasa kontenera hash_multimap jest rozszerzeniem standardowej biblioteki szablonów (STL) i jest używana do przechowywania i szybkiego pobierania danych z kolekcji, w której każdy element jest parą posiadającą klucz sortowania, którego wartość nie musi być unikalna, oraz skojarzoną wartość danych.

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

Parametry

Key
Typ danych klucza, który będzie przechowywany w hash_multimap.
Type
Typ danych elementu, który będzie przechowywany w hash_multimap.
Traits
Typ, który zawiera dwa obiekty funkcji, jeden z klasy Traits, porównujący wartości dwuelementowe jako klucze sortowania, aby ustalić ich względną kolejność, oraz drugi, czyli funkcję skrótu, która jest jednoargumentowym predykatem wartości klucza mapowania elementów do typu liczby całkowitej bez znaku size_t.Ten argument jest opcjonalny, a jego wartością domyślną jest hash_compare<Key, less<Key> >.
Allocator
Typ reprezentujący przechowywany obiekt alokatora, który hermetyzuje szczegóły dotyczące alokacji i dezalokacji pamięci hash_multimap.Ten argument jest opcjonalny, a jego wartością domyślną jest allocator<pair <const Key, Type> >.

Uwagi

Hash_multimap 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.
Wielokrotny, ponieważ jego elementy nie muszą mieć unikatowych kluczy, więc jedna wartość klucza może mieć wiele wartości elementów danych z nią skojarzonych.
Kontenerem skojarzonych par, ponieważ jego wartości elementu różnią się od 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_multimap, lecz nie wartość jego skojarzonego klucza, może być zmieniona 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_multimap powinno być skojarzonym kontenerem z wyboru, gdy warunki kojarzenia wartości z kluczami są spełnione przez aplikację.Modelem dla tego typu struktury jest uporządkowana lista słów kluczowych ze skojarzonymi wartościami ciągów, dostarczające, powiedzmy, definicje, w których słowa nie były zawsze zdefiniowane unikalnie.Jeśli zamiast tego słowa kluczowe zostały unikalnie zdefiniowane, tak że klucze są unikalne, wybranym kontenerem będzie hash_map.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_multimap porządkuje kontrolowaną sekwencję, wywołując przechowywany obiekt skrótu Traits typu value_compare.Dostęp do tego przechowywanego obiektu można uzyskać, wywołując funkcję członkowską key_comp.Taki obiekt funkcji musi zachowywać się tak samo jak obiekt klasy hash_compare<Key, less<Key> >.W szczególności, dla wszystkich wartości Key typu Key, wywołanie Traits (Key) implikuje dystrybucję 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.W wyniku tego ustalona zostanie kolejność między nierównoważnymi elementami.Ze strony bardziej technicznej, funkcja porównania jest predykatem dwuargumentowym, który wymusza ścisłe słabe porządkowanie w standardowym sensie matematycznym.Dwuargumentowy predykat f(x, y) jest obiektem funkcji, który posiada dwa obiekty argumentowe x i y i wartość zwracaną true lub false.Kolejność nałożona na hash_multimap jest ścisłym słabym porządkowaniem, jeśli dwuargumentowy predykat jest niezwrotny, przeciwsymetryczny i przechodni oraz jeśli równoważność jest przechodnia, gdzie dwa obiekty x i y są określone jako równoważne, gdy f(x, y) oraz f(y, x) są false.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.

Iterator dostarczony przez klasę hash_multimap jest iteratorem dwukierunkowym, ale funkcje członkowskie klasy insert i hash_multimap posiadają wersje przyjmujące jako parametry szablonu słabszy iterator wejściowy, którego wymagania funkcjonalności są mniejsze niż te gwarantowane przez klasę iteratorów dwukierunkowych.Pojęcia innych iteratorów formują rodzinę powiązanych przez udoskonalenia w swoich funkcjonalnościach.Każde pojęcie iteratora ma swoją własną hash_multimap wymagań, a algorytmy z nimi pracujące muszą ograniczać swoje założenia co do wymagań dostarczonych przez tego typu iterator.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 minimalna funkcjonalność hash_multimap, ale jest wystarczająca, aby można było mówić znacząco o zakresie iteratorów [First, Last) w kontekście funkcji członkowskich.

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_multimap

Tworzy listę o określonym rozmiarze lub z elementami określonej wartości lub z określonego allocator lub jako kopię innej hash_multimap.

Typedefs

allocator_type	Typ, który reprezentuje klasę allocator obiektu hash_multimap.
const_iterator	Typ, który dostarcza iterator dwukierunkowy, który może odczytać element const w hash_multimap.
const_pointer	Typ, który dostarcza wskaźnik do elementu const w hash_multimap.
const_reference	Typ, który dostarcza odwołanie do elementu const przechowywanego w hash_multimap 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_multimap.
difference_type	Typ liczby całkowitej ze znakiem, który może służyć do reprezentowania liczby elementów hash_multimap w zakresie pomiędzy elementami wskazywanymi przez iteratory.
iterator	Typ, który dostarcza iterator dwukierunkowy do odczytu i modyfikacji dowolnego elementu w hash_multimap.
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_multimap.
key_type	Typ, który opisuje obiekt klucza sortowania, stanowiący każdy element hash_multimap.
mapped_type	Typ, który reprezentuje typ danych przechowywanych w hash_multimap.
wskaźnik	Typ, który zawiera wskaźnik do elementu w hash_multimap.
odwołanie	Typ, który zawiera odwołanie do elementu przechowywanego w hash_multimap.
reverse_iterator	Typ, który dostarcza iterator dwukierunkowy do odczytu i modyfikacji elementu w odwróconym hash_multimap.
size_type	Typ liczby całkowitej bez znaku, który może reprezentować liczbę elementów w hash_multimap.
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_multimap.

Funkcje członkowskie

rozpocznij	Zwraca iterator adresujący pierwszy element w hash_multimap.
hash_multimap::cbegin	Zwraca stały iterator adresujący pierwszy element w hash_multimap.
hash_multimap::cend	Zwraca stały iterator adresujący lokalizację następującą po ostatnim elemencie w hash_multimap.
wyczyść	Usuwa wszystkie elementy hash_multimap.
count	Zwraca liczbę elementów w hash_multimap, których klucz pasuje do klucza określonego jako parametr.
hash_multimap::crbegin	Zwraca stały iterator adresujący pierwszy element w odwróconym hash_multimap.
hash_multimap::crend	Zwraca stały iterator adresujący lokalizację następującą po ostatnim elemencie w odwróconej hash_multimap.
hash_multimap::emplace	Wstawia element stworzony w miejscu do hash_multimap.
hash_multimap::emplace_hint	Wstawia element stworzony w miejscu do hash_multimap, ze wskazówką położenia.
pusty	Sprawdza, czy hash_multimap jest pusty.
end	Zwraca iterator adresujący lokalizację następującą po ostatnim elemencie w hash_multimap.
equal_range	Zwraca iterator adresujący lokalizację następującą po ostatnim elemencie w hash_multimap.
wymazywanie	Usuwa element lub zakres elementów w hash_multimap od określonej pozycji.
znajdź	Zwraca iterator adresujący lokalizację elementu w hash_multimap, który ma klucz równoważny z określonym kluczem.
get_allocator	Zwraca kopię obiektu allocator użytego do stworzenia hash_multimap.
wstaw	Wstawia element lub zakres elementów do hash_multimap na określonej pozycji.
key_comp	Pobiera kopię obiektu porównania użytego do uporządkowania kluczy w hash_multimap.
lower_bound	Zwraca iterator do pierwszego elementu w hash_multimap, gdzie wartość klucza jest równa lub większa do określonego klucza.
maksymalny rozmiar	Zwraca maksymalną długość hash_multimap.
rbegin	Zwraca iterator adresujący pierwszy element w odwróconym hash_multimap.
rend	Zwraca iterator adresujący lokalizację następującą po ostatnim elemencie w odwróconym hash_multimap.
rozmiar	Określa nowy rozmiar hash_multimap.
swap	Zamienia elementy z dwóch hash_multimap.
upper_bound	Zwraca iterator do pierwszego elementu w hash_multimap, 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_multimap.