hash_multiset-Klasse

Artikel
06/09/2015

Hinweis

Diese API ist veraltet.Die Alternative ist unordered_multiset-Klasse.

Das hash_multiset Containerklasse ist eine Erweiterung der Standardvorlagenbibliothek und für den Speicher und den schnellen Abrufen von Daten aus einer Auflistung verwendet, in der die Werte der enthaltenden Elemente als die Schlüsselwerte dienen und wird nicht benötigt, um eindeutig.

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

Parameter

Key
Der im hash_multiset zu speichernden Elementdatentyp.
Traits
Der Typ, der zwei Funktionsobjekte enthält, einer von Klassen vergleichen, die ein binäres Prädikat ist, das in der Lage ist, zwei Elementwerte als Sortierschlüssel zu vergleichen, um ihre relative Position und eine Hashfunktion zu bestimmen, die, Schlüsselwerte einer des unären Prädikats Zuordnung der Elemente an ganzen Zahlen ohne Vorzeichen Typ size_t entspricht. Dieses Argument ist optional und die hash_compare*<, Schlüssel* weniger*<Schlüssel> >* ist der Standardwert.
Allocator
Der Typ, der das gespeicherte Zuweisungsobjekt darstellt, das Informationen über die die Belegung und Freigabe des Speichers hash_multisets kapselt. Dieses Argument ist optional und allocator*<ist der Standardwert Schlüssel>.*

Hinweise

Das hash_multiset ist:

Ein assoziativer Container, der ein Container variabler Größe ist, der den effizienten Abruf von Elementwerten auf Grundlage eines zugeordneten Schlüsselwert unterstützt. Darüber hinaus ist ein einfacher assoziativer Container, weil die Elementwerte die Schlüsselwerte sind.
Umkehrbar, da ein bidirektionaler Iterator für den Zugriff auf die Elemente bereitgestellt wird.
Gehasht, da die Elemente auf Grundlage des Werts einer Hashfunktion, die auf die Schlüsselwerte der Elemente angewendet wird, in Buckets gruppiert werden.
Insofern eindeutig, da jedes der Elemente einen eindeutigen Schlüssel aufweisen muss. Da hash_multiset auch ein einfacher assoziativer Container handelt, sind seine Elemente ebenfalls eindeutig.
Eine Vorlagenklasse, da die Funktionen, die sie bereitstellt, ist und daher unabhängig des jeweiligen Typs der Daten generisch, die als Elemente oder Schlüssel enthalten werden. Die für Elemente und Schlüssel zu verwendenden Datentypen werden stattdessen in der Klassenvorlage zusammen mit der Vergleichsfunktion und der Zuweisung als Parameter angegeben.

Der Hauptvorteil des Hashverfahren zu Sortierung größere Effizienz ist: ein erfolgreiches Hashverfahren führt Einfügevorgängen, Löschvorgängen und Suchen in der Konstantendurchschnittszeit verglichen mit einer Uhrzeit aus, die für den Logarithmus der Anzahl der Elemente im Container für Sortierungstechniken proportional ist. Der Wert eines Elements in einen Satz nicht wird direkt geändert werden. Stattdessen müssen Sie alte Werte und Einsatzelemente mit neuen Werten löschen.

Die Auswahl des Containertyps sollte im Allgemeinen auf Grundlage des für die Anwendung erforderlichen Suchen und Einfügetyps erfolgen. Gehashte assoziative Container sind für Such-, Einfüge- und Entfernvorgänge optimiert. Die Memberfunktionen, die diese Vorgänge explizit unterstützen, sind effizient, wenn sie mit einer gut entworfenen Hashfunktion verwendet werden. Dann werden sie in einer Zeit ausgeführt, die im Durchschnitt konstant und nicht von der Anzahl von Elementen im Container abhängig ist. Eine ausgereifte Hashfunktion erzeugt eine vereinheitlichte Verteilung gehashter Werte und minimiert die Anzahl von Konflikten, bei denen ein Konflikt vorhergesagt wird, wenn unterschiedliche Schlüsselwerte dem gleichen gehashten Wert zugeordnet werden. Im schlimmsten Fall ist die Anzahl von Vorgängen bei der schlimmstmöglichen Hashfunktion zu der Anzahl von Elementen in der Sequenz proportional (lineare Zeit).

Das hash_multiset sollte der assoziative Container der Wahl sein, wenn die Bedingungen, die die Werte mit ihren Schlüssel zuordnen, erfüllt durch die Anwendung. Die Elemente eines hash_multiset können passieren und dienen als eigene Sortierschlüssel Schlüssel, so sind nicht eindeutig. Ein Modell für diesen Typ der Struktur ist eine geordnete Liste beispielsweise von Wörtern, in denen die Wörter möglicherweise mehrmals auftreten. Enthielte mehrere Vorkommen der Wörter nicht zulässig wurde, würde ein hash_set die entsprechende Containerstruktur gewesen sein. Wenn eindeutige Definitionen als Werte zur Liste der eindeutigen Schlüsselwörtern angefügt wurden, wird ein hash_map eine äquivalente Struktur sein, um diese Daten enthalten soll. Wenn stattdessen die Definitionen nicht eindeutig sind, wird ein hash_multimap der Container der Wahl sein.

Das hash_multiset sortiert die Sequenz, die steuert, indem ein gespeichertes Hashmerkmalsobjekt des Typs value_compare. Auf das gespeicherte Objekt wird möglicherweise zugegriffen, indem die Memberfunktion key_comp aufrufen wird. Ein solches Funktionsobjekt muss sich genauso verhalten wie ein Objekt der Klasse hash_compare*<Schlüssel,* weniger*<Schlüssel>>.* Insbesondere denn alle Werte Schlüssel des Typs Taste, wird der Aufruf Merkmal(Schlüssel) über Werte vom Typ size_t.

Im Allgemeinen müssen die Elemente der Vorwärtsiteratoren etwas weniger als vergleichbar sein, um diese Sortierung zu erstellen, sodass beliebige zwei Elemente möglicherweise als gleichwertig bestimmt werden (in dem Sinne, dass keins geringer als das Andere ist), oder dass eins geringer als das Andere ist. Dies führt zu einer Sortierung zwischen den nicht gleichwertigen Elementen. Etwas technischer betrachtet ist die Vergleichsfunktion ein binäres Prädikat, das eine strenge schwache Sortierung im mathematischen Sinn verursacht. Ein binärer Prädikat f(x,y) ist ein Funktionsobjekt, das zwei Argumentobjekt x und y und der Rückgabewert von true oder false hat von. Eine Reihenfolge, die einem hash_multiset angewendet wird, ist eine strenge schwache Sortieren, wenn das Prädikat irreflexiv binäre transitiv ist, antisymmetrisch, und wenn Äquivalenz transitiv ist, wo Objekt zwei x und y definiert werden, um zu entsprechen wenn sowohl f(x,y) als auch f(y,x) falsch sind. Wenn der stärkere Gleichheitszustand zwischen Schlüsseln die Äquivalenz ersetzt, erfolgt die Sortierung total (d. h., alle Elemente werden zueinander sortiert), und die verglichenen Schlüssel sind von den einander nicht mehr zu unterscheiden.

Die tatsächliche Reihenfolge der Elemente in der gesteuerten Sequenz hängt von der Hashfunktion, der Sortierfunktion und der aktuellen Größe der Hashtabelle ab, die im Containerobjekt gespeichert wird. Die aktuelle Größe der Hashtabelle kann nicht bestimmt werden. Deshalb kann die Reihenfolge der Elemente in der gesteuerten Sequenz im Allgemeinen nicht vorhergesagt werden. Das Einfügen von Elementen führt nicht dazu, dass Iteratoren ungültig werden, und durch das Entfernen von Elementen werden nur solche Iteratoren ungültig, die speziell auf die entfernten Elemente gezeigt haben.

Der Iterator, der von der hash_multiset Klasse bereitgestellt wird, ist ein bidirektionaler Iterator, der Klassenmember funktioniert Einfügen und hash_multiset haben Versionen, die als einen Vorlagenparameter abgeschwächten Eingabeiterator erhalten, dessen Funktionalitätsanforderungen minimaler sind als die, die von der Klasse von bidirektionalen Iteratoren garantiert werden. Die verschiedenen Iteratorkonzepte bilden eine Family, die durch Verfeinerungen in ihrer Funktionen verknüpft ist. Jedes Iteratorkonzept hat ein eigenes hash_multiset von Anforderungen und Algorithmen, die ihnen Muss-Grenze die Annahmen zu Anforderungen bearbeiten, die von diesem Typ des Iterators bereitgestellt werden. Es kann davon ausgegangen werden, dass ein Eingabeiterator möglicherweise so dereferenziert wird, dass er auf ein Objekt verweist und dieses möglicherweise zum folgenden Iterator in der Sequenz erhöht. Dies ist ein minimales hash_multiset der Funktionalität, sondern es genügt, um in der Lage zu sein, wird ein Bereich von Iteratoren [_First, _Last) im Rahmen der Memberfunktionen sinnvoll zu sprechen.

In Visual C++ .NET 2003 sind Member der <hash_map> und <hash_set> Headerdateien nicht mehr im STD-Namespace enthalten. Sie wurden stattdessen in den stdext-Namespace verschoben. Weitere Informationen finden Sie unter Der stdext-Namespace.

Konstruktoren

hash_multiset

Erstellt ein hash_multiset-Element, das leer oder die Kopie eines ganzen anderen hash_multiset-Elements oder eines Teils davon ist.

Typedefs

allocator_type	Ein Typ, der die allocator-Klassentyp für das hash_multiset-Objekt darstellt.
const_iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, der im hash_multiset-Element ein const-Element lesen kann.
const_pointer	Ein Typ, der einen Zeiger auf ein const-Element in einem hash_multiset-Element bereitstellt.
const_reference	Ein Typ, der einen Verweis auf ein const-Element bereitstellt, das in einem hash_multiset-Element zum Lesen und Ausführen von const-Vorgängen gespeichert ist.
const_reverse_iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, der im hash_multiset-Element jedes const-Element lesen kann.
difference_type	Ein ganzzahliger Typ mit Vorzeichen, mit der der Unterschied zwischen zwei stellt Iteratoren, die Elemente innerhalb des gleichen hash_multiset behandeln.
Iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, mit dem jedes Element in einer hash_multiset gelesen oder geändert werden kann.
key_compare	Eine Typ, der ein Funktionsobjekt bereitstellt, das zwei Sortierschlüssel vergleichen kann, um die relative Position von zwei Elementen im hash_multiset-Element zu bestimmen.
key_type	Ein Typ, der ein Objekt beschrieben wird, das als Element von hash_set in dessen Kapazität als Sortierschlüssel gespeichert wird.
Zeiger	Ein Typ, der einen Zeiger auf ein Element in einer hash_multiset bereitstellt.
Verweis	Ein Typ, der einen Verweis auf ein in einer hash_multiset gespeichertes Element bereitstellt.
reverse_iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, mit dem ein Element in einem umgekehrten hash_multiset-Element gelesen oder geändert werden kann.
size_type	Eine Ganzzahltyp ohne Vorzeichen, der die Anzahl von Elementen in hash_multiset darstellen kann.
value_compare	Ein Typ, der zwei, Funktionsobjekte stellt ein binäres Prädikat der Klasse vergleichen, das zwei Elementwerte von hash_multiset vergleichen kann, um ihre relative Position und kein unäres Prädikat zu bestimmen, das die Elemente wendet.
value_type	Ein Typ, der ein Objekt beschrieben wird, das als Element von hash_multiset in dessen Kapazität als Wert gespeichert wird.

Memberfunktionen

begin	Gibt ein Iterator zurück, der das erste Element in hash_multiset behandelt.
hash_multiset::cbegin	Gibt einen konstanten Iterator zurück, der das erste Element im hash_multiset-Element adressiert.
hash_multiset::cend	Gibt einen konstanten Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines hash_multiset-Elements nachfolgt.
clear	Löscht alle Elemente einer hash_multiset auf.
count	Gibt die Anzahl der Elemente in hash_multiset zurück, dessen Schlüssel eine Parameter-angegebene Schlüssel entspricht
hash_multiset::crbegin	Gibt einen konstanten Iterator zurück, der das erste Element im umgekehrten hash_multiset-Element adressiert.
hash_multiset::crend	Gibt einen konstanten Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines umgekehrten hash_multiset-Elements nachfolgt.
hash_multiset::emplace	Fügt ein Element ein, das vor Ort in ein hash_multiset-Element erstellt wird.
hash_multiset::emplace_hint	Fügt ein Element ein, das vor Ort mit einem Platzierungshinweis in ein hash_multiset-Element erstellt wird.
empty	Testet, ob ein hash_multiset-Element leer ist.
end	Gibt einen Iterator zurück, der den Speicherort adressiert, der dem letzten Element einem hash_multiset-Element nachfolgt.
equal_range	Gibt ein Paar Iteratoren bzw. dem ersten Element in hash_multiset mit einem Schlüssel, die größer ist, als ein bestimmter Schlüssel und dem ersten Element in hash_multiset mit einem Schlüssel zurück, die größer oder gleich dem Schlüssel.
Löschen	Entfernt ein Element oder einen Bereich von Elementen in hash_multiset von den angegebenen Speicherorten Elemente oder entfernt, die einen angegebenen Schlüssel übereinstimmen.
find	Gibt einen Iterator zurück, der die Position eines Elements in einem hash_multiset-Element adressiert, das einen Schlüssel aufweist, der einen angegebenen Schlüssel entspricht.
get_allocator	Gibt eine Kopie des zum Erstellen von allocator verwendeten hash_multiset-Objekts zurück.
Einfügen	Fügt ein Element oder einen Elementbereich in ein hash_multiset-Element ein.
key_comp	Ruft eine Kopie des Vergleichsobjekts ab, das zum Sortieren der Schlüssel in hash_multiset verwendet wird.
lower_bound	Gibt ein Iterator zum ersten Element in hash_multiset mit einem Schlüssel zurück, die größer oder gleich dem ein bestimmter Schlüssel.
max_size	Gibt die Maximallänge der hash_multiset zurück.
rbegin	Gibt einen Iterator zurück, der das erste Element in einem umgekehrten hash_multiset-Element adressiert.
rend	Gibt einen Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines umgekehrten hash_multiset-Elements nachfolgt.
size	Gibt die Anzahl von Elementen in der hash_multiset zurück.
swap	Tauscht die Elemente zweier hash_multisetn.
upper_bound	Gibt ein Iterator zum ersten Element in hash_multiset zurück, das einer Taste, die größer oder gleich dem ein bestimmter Schlüssel.
value_comp	Ruft eine Kopie des Hashmerkmalsobjekts ab, das verwendet wird, um Elementschlüsselwerte in hash_multiset zu hashen und zu sortieren.