hash_multimap – třída

Článek
06/09/2015

[!POZNÁMKA]

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

Hash_multimap třída kontejneru je rozšíření knihovny standardních šablon a používá se pro skladování a rychlému načítání dat z kolekce, ve kterém každý prvek je pár, který má klíč řazení, jehož hodnota nemusí být jedinečné a přidružená data hodnotu.

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 dat klíče uložené v hash_multimap.
Type
Typ datových prvků v hash_multimap.
Traits
Typ, který obsahuje dvě funkce objektů třídy Traits , je možné porovnat dvě hodnoty elementu jako klíče řazení k určení jejich relativní pořadí a funkce hash, která je unárního predikátu mapování hodnot klíčových prvků na znaménka typu size_t.Tento argument je nepovinný a hash_compare<Key, less<Key> > je výchozí hodnota.
Allocator
Typ, který představuje uloženou přidělování objekt, který zapouzdří informace o přidělování a navracení zpět paměti hash_multimap.Tento argument je nepovinný a výchozí hodnota je allocator<pair <const Key, Type> >.

Poznámky

Hash_multimap 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ů.
Více, protože jeho prvky nemusí mít jedinečné klíče tak, aby jedna hodnota klíče mohou mít mnoho hodnot dat prvek přidružen.
Pár asociativní kontejneru, protože jeho hodnoty prvku se liší od hodnoty klíče.
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í.Hodnoty elementu v hash_multimap, ale ne jeho přidruženou hodnotu klíče, může se 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).

Aplikace jsou splněny podmínky přiřazení hodnoty k jejich klíče by měl být hash_multimap asociativní kontejneru dle výběru.Model pro tento typ struktury je uspořádaný seznam klíčová slova s přidružených řetězcových hodnot poskytování, říci, definice, kde nebyly vždy jednoznačně definovány slova.Pokud místo toho byly jednoznačně definovaná klíčová slova tak, aby byly jedinečné klíče, by bylo hash_map kontejneru dle 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.

Řada ovládá pomocí volání uložené hodnoty hash objednávky hash_multimap Traits objekt typu value_compare.K tomuto uloženému objektu lze přistupovat voláním členské funkce key_comp.Funkce objektu musí se chovají stejně jako objekt třídy hash_compare<Key, less<Key> >.Konkrétně pro všechny hodnoty Key typu Key, volání Traits (Key) dává 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ý.Výsledkem řazení mezi prvky nerovnocenné.Technicky je funkce porovnání binárním predikátem, který indukuje přísné slabé řazení, standardním matematickým způsobem.Funkce objektu, který má dva objekty argumentu je binárního predikátu f (x, y) x a y a vrácená hodnota true nebo false.Objednání ukládané hash_multimap přísné slabým objednávání Pokud binárního predikátu Nereflexivní antisymetrického a přenosné a je-li rovnocennost přenosné, kde dva objekty se x a y jsou definovány jsou rovnocenné, pokud je f (x, y) a f (y, x) false.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.

Obousměrný iterátor, ale členské funkce třídy je iterátor poskytovaném třídou hash_multimap Vložit a hash_multimap verze, které berou jako parametry šablony slabší vstupní iterátor, jehož funkce požadavky jsou minimální více než jsou zaručeny třídy iterátorů obousměrné.Různé koncepty iterátorů tvoří rodinu týkající se upřesnění jejich funkčnosti.Každý iterátor pojem má svou vlastní hash_multimap požadavky a algoritmy, které pracují s nimi musí omezit jejich předpoklady k požadavkům podle typu iterator.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í hash_multimap funkcí, ale je dostatečně srozumitelně komunikovat o rozsahu u iterátorů [First, Last) v rámci členské funkce.

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_multimap

Sestaví seznam určitou velikost nebo s prvky určitou hodnotu nebo s určitým allocator nebo jako kopie některých jiných hash_multimap.

Typedefs

allocator_type	Typ, který představuje třídu allocator pro objekt hash_multimap.
const_iterator	Typ, který poskytuje obousměrný iterátor, který může přečíst prvek const v objektu hash_multimap.
const_pointer	Typ, který poskytuje ukazatel na prvek const v objektu hash_multimap.
const_reference	Typ, který poskytuje odkaz na prvek const uložený v objektu hash_multimap 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_multimap.
difference_type	Celočíselný typ se znaménkem, který slouží k vyjádření počtu prvků objektu hash_multimap 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_multimap.
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_multimap.
key_type	Typ, který popisuje objekt klíče řazení, který představuje každý prvek hash_multimap.
mapped_type	Typ, který představuje datový typ uložený v objektu hash_multimap.
ukazatel	Typ, který poskytuje ukazatel na prvek v objektu hash_multimap.
odkaz	Typ, který poskytuje odkaz na prvek uložený v objektu hash_multimap.
reverse_iterator	Typ, který poskytuje obousměrný iterátor, který může číst nebo upravovat prvek v obráceném objektu hash_multimap.
size_type	Celočíselný typ bez znaménka představující počet prvků v objektu hash_multimap.
value_type	Typ, který poskytuje objekt funkce, který může porovnat dva prvky pro určení jejich relativního pořadí v objektu hash_multimap.

Členské funkce

begin	Vrátí iterátor adresující první prvek v objektu hash_multimap.
hash_multimap::cbegin	Vrátí konstantní iterátor adresující první prvek v objektu hash_multimap.
hash_multimap::cend	Vrátí konstantní iterátor adresující umístění následující po posledním prvku v objektu hash_multimap..
vymazat	Vymaže všechny prvky objektu hash_multimap.
count	Vrátí počet prvků objektu hash_multimap, jejichž klíč odpovídá klíči se zadaným parametrem.
hash_multimap::crbegin	Vrátí konstantní iterátor adresující první prvek v obráceném objektu hash_multimap.
hash_multimap::crend	Vrátí konstantní iterátor adresující umístění následující po posledním prvku v obráceném objektu hash_multimap.
hash_multimap::emplace	Vloží vytvořený prvek na místo do objektu hash_multimap.
hash_multimap::emplace_hint	Vloží vytvořený prvek s náznakem umístění na místo do objektu hash_multimap.
prázdné	Testuje, zda je objekt hash_multimap prázdný.
end	Vrátí iterátor adresující umístění následující po posledním prvku v objektu hash_multimap.
equal_range	Vrátí iterátor adresující umístění následující po posledním prvku v objektu hash_multimap.
smazat	Odstraní prvek nebo rozsah elementů v objektu hash_multimap ze zadaných pozic
najít	Vrátí iterátor adresující umístění prvku v objektu hash_multimap, který má klíč odpovídající zadanému klíči.
get_allocator	Vrátí kopii objektu allocator, který slouží k vytvoření objektu hash_multimap.
insert	Vloží prvek nebo rozsahu prvků do hash_multimap na určené pozici.
key_comp	Získá kopii porovnání objekt použitý k objednávce klíčů v hash_multimap.
lower_bound	Iterovat vrátí první prvek hash_multimap , že klíč hodnota je rovna nebo větší než zadané klíče.
max_size	Vrátí maximální délku objektu hash_multimap.
rbegin	Vrátí iterátor adresující první prvek v obráceném objektu hash_multimap.
rend	Vrátí iterátor adresující umístění následující po posledním prvku v obráceném objektu hash_multimap.
velikost	Určuje novou velikost objektu hash_multimap.
zaměnit	Vymění prvky dvou objektů hash_multimap.
upper_bound	Vrátí iterátor na první prvek objektu hash_multimap 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_multimap.