multiset-Klasse

Artikel
06/09/2015

Die Standardvorlagenbibliothek-Multimengenklasse wird zum Speichern und Abrufen von Daten aus einer Sammlung verwendet, in der die Werte der enthaltenen Elemente nicht eindeutig sein müssen und in der sie als die Schlüsselwerte dienen, nach denen die Daten automatisch sortiert werden. Der Schlüsselwert eines Elements in einer Multimenge darf nicht direkt geändert werden. Stattdessen müssen alte Werte gelöscht und Elemente mit neuen Werten eingefügt werden.

template < 
   class Key,  
   class Compare=less<Key>,  
   class Allocator=allocator<Key>  
> 
class multiset

Parameter

Key
Der in der Multimenge zu speichernde Elementdatentyp.
Compare
Der Typ, der ein Funktionsobjekt bereitstellt, das zwei Elementwerte als Sortierschlüssel vergleichen kann, um deren relative Reihenfolge in der Multimenge zu bestimmen. Das binäre Prädikat less<Key> ist der Standardwert.
Allocator
Der Typ, mit dem das gespeicherte Zuordnungsobjekt dargestellt wird, mit dem Details zum Belegen und Freigeben des Arbeitsspeichers der Multimenge gekapselt werden. Der Standardwert ist allocator*<Key>.*

Hinweise

Die STL-Multimengenklasse ist:

Ein assoziativer Container, der ein Container variabler Größe ist, der den effizienten Abruf von Elementwerten auf Grundlage eines zugeordneten Schlüsselwerts unterstützt.
Umkehrbar, da bidirektionale Iteratoren für den Zugriff auf die Elemente bereitgestellt werden.
Sortiert, da die Elemente anhand von Schlüsselwerten innerhalb des Containers mit einer angegebenen Vergleichsfunktion sortiert werden.
Mehrfach insofern, als die Elemente keine eindeutigen Schlüssel aufweisen müssen, damit ein Schlüsselwert über viele zugeordnete Elementdatenwerte verfügen kann.
Ein einfacher assoziativer Container, da die Elementwerte den Schlüsselwerten entsprechen.
Eine Vorlagenklasse, da die bereitgestellten Funktionen generisch und daher unabhängig vom angegebenen Datentyp sind, der als Elemente enthalten ist. Der zu verwendende Datentyp wird stattdessen in der Klassenvorlage zusammen mit der Vergleichsfunktion und der Zuweisung als Parameter angegeben.

Der von der Multimengenklasse bereitgestellte Iterator ist ein bidirektionaler Iterator. Die Klassenmemberfunktionen insert und multiset weisen allerdings Versionen auf, die 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 eigenen Satz 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 ein minimaler Funktionssatz, allerdings genügt er, um sinnvoll über einen Bereich von Iteratoren (First, Last) im Kontext der Klassenmemberfunktionen zu sprechen.

Die Auswahl des Containertyps sollte im Allgemeinen auf Grundlage des für die Anwendung erforderlichen Suchen und Einfügetyps erfolgen. Assoziative Container sind für Such-, Einfüge- und Entfernvorgänge optimiert. Die Memberfunktionen, die diese Vorgänge explizit unterstützen, sind effizient und führen sie in einer Zeit aus, die zum Logarithmus der Elementanzahl im Container im Durchschnitt proportional ist. 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.

Die Multimenge 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. Die Elemente einer Multimenge können Mehrfache sein und als eigene Sortierschlüssel dienen, sodass Schlüssel nicht eindeutig sind. Ein Modell für diesen Typ der Struktur ist eine geordnete Liste von z. B. Wörtern, in denen die Wörter möglicherweise mehrmals auftreten. Wenn mehrfaches Vorkommen der Wörter nicht zugelassen wurde, ist eine Menge die geeignete Containerstruktur. Wenn eindeutige Definitionen als Werte zur Liste von eindeutigen Schlüsselwörtern angefügt wurden, ist eine Zuordnung eine äquivalente Struktur, um diese Daten zu enthalten. Wenn stattdessen die Definitionen nicht eindeutig sind, ist eine Mehrfachzuordnung der geeignete Container.

Die Multimenge sortiert die von ihr gesteuerten Elemente, indem ein gespeichertes Funktionsobjekt vom Typ Compare aufgerufen wird. Bei diesem gespeicherten Objekt handelt es sich um eine Vergleichsfunktion, auf die zugegriffen werden kann, indem die key_comp-Memberfunktion aufgerufen wird. 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 eine Multimenge 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(y,x) "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.

Konstruktoren

multiset

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

Typedefs

allocator_type	Eine Typedef für die allocator-Klasse für das multiset-Objekt.
const_iterator	Eine Typedef für einen bidirektionalen Iterator, der ein const-Element in der multiset lesen kann.
const_pointer	Eine Typedef für einen Zeiger auf ein const-Element in einer multiset.
const_reference	Eine Typedef für einen Verweis auf ein const-Element, das in einer multiset zum Lesen und Ausführen von const-Vorgängen gespeichert ist.
const_reverse_iterator	Eine Typedef für einen bidirektionalen Iterator, der ein beliebiges const-Element in der multiset lesen kann.
difference_type	Ein Ganzzahltyp mit Vorzeichen für die Anzahl von Elementen einer multiset in einem Bereich zwischen Elementen, auf die von Iteratoren gezeigt wird.
Iterator	Eine Typedef für einen bidirektionalen Iterator, der ein beliebiges Element in einer multiset lesen oder ändern kann.
key_compare	Eine Typedef für ein Funktionsobjekt, das zwei Sortierschlüssel vergleichen kann, um die relative Position von zwei Elementen in der multiset zu bestimmen.
key_type	Eine Typedef für ein Funktionsobjekt, das zwei Sortierschlüssel vergleichen kann, um die relative Position von zwei Elementen in der multiset zu bestimmen.
pointer	Eine Typedef für einen Zeiger auf ein Element in einer multiset.
Verweis	Eine Typedef für einen Verweis auf ein in einer multiset gespeichertes Element.
reverse_iterator	Eine Typedef für einen bidirektionalen Iterator, der ein Element in einer umgekehrten multiset lesen oder ändern kann.
size_type	Eine Ganzzahltyp ohne Vorzeichen, der die Anzahl von Elementen in multiset darstellen kann.
value_compare	Die Typedef für ein Funktionsobjekt, das zwei Elemente als Sortierschlüssel vergleichen kann, um ihre relative Position in der multiset zu bestimmen.
value_type	Eine Typedef, die ein Objekt beschreibt, das als Element und multiset in seiner Kapazität als Wert gespeichert wird.

Memberfunktionen

begin	Gibt einen Iterator zurück, der auf das erste Element in der multiset zeigt.
cbegin	Gibt einen konstanten Iterator zurück, der das erste Element in der multiset adressiert.
cend	Gibt einen konstanten Iterator zurück, der den Speicherort adressiert, der dem letzten Element eines multiset-Elements nachfolgt.
clear	Löscht alle Elemente einer multiset auf.
count	Gibt die Anzahl von Elementen in einer multiset zurück, deren Schlüssel dem als Parameter angegebenen Schlüssel entspricht.
crbegin	Gibt einen const-Iterator zurück, der das erste Element in einer umgekehrten Menge adressiert.
crend	Gibt einen const-Iterator zurück, der den Speicherort adressiert, der dem letzten Element einer umgekehrten Menge nachfolgt.
emplace	Fügt ein Element ein, das vor Ort in ein multiset-Element erstellt wird.
emplace_hint	Fügt ein Element ein, das vor Ort mit einem Platzierungshinweis in ein multiset-Element erstellt wird.
empty	Testet, ob ein multiset-Element leer ist.
end	Gibt einen Iterator zurück, der auf den Speicherort zeigt, der hinter dem letzten Element einer multiset liegt.
equal_range	Gibt ein Paar von Iteratoren zurück. Der erste Iterator im Paar zeigt auf das erste Element in multiset mit einem Schlüssel, der größer ist, als ein bestimmter Schlüssel. Der zweite Iterator im Paar zeigt auf das erste Element in der multiset mit einem Schlüssel, der größer oder gleich dem Schlüssel ist.
Löschen	Es wird ein Element oder ein Bereich von Elementen in einem multiset von angegebenen Speicherorten entfernt, oder es werden die einem angegebenen Schlüssel entsprechenden Elemente entfernt.
find	Gibt einen Iterator zurück, der auf den ersten Speicherort eines Elements in einer multiset zeigt, der einen Schlüssel gleich einem angegebenen Schlüssel aufweist.
get_allocator	Gibt eine Kopie des zum Erstellen der multiset verwendeten allocator-Objekts zurück.
Einfügen	Fügt ein Element oder einen Elementbereich in ein multiset-Element ein.
key_comp	Stellt ein Funktionsobjekt bereit, das zwei Sortierschlüssel vergleichen kann, um die relative Position von zwei Elementen in der multiset zu bestimmen.
lower_bound	Gibt einen Iterator zum ersten Element in einem multiset-Element mit einem Schlüssel zurück, der gleich oder größer ist, als ein angegebener Schlüssel.
max_size	Gibt die Maximallänge der multiset zurück.
rbegin	Gibt einen Iterator zurück, der auf das erste Element in einer umgekehrten multiset zeigt.
rend	Gibt einen Iterator zurück, der auf den Speicherort zeigt, der auf das letzte Element einer umgekehrten multiset folgt.
size	Gibt die Anzahl von Elementen in einer multiset zurück.
swap	Tauscht die Elemente zweier multisetn.
upper_bound	Gibt einen Iterator zum ersten Element in einem multiset-Element mit einem Schlüssel zurück, der größer als ein angegebener Schlüssel ist.
value_comp	Ruft eine Kopie des Vergleichsobjekts ab, das verwendet wird, um Elementwerte in einer multiset zu sortieren.

Operators

operator=

Ersetzt die Elemente eines multiset-Elements durch eine Kopie eines anderen multiset-Elements.

Anforderungen

Header: <set>

Namespace: std

Siehe auch

Share via

multiset-Klasse

Parameter

Hinweise

Konstruktoren

Typedefs

Memberfunktionen

Operators

Anforderungen

Siehe auch

Referenz

Konzepte

Weitere Ressourcen

Zusätzliche Ressourcen