WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::multiset — ein geordneter Container mit Duplikaten

std::multiset aus <set> speichert Schlüssel in einer durch den Vergleichsoperator festgelegten Reihenfolge und erlaubt äquivalente Schlüssel. Erfahre, wie Suchen und Zählen funktionieren und worin sich das Löschen eines Elements vom Löschen aller äquivalenten Elemente unterscheidet.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>

std::multiset<Key, Compare, Allocator> aus <set> ist ein geordneter assoziativer Container: Jedes Element ist zugleich ein Schlüssel. Anders als std::set erlaubt er mehrere äquivalente Schlüssel. Das Standard-std::less<Key> ergibt bei Zahlen aufsteigende Reihenfolge; die Iteration folgt der Reihenfolge des Vergleichsoperators.

Compare muss eine strikte schwache Ordnung definieren. Schlüssel a und b sind äquivalent, wenn !comp(a, b) && !comp(b, a) gilt; das bedeutet nicht zwingend a == b. Elemente lassen sich nicht über Iteratoren ändern. Um einen Schlüssel zu ändern, kann man das Element löschen und ein neues einfügen. Iteratoren sind bidirektional, aber keine Iteratoren mit wahlfreiem Zugriff.

Bei N Elementen haben gewöhnliches Einfügen sowie find, lower_bound und upper_bound eine Komplexität von O(log N). find liefert ein passendes Element oder end(); count zählt alle äquivalenten Elemente, und equal_range bestimmt deren Bereich [first, last). Das Zählen kostet O(log N + K), wobei K die Anzahl der Treffer ist.

Achtung: erase(key) löscht alle äquivalenten Elemente und gibt deren Anzahl zurück. erase(it) löscht nur das angegebene Element; end() darf nicht übergeben werden. Einfügen macht Iteratoren und Referenzen nicht ungültig, Löschen hingegen nur solche, die auf gelöschte Elemente verweisen.

Das Beispiel ist für die Kompilierung mit -std=c++23 vorgesehen; das Laufzeitverhalten in einer Produktionsumgebung ist nicht bestätigt. Die Quelle ist ein fortlaufend bearbeiteter Standardentwurf, keine endgültige C++23-Veröffentlichung; dieser Eintrag überträgt dessen neuere constexpr-Deklarationen nicht auf C++23.

Beispiele

#include <iostream>
#include <set>

int main() {
    std::multiset<int> values{3, 1, 3, 2};
    values.insert(3);
    std::cout << "count: " << values.count(3) << '\n';

    auto it = values.find(3);
    if (it != values.end()) {
        values.erase(it);
    }
    std::cout << "after one: " << values.count(3) << '\n';

    auto removed = values.erase(3);
    std::cout << "removed: " << removed << '\n';
    std::cout << "remaining:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Ergebnis

count: 3
after one: 2
removed: 2
remaining: 1 2

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen