WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::multimap — geordnete Paare mit doppelten Schlüsseln

std::multimap aus <map> speichert Schlüssel-Wert-Paare in Schlüsselreihenfolge und erlaubt mehrere Elemente mit gleichwertigen Schlüsseln. equal_range liefert die gesamte passende Gruppe, während erase(key) alle Elemente dieser Gruppe entfernt.

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

Syntax

#include <map>
std::multimap<Key, T> name;
std::multimap<Key, T, Compare> name;

std::multimap<Key, T> aus <map> ist ein geordneter assoziativer Container. Anders als std::map erlaubt er mehrere Elemente mit gleichwertigen Schlüsseln. Die Iteration folgt Compare, standardmäßig std::less<Key>. Der Vergleichsoperator muss eine strikte schwache Ordnung definieren; Gleichwertigkeit bedeutet !comp(a, b) && !comp(b, a) und nicht notwendigerweise a == b.

Ein Element hat den Typ std::pair<const Key, T>: Über einen Iterator lässt sich der zugeordnete Wert ändern, nicht aber der Schlüssel. Ein gewöhnliches emplace fügt ein Element am Ende der Gruppe gleichwertiger Schlüssel ein. std::multimap stellt weder operator[] noch at bereit; es wählt nicht automatisch einen einzelnen Wert für einen Schlüssel aus.

equal_range(key) gibt zwei Iteratoren zurück, die den halboffenen Bereich aller Treffer begrenzen; gibt es keine Treffer, ist der Bereich leer. find(key) liefert nur einen Treffer oder end(). erase(key) entfernt alle Treffer und gibt deren Anzahl zurück; erase(it) entfernt ein einzelnes ausgewähltes Element. Bei N Elementen benötigen Suche und gewöhnliches Einfügen O(log N); das Durchlaufen von K Treffern nach equal_range benötigt insgesamt O(log N + K).

Im Beispiel behalten die beiden emplace-Aufrufe für Schlüssel 2 die Reihenfolge review, test bei; nach dem Entfernen dieser Gruppe bleibt ein Element übrig. Das Beispiel ist für C++23 vorgesehen. Das bereitgestellte Dokument ist ein fortlaufend bearbeiteter Entwurf und keine festgeschriebene C++23-Ausgabe; neuere Deklarationen im Entwurf belegen nicht ihre Verfügbarkeit in C++23. Ein Compiler-Flag im Repository bestätigt nicht die Produktionslaufzeit.

Beispiele

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<int, std::string> tasks;
    tasks.emplace(2, "review");
    tasks.emplace(1, "build");
    tasks.emplace(2, "test");

    const auto [first, last] = tasks.equal_range(2);
    for (auto it = first; it != last; ++it) {
        std::cout << it->first << ": " << it->second << '\n';
    }
    std::cout << "removed: " << tasks.erase(2) << '\n';
    std::cout << "remaining: " << tasks.size() << '\n';
}

Ergebnis

2: review
2: test
removed: 2
remaining: 1

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