KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::multiset — een geordende container met duplicaten

std::multiset uit <set> bewaart sleutels in de door de vergelijker bepaalde volgorde en staat equivalente sleutels toe. Ontdek hoe zoeken en tellen werken en wat het verschil is tussen één element verwijderen en alle equivalente elementen verwijderen.

Versie: 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> uit <set> is een geordende associatieve container: elk element is zelf een sleutel. In tegenstelling tot std::set zijn meerdere equivalente sleutels toegestaan. De standaard-std::less<Key> geeft getallen een oplopende volgorde; iteratie volgt de volgorde van de vergelijker.

Compare moet een strikte zwakke ordening definiëren. Sleutels a en b zijn equivalent wanneer !comp(a, b) && !comp(b, a) geldt; dat betekent niet noodzakelijk a == b. Elementen kunnen niet via iterators worden gewijzigd. Om een sleutel te veranderen, kun je het element wissen en een nieuw element invoegen. Iterators zijn bidirectioneel, niet geschikt voor willekeurige toegang.

Bij N elementen hebben gewone invoeging en find, lower_bound en upper_bound een complexiteit van O(log N). find geeft één overeenkomend element of end() terug; count telt alle equivalente elementen en equal_range bepaalt hun bereik [first, last). Tellen kost O(log N + K), waarbij K het aantal overeenkomsten is.

Let op: erase(key) verwijdert alle equivalente elementen en geeft hun aantal terug. erase(it) verwijdert alleen het aangewezen element; end() meegeven is ongeldig. Invoegen maakt iterators en verwijzingen niet ongeldig; wissen maakt alleen die ongeldig die naar gewiste elementen verwijzen.

Het voorbeeld is bedoeld om te compileren met -std=c++23; gedrag tijdens uitvoering in een productieomgeving is niet bevestigd. De bron is een voortdurend bijgewerkt concept van de standaard, geen definitieve C++23-publicatie; dit artikel past de nieuwere constexpr-declaraties ervan niet toe op C++23.

Voorbeelden

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

Resultaat

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

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen