CKTIS / C++
std::multiset — uporządkowany kontener z duplikatami
std::multiset z nagłówka <set> przechowuje klucze w porządku określonym przez komparator i dopuszcza klucze równoważne. Poznaj wyszukiwanie, zliczanie oraz różnicę między usunięciem jednego elementu a wszystkich jego odpowiedników.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> z nagłówka <set> to uporządkowany kontener asocjacyjny: każdy element jest jednocześnie kluczem. W przeciwieństwie do std::set dopuszcza wiele równoważnych kluczy. Domyślny std::less<Key> daje dla liczb porządek rosnący; iteracja odwiedza elementy w porządku komparatora.
Compare musi definiować ścisły słaby porządek. Klucze a i b są równoważne, gdy !comp(a, b) && !comp(b, a), co nie musi oznaczać a == b. Nie można zmieniać elementów przez iteratory. Aby zmienić klucz, można usunąć element i wstawić nowy. Iteratory są dwukierunkowe, nie losowego dostępu.
Dla N elementów zwykłe wstawienie oraz find, lower_bound i upper_bound mają złożoność O(log N). find zwraca jeden pasujący element albo end(); count zlicza wszystkie odpowiedniki, a equal_range wyznacza ich zakres [first, last). Zliczanie kosztuje O(log N + K), gdzie K to liczba dopasowań.
Uwaga: erase(key) usuwa wszystkie równoważne elementy i zwraca ich liczbę. erase(it) usuwa tylko wskazany element; nie wolno przekazać end(). Wstawianie nie unieważnia iteratorów ani referencji, a usuwanie unieważnia tylko te odnoszące się do usuniętych elementów.
Przykład jest przeznaczony do kompilacji z -std=c++23; działania w środowisku produkcyjnym nie potwierdzono. Źródło jest rozwijanym szkicem standardu, nie zamrożoną publikacją C++23; wpis nie przenosi jego nowszych deklaracji constexpr na C++23.
Przykłady
#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';
}
Wynik
count: 3 after one: 2 removed: 2 remaining: 1 2
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.