hash_set Class

Článek
03/26/2013

[!POZNÁMKA]

Toto rozhraní API je zastaralé.Alternativou je unordered_set Class.

Hash_set třídy kontejneru je rozšíření této šablony knihovny STL (Standard) a slouží pro ukládání a rychlé načítání dat z kolekce jsou jedinečné hodnoty obsažených prvků a sloužit jako hodnoty klíče.

template <
   class Key, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<Key> 
>
class hash_set

Parametry

Key
Typ dat prvku uloženy v hash_set.
Traits
Typ, který zahrnuje dva objekty funkce Porovnat jednu třídu je binárního predikátu moci porovnat dvě hodnoty elementu jako klíče řazení určit jejich relativní pořadí a funkce hash, která je unární predikát mapování hodnot klíčových prvků na nepodepsané celá čísla typu size_t.Tento argument je nepovinný a hash_compare*< klíče* méně*<Key> >* Výchozí hodnota je.
Allocator
Typ, který představuje uloženou přidělování objekt, který zapouzdřuje informace o přidělování a navracení zpět paměti hash_set.Tento argument je nepovinný a výchozí hodnota je přidělování*<Key>.*

Poznámky

Hash_set je:

Asociativní kontejneru, které proměnné velikosti kontejneru, který podporuje efektivní načtení hodnoty elementu podle přidružené klíče hodnoty.Dále je jednoduché asociativní kontejner, protože jeho hodnoty elementu jeho hodnoty klíče.
Vrátit zpět, protože poskytuje obousměrný iterátor přístup k jeho prvky.
Hešováno, protože jeho prvky jsou seskupeny do bloků na základě hodnoty hash funkce použity hodnoty klíče prvků.
V tom smyslu, že každý z jeho prvků musí mít jedinečný klíč je jedinečný.Protože hash_set je také jednoduché asociativní kontejneru, jeho prvky jsou také jedinečné.
Třída šablony protože poskytuje funkce je obecný a tak nezávislé na konkrétní typ dat obsažených prvků nebo klíče.Datové typy pro klíče a prvky jsou, místo toho zadány jako parametry v šabloně třídy a funkce porovnání a přidělování.

Hlavní výhodou hash přes řazení je větší účinnost; úspěšné hash provádí vkládání, odstraňování a vyhledá v konstantní Průměrná doba srovnání času úměrné logaritmu počtu prvků v kontejneru pro třídění technik.Hodnotu elementu v sadě nemusí přímo změnit.Místo toho musíte odstranit staré hodnoty a vložení prvků novými hodnotami.

Volba typu kontejner by obecně založené na typu hledání a vložením požadovaného aplikací.Hash asociativní kontejnery jsou optimalizovány pro operace vyhledávání, vkládání a odstraňování.Členské funkce, které explicitně podporují tyto operace jsou účinné při použití funkce hash dobře, jejich provedení v čase, který je v průměru konstantní a není závislá na počtu prvků v kontejneru.Funkce hash dobře vytváří rovnoměrné rozdělení hodnot hash hodnoty a minimalizuje počet kolizím, kde se říká srážky při odlišné hodnoty klíče jsou mapovány na stejnou hodnotu hash.V nejhorším případě nejhorší možné hash funkce počet operací je úměrná počtu prvků v pořadí (lineární čas).

Hash_set by měl být asociativní kontejneru voleb jsou splněny podmínky jejich klíče Přiřazení hodnoty aplikací.Prvky hash_set jsou jedinečné a sloužit jako vlastní klíče řazení.Model pro tento typ struktury je uspořádaný seznam, slova říci, ve kterých slova může dojít pouze jednou.Pokud bylo povoleno více výskytů slova, by hash_multiset struktura odpovídající kontejner.Pokud hodnoty je třeba připojit k seznamu jedinečný klíčová slova, hash_map by vhodné struktury obsahovat tato data.Pokud namísto klíče nejsou jedinečné, by hash_multimap kontejner voleb.

Pořadí řídí voláním uložené hodnoty hash objednávky hash_set Vlastnosti objekt typu value_compare.Tento objekt uložené mohou přistupovat voláním členské funkce key_comp.Funkce objektu musí se chovají stejně jako objekt třídy hash_compare < klíč, méně <Key> >. Konkrétně pro všechny hodnoty _Key typu klíče volání znak (_Key ) dává rozdělení hodnot typu size_t.

Obecně třeba zavést tuto objednávku pouze menší než srovnatelné prvky: aby dána dvěma prvky, jej může být stanoven jsou rovnocenné (v tom smyslu, že ani menší než jiný) nebo že jeden je menší než ostatní.Výsledkem řazení mezi prvky nejsou rovnocenné.Na další technické poznámky je funkce porovnání binárního predikátu, která indukuje přísné slabé řazení do standardní matematické smysl.Binárního predikátu f(x,y) je funkce objektu, který má dva objekty argumentu x a y a vrácená hodnota true nebo false.Přísné slabým objednání Pokud binárního predikátu nereflexivní antisymetrického a přenositelné a pokud rovnocennosti přenosné, kde dva objekty řazení uložených hash_set je x a y jsou definovány jako rovnocenné, kdy obě f(x,y) a f(y,x) jsou nepravdivé.Pokud silnější podmínku rovnosti mezi klíči nahradí, rovnocennosti, řazení se stane celkem (v tom smyslu, že jsou všechny prvky uspořádány k sobě) a odpovídající klíče budou od sebe indiscernible.

Skutečné pořadí prvků v řízené sekvenci závisí na funkci hash funkce řazení a aktuální velikost tabulky hash uložené v objektu kontejneru.Aktuální velikost tabulky hash nelze určit tak pořadí prvků v řízené sekvenci nelze předpovědět obecně.Vkládání prvků přestanou platit žádné iterátorů a odebrání prvků zruší platnost pouze iterátory, které bylo výslovně nepočítá prvky odstraněny.

Obousměrný iterátor, ale členské funkce třídy je iterátor poskytuje třídy hash_set Vložit a hash_set verzemi vzít jako parametry šablony slabší vstupní iterátor, jehož funkce požadavky jsou minimální více než zaručené třídou obousměrných iterátorů.Formulář iterátor odlišné koncepty vztahují zpřesnění jejich funkčnosti rodiny.Každý koncept iterátor má vlastní sadu požadavků a algoritmy, které s nimi pracovat, musí omezit jejich předpoklady podle typu iterator požadavky.Může předpokládat, že může přímo odkázat vstupní iterátor odkázat na některý objekt a může být zvýšena na iterátor další v pořadí.Toto je minimální sadu funkcí, ale je dost moci hovořit o rozsahu iterátorů srozumitelně [_First, _Last) v rámci členské funkce třídy.

V aplikaci Visual C++ .NET 2003, členové <hash_map> a <hash_set> jsou již v oboru názvů std soubory hlaviček, ale spíše být přesunut do oboru názvů stdext.Viz stdext obor názvů Další informace.

Konstruktory

hash_set

Konstrukce hash_set je prázdné nebo je kopírovat všechny nebo některé další část hash_set.

Funkce TypeDef

allocator_type	Typ, který představuje allocator pro třídu hash_set objektu.
const_iterator	Typ, který poskytuje obousměrný iterátor, která mohou číst const prvek hash_set.
const_pointer	Typ, který obsahuje ukazatel const element v hash_set.
const_reference	Typ, který poskytuje odkaz na const element uložené v hash_set pro čtení a provádění const operace.
const_reverse_iterator	Typ, který poskytuje obousměrný iterátor, která mohou číst všechny const prvek hash_set.
difference_type	Použitý představující počet prvků typu se znaménkem hash_set v rozsahu mezi prvky odkazuje iterátorů.
iterace	Typ, který poskytuje obousměrný iterátor, který lze číst nebo upravovat libovolný prvek v hash_set.
key_compare	Typ, který poskytuje funkce objektu, který lze porovnat dva klíče řazení určit relativní pořadí dvou prvků hash_set.
key_type	Typ, který popisuje objekt uložen jako prvek hash_set v postavení klíč řazení.
ukazatel	Typ, který obsahuje ukazatel na prvek hash_set.
odkaz	Typ, který poskytuje odkaz na element v uložených hash_set.
reverse_iterator	Typ, který poskytuje obousměrný iterátor, který lze číst nebo upravovat prvek Stornovaná hash_set.
size_type	Typ unsigned integer představující počet prvků v hash_set.
value_compare	Typ, který poskytuje dvě funkce objektů binárního predikátu porovnat třídy, můžete porovnat dvě hodnoty elementu hash_set k určení jejich relativní pořadí a unární operátor predikátu, vytvoří hodnotu hash prvky.
value_type	Typ, který popisuje objekt uložen jako prvek hash_set jako hodnotu.

Členské funkce

začít	Vrátí iterátor, který řeší první prvek hash_set.
hash_set::cbegin	Vrátí const iterátor adresování první prvek hash_set.
hash_set::cend	Vrátí const iterátor, který řeší umístění následných posledního prvku hash_set.
Vymazat	Vymaže všechny prvky hash_set.
počet	Vrátí počet prvků hash_set klíč, jehož shoduje s klíčem zadán parametr.
hash_set::crbegin	Vrátí const iterátor adresování první prvek Stornovaná hash_set.
hash_set::crend	Vrátí const iterátor, který řeší umístění následných poslední prvek v reverzní hash_set.
hash_set::emplace	Vloží prvek konstruovány do místa hash_set.
hash_set::emplace_hint	Vloží prvek vyrobeno na místě do hash_set, s umístění nápovědy.
prázdné	Pokud testy hash_set je prázdný.
Konec	Vrátí iterátor, který řeší umístění následných posledního prvku hash_set.
equal_range	Vrátí pár iterátorů respektive první prvek hash_set s klíčem, který je větší než zadaný klíč a první prvek hash_set s klíčem, který je roven nebo větší než klíč.
Vymazat	Odebere prvek nebo rozsahu prvků v hash_set od zadané pozice nebo odebere prvky, které odpovídají zadaným klíčem.
Najít	Vrátí iterace adresování umístění prvku v hash_set , který má zadaný klíč odpovídající klíč.
get_allocator	Vrátí kopii allocator používá k vytvoření objektu hash_set.
Vložit	Vloží element nebo elementy do oblasti hash_set.
key_comp	Získá kopii objektu porovnání, používá pořadí klíče hash_set.
lower_bound	Vrátí iterace první prvek hash_set s klíčem, který je roven nebo větší než zadaný klíč.
max_size	Vrátí maximální délku hash_set.
rbegin	Vrátí iterace adresování první prvek Stornovaná hash_set.
rend	Vrátí iterátor, který řeší umístění následných poslední prvek v reverzní hash_set.
size	Vrátí počet prvků hash_set.
odkládací	Výměny prvky dvou hash_sets.
upper_bound	Vrátí iterace první prvek hash_set , s klíčem, který je roven nebo větší než zadaný klíč.
value_comp	Získá kopii objektu znaky hash algoritmu hash a pořadí hodnoty klíče v prvku hash_set.