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

CKTIS / C++

std::multiset — usporiadaný kontajner s duplicitami

std::multiset z <set> ukladá kľúče v poradí určenom porovnávacou funkciou a umožňuje ekvivalentné kľúče. Zistite, ako funguje vyhľadávanie a počítanie, a rozlišujte medzi odstránením jedného prvku a všetkých ekvivalentných prvkov.

Verzia: 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> z <set> je usporiadaný asociatívny kontajner: každý prvok je zároveň kľúčom. Na rozdiel od std::set umožňuje viacero ekvivalentných kľúčov. Predvolený std::less<Key> určuje pre čísla vzostupné poradie; iterácia prechádza prvky v poradí podľa porovnávacej funkcie.

Compare musí definovať ostré slabé usporiadanie. Kľúče a a b sú ekvivalentné, keď platí !comp(a, b) && !comp(b, a), čo nemusí znamenať a == b. Prvky nemožno meniť prostredníctvom iterátorov. Ak chcete zmeniť kľúč, môžete prvok odstrániť a vložiť nový. Iterátory sú obojsmerné, nie s náhodným prístupom.

Pre N prvkov majú bežné vkladanie a operácie find, lower_bound a upper_bound zložitosť O(log N). find vráti jeden zodpovedajúci prvok alebo end(); count spočíta všetky ekvivalentné prvky a equal_range určí ich rozsah [first, last). Počítanie má zložitosť O(log N + K), kde K je počet zhôd.

Pozor: erase(key) odstráni všetky ekvivalentné prvky a vráti ich počet. erase(it) odstráni iba určený prvok; odovzdať end() je neplatné. Vkladanie nezneplatňuje iterátory ani referencie, zatiaľ čo mazanie zneplatní iba tie, ktoré odkazujú na odstránené prvky.

Príklad je určený na kompiláciu s -std=c++23; správanie pri spustení v produkčnom prostredí nie je potvrdené. Zdroj je priebežne vyvíjaný návrh štandardu, nie konečné vydanie C++23; tento záznam neprenáša jeho novšie deklarácie constexpr do C++23.

Príklady

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

Výsledok

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

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

Zdroje