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.