hash_map – třída

Článek
06/09/2015

[!POZNÁMKA]

Toto rozhraní API je zastaralé.Alternativou je unordered_map – třída.

Rychle ukládá a načítá data z kolekce, ve které je každý prvek pár, který má klíč řazení, jehož hodnota je jedinečná a přidružená k datové hodnotě.

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

Parametry

Key
Datový typ klíče, který se uloží v objektu hash_map.
Type
Datový typ prvku, který se uloží v objektu hash_map.
Traits
Typ, který obsahuje dva objekty funkce, jedna z tříd porovnává dvě hodnoty prvku jako klíče řazení, čímž lze zjistit jejich relativní pořadí a hashovací funkce, která je unární predikát mapující hodnoty klíčových prvků na bez znaménkové celé číslo typu size_t.Tento argument je nepovinný a hash_compare<Key, less<Key> > je výchozí hodnota.
Allocator
Typ, který představuje uložený objekt alokátoru, který zapouzdřuje informace o přidělování a navracení zpět paměti objektu hash_map.Tento argument je volitelný a výchozí hodnota je allocator<pair <const Key, Type>>.

Poznámky

Objekt hash_map je:

Asociativní kontejner, což je kontejner proměnné velikosti, který podporuje efektivní načtení hodnoty prvku založené na přiřazené hodnotě klíče.
Oboustranný, protože poskytuje obousměrný iterátor pro přístup k jeho prvkům.
Používá algoritmus hash, protože jeho prvky jsou seskupeny do bloků podle hodnoty hashovací funkce použité na hodnoty klíčů prvků.
Jedinečný v tom smyslu, že každý z jeho prvků musí mít jedinečný klíč.
Kontejner asociativních párů, protože jeho prvky hodnoty dat se liší od hodnot klíčů.
Třída šablony, protože poskytuje obecné funkce a to nezávisle na určitém typu dat obsažených jako prvky nebo klíče.Datové typy použité pro prvky a klíče jsou místo toho zadány jako parametry v šabloně třídy společně s funkcí porovnání a alokátorem.

Hlavní výhodou hashování oproti řazení je vyšší výkon, úspěšné hashování provede vkládání, odstranění a vyhledání v konstantní průměrné době ve srovnání s dobou úměrnou logaritmu počtu prvků v kontejneru pro techniky třídění.Hodnotu prvku v objektu hash_map, ale ne jeho přidruženou hodnotu klíče, lze změnit přímo.Namísto toho hodnoty klíčů přidružené ke starým prvkům musí být odstraněny a vloženy nové hodnoty klíče související s novými prvky.

Volba typu kontejneru by měla obecně vycházet z typu vyhledávání a vkládání vyžadovaného aplikací.Asociativní kontejnery algoritmu hash jsou optimalizovány pro operace vyhledávání, vkládání a odstranění.Členské funkce, které explicitně podporují tyto operace, jsou účinné při použití dobře navržené hashovací funkce, provedené v čase konstantního průměru a nejsou závislé na počtu prvků v kontejneru.Dobře navržená hashovací funkce vytváří rovnoměrné rozdělení hashovaných hodnot a minimalizuje počet kolizí, kde ke kolizi dojde, pokud jsou hodnoty odlišných hodnot klíčů mapovány na stejnou hashovanou hodnotu.V nejhorším případě s nejhorší možnou hashovací funkcí je počet operací úměrný počtu prvků v sekvenci (lineární čas).

Objekt hash_map by měl být asociativní kontejner dle výběru, kdy jsou podmínky přiřazení hodnot k jejich klíčům splněny aplikací.Model tohoto typu struktury je uspořádaný seznam jednoznačně se vyskytujících klíčových slov s přidruženými řetězcovými hodnotami poskytují definice.Pokud místo toho tato slova měla více než jednu správnou definici, takže klíče nebyly jedinečné, bude objekt hash_multimap správným kontejnerem výběru.Naopak pokud je pouze uložen seznam slov, bude objekt hash_set tím správným kontejnerem.Pokud bylo povoleno více výskytů jednoho slova, je objekt hash_multiset odpovídající strukturou kontejneru.

Objekt hash_map seřadí sekvenci, kterou ovládá pomocí volání uloženého objektu Traits třídy value_compare.K tomuto uloženému objektu lze přistupovat voláním členské funkce key_comp.Takový objekt funkce se musí chovat stejně jako objekt třídy hash_compare<Key, less<Key>>.Konkrétně pro všechny hodnoty Key typu Key volání objektu Traits(Key ) poskytuje rozdělení hodnot typu size_t.

Obecně, tyto prvky musí být menší než srovnatelné pro toto pořadí, což znamená, že když jsou uvedeny dva prvky, může být stanoveno, zda jsou ekvivalentní (v tom smyslu, že ani jeden není menší než ten druhý), nebo že jeden je menší než druhý.To má za výsledek řazení mezi neekvivalentními prvky.Technicky je funkce porovnání binárním predikátem, který indukuje přísné slabé řazení, standardním matematickým způsobem.Binární predikát f(x y) je objekt funkce, který má dva objekty argumentu x a y a návratovou hodnotu true nebo false.Řazení stanovené objektem hash_map je přísné slabé řazení, pokud je binární predikát nereflexivní, antisymetrický a tranzitivní, a je-li ekvivalence tranzitivní, kde dva objekty x a y jsou definovány jako ekvivalentní, když jsou f(x, y) i f(y, x) nepravdivé.Pokud silnější podmínka rovnosti mezi klíči nahradí ekvivalenci, stane se pořadí celkovým (v tom smyslu, že všechny prvky jsou uspořádány ve vztahu k sobě navzájem) a odpovídající klíče budou od sebe nerozeznatelné.

Skutečné pořadí prvků v řízené sekvenci závisí na hashovací funkci, funkci řazení a aktuální velikosti hashovací tabulky uložené v objektu kontejneru.Aktuální velikost hashovací tabulky nelze určit, takže obecně nelze předvídat pořadí prvků v řízené sekvenci.Vkládání prvků nezruší platnost žádných iterátorů a odstranění prvků zruší platnost pouze těch iterátorů, které výslovně odkazovaly na odstraněné prvky.

Iterátor poskytovaný třídou hash_map je obousměrný iterátor, ale členské funkce třídy insert a hash_map mají verze, které jako parametry šablony berou slabší vstupní iterátor, jehož požadavky na funkce jsou minimálnější než ty, které jsou zaručeny třídou obousměrných iterátorů.Různé koncepty iterátorů tvoří rodinu týkající se upřesnění jejich funkčnosti.Každý koncept iterátoru má vlastní sadu požadavků a algoritmy, které s nimi pracují, musí omezit jejich předpoklady na požadavky podle typu iterátoru.Lze předpokládat, že ke vstupnímu iterátoru lze přistoupit přes ukazatel pro odkazování na některý objekt a že může být zvýšen na další iterátor v pořadí.Toto je minimální sada funkcí, ale je dostatečná pro srozumitelnou komunikaci o rozsahu u iterátorů [First, Last) v rámci členské funkce třídy.

V aplikaci Visual C++ .NET 2003, členové hlavičkových souborů tříd <hash_map> a <hash_set> již nejsou v oboru názvů std, ale byly přesunuty do oboru názvů stdext.Další informace naleznete v tématu Obor názvů stdext.

Konstruktory

hash_map

Zkonstruuje objekt hash_map, který je prázdný nebo který je kopií celého nebo části některého jiného objektu hash_map.

Typedefs

allocator_type	Typ, který představuje třídu allocator pro objekt hash_map.
const_iterator	Typ, který poskytuje obousměrný iterátor, který může přečíst prvek const v objektu hash_map.
const_pointer	Typ, který poskytuje ukazatel na prvek const v objektu hash_map.
const_reference	Typ, který poskytuje odkaz na prvek const uložený v objektu hash_map pro čtení a provádění operací const.
const_reverse_iterator	Typ, který poskytuje obousměrný iterátor, který může přečíst jakýkoli prvek const v objektu hash_map.
difference_type	Celočíselný typ se znaménkem, který slouží k vyjádření počtu prvků objektu hash_map v rozsahu mezi prvky, na které odkazují iterátory.
iterátor	Typ, který poskytuje obousměrný iterátor, který může číst nebo upravovat libovolný prvek v objektu hash_map.
key_compare	Typ, který poskytuje objekt funkce, který může porovnat dva klíče řazení pro určení relativního pořadí dvou prvků v objektu hash_map.
key_type	Typ, který popisuje řazení objektu klíče, který představuje každý prvek objektu hash_map.
mapped_type	Typ, který představuje datový typ uložený v objektu hash_map.
ukazatel	Typ, který poskytuje ukazatel na prvek v objektu hash_map.
odkaz	Typ, který poskytuje odkaz na prvek uložený v objektu hash_map.
reverse_iterator	Typ, který poskytuje obousměrný iterátor, který může číst nebo upravovat prvek v obráceném objektu hash_map.
size_type	Celočíselný typ bez znaménka představující počet prvků v objektu hash_map.
value_type	Typ, který poskytuje objekt funkce, který může porovnat dva prvky pro určení jejich relativního pořadí v objektu hash_map.

Členské funkce

hash_map::at	Vyhledá prvek v objektu hash_map se zadanou hodnotou klíče.
begin	Vrátí iterátor adresující první prvek v objektu hash_map.
hash_map::cbegin	Vrátí konstantní iterátor adresující první prvek v objektu hash_map.
hash_map::cend	Vrátí konstantní iterátor adresující umístění následující po posledním prvku v objektu hash_map..
vymazat	Vymaže všechny prvky objektu hash_map.
count	Vrátí počet prvků objektu hash_map, jejichž klíč odpovídá klíči se zadaným parametrem.
hash_map::crbegin	Vrátí konstantní iterátor adresující první prvek v obráceném objektu hash_map.
hash_map::crend	Vrátí konstantní iterátor adresující umístění následující po posledním prvku v obráceném objektu hash_map.
hash_map::emplace	Vloží vytvořený prvek na místo do objektu hash_map.
hash_map::emplace_hint	Vloží vytvořený prvek s náznakem umístění na místo do objektu hash_map.
prázdné	Testuje, zda je objekt hash_map prázdný.
end	Vrátí iterátor adresující umístění následující po posledním prvku v objektu hash_map.
equal_range	Vrátí pár iterátorů, respektive, na první prvek objektu hash_map s klíčem, který je větší než zadaný klíč a na první prvek objektu hash_map s klíčem, který je roven nebo větší než tento klíč.
smazat	Odstraní prvek nebo rozsah elementů v objektu hash_map ze zadaných pozic
najít	Vrátí iterátor adresující umístění prvku v objektu hash_map, který má klíč odpovídající zadanému klíči.
get_allocator	Vrátí kopii objektu allocator, který slouží k vytvoření objektu hash_map.
insert	Vloží prvek nebo rozsah prvků do objektu hash_map.
key_comp	Vrátí iterátor na první prvek objektu hash_map s hodnotou klíče, který je roven nebo větší než zadaný klíč.
lower_bound	Vrátí iterátor na první prvek objektu hash_map s hodnotou klíče, který je roven nebo větší než zadaný klíč.
max_size	Vrátí maximální délku objektu hash_map.
rbegin	Vrátí iterátor adresující první prvek v obráceném objektu hash_map.
rend	Vrátí iterátor adresující umístění následující po posledním prvku v obráceném objektu hash_map.
velikost	Vrátí počet prvků v objektu hash_map.
zaměnit	Vymění prvky dvou objektů hash_map.
upper_bound	Vrátí iterátor na první prvek objektu hash_map s hodnotou klíče, který je větší než zadaný klíč.
value_comp	Získá kopii objektu porovnání použitého pro seřazení hodnot prvků objektu hash_map.

Operátory

operátor []	Vloží prvek do objektu hash_map se zadanou hodnotou klíče.
hash_map::operator=	Nahradí prvky objektu hash_map kopií jiného objektu hash_map.