Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::multiset — uređeni spremnik s duplikatima

std::multiset iz <set> pohranjuje ključeve prema poretku koji određuje komparator i dopušta ekvivalentne ključeve. Saznajte kako funkcioniraju pretraživanje i brojanje te razlikujte uklanjanje jednog elementa od uklanjanja svih ekvivalentnih elemenata.

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

Sintaksa

#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>

std::multiset<Key, Compare, Allocator> iz <set> uređeni je asocijativni spremnik: svaki je element ujedno ključ. Za razliku od std::set, dopušta više ekvivalentnih ključeva. Zadani std::less<Key> za brojeve daje uzlazni poredak; iteracija prolazi elemente prema poretku komparatora.

Compare mora definirati strogi slabi poredak. Ključevi a i b ekvivalentni su kada vrijedi !comp(a, b) && !comp(b, a), što ne mora značiti a == b. Elementi se ne mogu mijenjati putem iteratora. Želite li promijeniti ključ, možete ukloniti element i umetnuti novi. Iteratori su dvosmjerni, a ne sa slučajnim pristupom.

Za N elemenata uobičajeno umetanje te find, lower_bound i upper_bound imaju složenost O(log N). find vraća jedan odgovarajući element ili end(); count broji sve ekvivalentne elemente, a equal_range određuje njihov raspon [first, last). Brojanje ima složenost O(log N + K), gdje je K broj podudaranja.

Upozorenje: erase(key) uklanja sve ekvivalentne elemente i vraća njihov broj. erase(it) uklanja samo navedeni element; prosljeđivanje vrijednosti end() nije valjano. Umetanje ne poništava iteratore ni reference, dok uklanjanje poništava samo one koji se odnose na uklonjene elemente.

Primjer je namijenjen prevođenju s -std=c++23; ponašanje pri izvođenju u produkcijskom okruženju nije potvrđeno. Izvor je nacrt standarda koji se razvija, a ne konačna publikacija C++23; ovaj zapis ne prenosi njegove novije deklaracije constexpr na C++23.

Primjeri

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

Rezultat

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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori