Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::multimap — usporiadané dvojice s duplicitnými kľúčmi

std::multimap z <map> ukladá dvojice kľúč–hodnota v poradí kľúčov a umožňuje viac prvkov s ekvivalentnými kľúčmi. equal_range získa celú zodpovedajúcu skupinu, zatiaľ čo erase(key) odstráni všetky jej prvky.

Verzia: 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> z <map> je usporiadaný asociatívny kontajner. Na rozdiel od std::map umožňuje viac prvkov s ekvivalentnými kľúčmi. Iterácia sa riadi podľa Compare, ktorého predvolenou hodnotou je std::less<Key>. Komparátor musí definovať striktné slabé usporiadanie; ekvivalencia znamená !comp(a, b) && !comp(b, a), nie nevyhnutne a == b.

Prvok má typ std::pair<const Key, T>: pomocou iterátora možno zmeniť mapovanú hodnotu, nie však kľúč. Bežné emplace pridá prvok na koniec skupiny ekvivalentných kľúčov. std::multimap neposkytuje operator[] ani at; automaticky nevyberá jednu hodnotu pre kľúč.

equal_range(key) vracia dvojicu iterátorov ohraničujúcich polootvorený rozsah všetkých zhôd; ak žiadne zhody neexistujú, rozsah je prázdny. find(key) vracia iba jednu zhodu alebo end(). erase(key) odstráni všetky zhody a vráti ich počet; erase(it) odstráni jeden vybraný prvok. Pre N prvkov majú vyhľadávanie a bežné vkladanie zložitosť O(log N); prechod cez K zhôd po equal_range stojí celkovo O(log N + K).

V príklade zachovajú dve volania emplace pre kľúč 2 poradie review, test; po odstránení tejto skupiny zostane jeden prvok. Príklad je určený pre C++23. Dodaný dokument je priebežne aktualizovaný návrh, nie zmrazené vydanie C++23; novšie deklarácie v návrhu nedokazujú dostupnosť v C++23. Príznak kompilátora v repozitári nepotvrdzuje produkčné prostredie.

Príklady

#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';
}

Výsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje