hash_multimap-Klasse

Artikel
06/09/2015

Hinweis

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

Die hash_multimap-Containerklasse ist eine Erweiterung der Standardvorlagenbibliothek und wird für das Speichern und schnelle Abrufen von Daten aus einer Auflistung verwendet, in der jedes Element ein Paar mit einem Sortierschlüssel ist, dessen Wert nicht eindeutig sein muss, und einem zugeordneten Datenwert.

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

Parameter

Key
Der im hash_multimap-Element zu speichernde Schlüsseldatentyp.
Type
Der im hash_multimap-Element zu speichernde Elementdatentyp.
Traits
Der Typ, der zwei Funktionsobjekte enthält. Einer der Klasse Traits, der zwei Elementwerte als Sortierschlüssel vergleichen kann, um ihre relative Position zu bestimmen und eine Hashfunktion, die ein Zuordnungsschlüssel mit unärem Prädikat der Elemente für ganzen Zahlen ohne Vorzeichen vom Typ size_t ist. Dieses Argument ist optional, und hash_compare<Key, less<Key> > ist der Standardwert.
Allocator
Der Typ, mit dem das gespeicherte Zuordnungsobjekt darstellt wird, mit dem Details zum Belegen und Freigeben des Arbeitsspeichers des hash_multimap-Elements gekapselt werden. Dieses Argument ist optional, und der Standardwert ist allocator<pair <const Key, Type> >.

Hinweise

Das hash_multimap-Element 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.
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.
Mehrfach, da die Elemente keine eindeutige Schlüssel aufweisen müssen, damit ein Schlüsselwert über viele zugeordnete Elementdatenwerte verfügen kann.
Ein Paar assoziativer Container, da sich die Elementwerte von den Schlüsselwerten unterscheiden.
Eine Vorlagenklasse, da die bereitgestellten Funktionen generisch ist und daher unabhängig vom angegebenen Datentyp, der als Elemente oder Schlüssel enthalten ist. 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 Hashverfahrens gegenüber der Sortierung ist die größere Effizienz. Bei einem erfolgreichen Hashverfahren werden Einfüge-, Lösch- und Suchvorgänge, verglichen mit einer Zeit, die zum Logarithmus der Anzahl von Elementen im Container für Sortiertechniken proportional ist, in einer konstanten Durchschnittszeit durchgeführt. Der Wert eines Elements in einem hash_multimap-Element, aber nicht der zugehörige Schlüsselwert, werden möglicherweise direkt geändert. Stattdessen müssen die Schlüsselwerte, die alten Elementen zugeordnet sind, gelöscht, und stattdessen neuen Schlüsselwerten für neue Elemente zugeordnet werden.

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_multimap-Element sollte der ausgewählte assoziative Container sein, wenn die Bedingungen, mit denen die Werte von der Anwendung den Schlüsseln zugeordnet werden, erfüllt werden. Ein Modell für diesen Strukturtyp ist eine sortierte Liste von Schlüsselwörtern mit zugeordneten Zeichenfolgewerten, die, sagen wir, Definitionen bereitstellen, in denen die Wörter nicht immer eindeutig definiert wurden. Wenn die Schlüsselwörter stattdessen eindeutig definiert werden, damit die Schlüssel eindeutig sind, ist ein hash_map-Element der gewählte Container. Wenn hingegen nur die Wortliste gespeichert wurden, ist ein hash_set-Element der richtige Container. Wenn mehrfaches Vorkommen der Wörter zugelassen wird, ist ein hash_multiset-Element die geeignete Containerstruktur.

Das hash_multimap-Element sortiert die gesteuerte Sequenz, indem ein gespeichertes Traits-Hashobjekt des Objekts value_compare aufgerufen wird. Auf das gespeicherte Objekt wird möglicherweise zugegriffen, indem die Memberfunktion key_comp aufrufen wird. Ein solches Funktionsobjekt muss das gleiche Verhalten aufweisen, wie ein Objekt der hash_compare<Key, less<Key> >-Klasse. Insbesondere für alle Key-Werte des Typs Key, erreicht der Traits (Key)-Aufruf eine Verteilung der 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. Bei einem binären f(x, y)--Prädikat handelt es sich um ein Funktionsobjekt, das die zwei Argumentobjekte x und y aufweist sowie einen Rückgabewert von true oder false. Eine Sortierung, die auf ein hash_multimap-Element angewendet wird, ist eine strenge schwache Sortierung, wenn das binäre Prädikat irreflexiv, antisymmetrisch und transitiv ist, und wenn die Äquivalenz transitiv ist, wobei die beiden Objekte x und y als äquivalent definiert werden, wenn sowohl f (x, y) als auch f (x, y) false 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 von einer hash_multimap-Klasse bereitgestellte Iterator ist ein bidirektionaler Iterator. Die Klassenmemberfunktionen insert und hash_multimap weisen allerdings Versionen auf, einen abgeschwächten Eingabeiterator als einen Vorlagenparameter akzeptieren, dessen Funktionalitätsanforderungen weniger umfangreich sind, als die von der Klasse bidirektionaler Iteratoren garantierten. Die verschiedenen Iteratorkonzepte bilden eine Family, die durch Verfeinerungen in ihrer Funktionen verknüpft ist. Jedes Iteratorkonzept weist einen eigenes hash_multimap-Element von Anforderungen auf, und die damit funktionierenden Algorithmen müssen die Annahmen hinsichtlich der von diesem Iteratortyp bereitgestellten Anforderungen begrenzen. 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. Das ist eine minimaler hash_multimap-Funktion, allerdings genügt sie, um sinnvoll über einen Bereich von [First, Last)-Iteratoren im Kontext der Klassenmemberfunktionen 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_multimap

Erstellt eine Liste einer bestimmten Größe bzw. mit Elementen eines bestimmten Werts oder mit einem bestimmten allocator-Element oder als vollständige bzw. teilweise Kopie eines anderen hash_multimap-Elements.

Typedefs

allocator_type	Ein Typ, der die allocator-Klassentyp für das hash_multimap-Objekt darstellt.
const_iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, der im hash_multimap-Element ein const-Element lesen kann.
const_pointer	Ein Typ, der einen Zeiger auf ein const-Element in einem hash_multimap-Element bereitstellt.
const_reference	Ein Typ, der einen Verweis auf ein const-Element bereitstellt, das in einem hash_multimap-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_multimap-Element jedes const-Element lesen kann.
difference_type	Ein Ganzzahltyp mit Vorzeichen, der dazu verwendet werden kann, die Anzahl von Elementen eines hash_multimap-Elements in einen Bereich zwischen Elementen darzustellen, auf die von Iteratoren gezeigt wird.
Iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, mit dem jedes Element in einer hash_multimap 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_multimap-Element zu bestimmen.
key_type	Ein Typ, mit dem das Sortierschlüsselobjekt beschrieben wird, das jedes Element von hash_multimap bildet.
mapped_type	Ein Typ, der den in einer hash_multimap gespeicherten Datentyp darstellt.
Zeiger	Ein Typ, der einen Zeiger auf ein Element in einer hash_multimap bereitstellt.
Verweis	Ein Typ, der einen Verweis auf ein in einer hash_multimap gespeichertes Element bereitstellt.
reverse_iterator	Ein Typ, der einen bidirektionalen Iterator bereitstellt, mit dem ein Element in einem umgekehrten hash_multimap-Element gelesen oder geändert werden kann.
size_type	Eine Ganzzahltyp ohne Vorzeichen, der die Anzahl von Elementen in hash_multimap darstellen kann.
value_type	Eine Typ, der ein Funktionsobjekt bereitstellt, das zwei Elemente als Sortierschlüssel vergleichen kann, um die relative Position im hash_multimap-Element zu bestimmen.

Memberfunktionen

begin	Gibt ein Iterator zurück, der das erste Element im hash_multimap-Element adressiert.
hash_multimap::cbegin	Gibt einen konstanten Iterator zurück, der das erste Element im hash_multimap-Element adressiert.
hash_multimap::cend	Gibt einen konstanten Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines hash_multimap-Elements nachfolgt.
clear	Löscht alle Elemente einer hash_multimap auf.
count	Gibt die Anzahl von Elementen in einem hash_multimap-Element zurück, dessen Schlüssel dem von einem Parameter angegebenen Schlüssel entspricht.
hash_multimap::crbegin	Gibt einen konstanten Iterator zurück, der das erste Element im umgekehrten hash_multimap-Element adressiert.
hash_multimap::crend	Gibt einen konstanten Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines umgekehrten hash_multimap-Elements nachfolgt.
hash_multimap::emplace	Fügt ein Element ein, das vor Ort in ein hash_multimap-Element erstellt wird.
hash_multimap::emplace_hint	Fügt ein Element ein, das vor Ort mit einem Platzierungshinweis in ein hash_multimap-Element erstellt wird.
empty	Testet, ob ein hash_multimap-Element leer ist.
end	Gibt einen Iterator zurück, der den Speicherort adressiert, der dem letzten Element einem hash_multimap-Element nachfolgt.
equal_range	Gibt einen Iterator zurück, der den Speicherort adressiert, der dem letzten Element einem hash_multimap-Element nachfolgt.
Löschen	Entfernt ein Element oder eine Reihe von Elementen in einer hash_multimap aus angegebenen Speicherorten.
find	Gibt einen Iterator zurück, der die Position eines Elements in einem hash_multimap-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_multimap-Objekts zurück.
Einfügen	Fügt ein Element oder einen Elementbereich an einer angegebenen Position in das hash_multimap-Element ein.
key_comp	Ruft eine Kopie des Vergleichsobjekts ab, das zum Sortieren der Schlüssel in hash_multimap verwendet wird.
lower_bound	Gibt einen Iterator zum ersten Element in einem hash_multimap-Element mit einem Schlüsselwert zurück, der gleich oder größer ist, als ein angegebener Schlüssel.
max_size	Gibt die Maximallänge der hash_multimap zurück.
rbegin	Gibt einen Iterator zurück, der das erste Element in einem umgekehrten hash_multimap-Element adressiert.
rend	Gibt einen Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines umgekehrten hash_multimap-Elements nachfolgt.
size	Gibt eine neue Größe für eine hash_multimap an.
swap	Tauscht die Elemente zweier hash_multimapn.
upper_bound	Gibt einen Iterator zum ersten Element in einem hash_multimap-Element mit einem Schlüsselwert zurück, der größer ist, als ein angegebener Schlüssel.
value_comp	Ruft eine Kopie des Vergleichsobjekts ab, das zum Sortieren der Elementwerte in hash_multimap verwendet wird.