Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::multiset — uspořádaný kontejner s duplicitami

std::multiset z <set> ukládá klíče v pořadí určeném porovnávací funkcí a umožňuje ekvivalentní klíče. Zjistěte, jak funguje vyhledávání a počítání, a rozlišujte mezi odstraněním jednoho prvku a všech ekvivalentních prvků.

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

Syntaxe

#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 uspořádaný asociativní kontejner: každý prvek je zároveň klíčem. Na rozdíl od std::set umožňuje více ekvivalentních klíčů. Výchozí std::less<Key> určuje pro čísla vzestupné pořadí; iterace prochází prvky v pořadí daném porovnávací funkcí.

Compare musí definovat ostré slabé uspořádání. Klíče a a b jsou ekvivalentní, pokud platí !comp(a, b) && !comp(b, a), což nemusí znamenat a == b. Prvky nelze měnit prostřednictvím iterátorů. Chcete-li změnit klíč, můžete prvek odstranit a vložit nový. Iterátory jsou obousměrné, nikoli s náhodným přístupem.

Pro N prvků mají běžné vkládání a operace find, lower_bound a upper_bound složitost O(log N). find vrátí jeden odpovídající prvek nebo end(); count spočítá všechny ekvivalentní prvky a equal_range určí jejich rozsah [first, last). Počítání má složitost O(log N + K), kde K je počet shod.

Pozor: erase(key) odstraní všechny ekvivalentní prvky a vrátí jejich počet. erase(it) odstraní pouze určený prvek; předat end() je neplatné. Vkládání nezneplatňuje iterátory ani reference, zatímco mazání zneplatní pouze ty, které odkazují na odstraněné prvky.

Příklad je určen ke kompilaci s -std=c++23; chování při běhu v produkčním prostředí není potvrzeno. Zdroj je průběžně vyvíjený návrh standardu, nikoli konečné vydání C++23; tento záznam nepřenáší jeho novější deklarace constexpr do C++23.

Pří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ýsledek

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

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje