CKTIS / C++
std::multiset — un contenitore ordinato con duplicati
std::multiset di <set> memorizza le chiavi nell’ordine definito dal comparatore e ammette chiavi equivalenti. Scopri come funzionano la ricerca e il conteggio e distingui la rimozione di un elemento da quella di tutti gli elementi equivalenti.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> di <set> è un contenitore associativo ordinato: ogni elemento è anche una chiave. A differenza di std::set, ammette più chiavi equivalenti. Il std::less<Key> predefinito stabilisce un ordine crescente per i numeri; l’iterazione segue l’ordine del comparatore.
Compare deve definire un ordinamento debole stretto. Le chiavi a e b sono equivalenti quando vale !comp(a, b) && !comp(b, a), il che non implica necessariamente a == b. Gli elementi non si possono modificare tramite iteratori. Per cambiare una chiave, si può eliminare l’elemento e inserirne uno nuovo. Gli iteratori sono bidirezionali, non ad accesso casuale.
Con N elementi, l’inserimento ordinario e find, lower_bound e upper_bound hanno costo O(log N). find restituisce un elemento corrispondente oppure end(); count conta tutti gli equivalenti e equal_range individua il loro intervallo [first, last). Il conteggio costa O(log N + K), dove K è il numero di corrispondenze.
Attenzione: erase(key) rimuove tutti gli elementi equivalenti e ne restituisce il numero. erase(it) rimuove solo l’elemento indicato; passare end() non è valido. L’inserimento non invalida iteratori o riferimenti, mentre la rimozione invalida solo quelli che si riferiscono agli elementi rimossi.
L’esempio è destinato alla compilazione con -std=c++23; il comportamento in esecuzione in produzione non è attestato. La fonte è una bozza di standard in evoluzione, non una pubblicazione C++23 definitiva; questa voce non applica a C++23 le sue dichiarazioni constexpr più recenti.
Esempi
#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';
}
Risultato
count: 3 after one: 2 removed: 2 remaining: 1 2
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.