CKTIS / C++
std::multiset — um contentor ordenado com duplicados
std::multiset de <set> guarda chaves pela ordem definida pelo comparador e permite chaves equivalentes. Saiba como funcionam a pesquisa e a contagem e distinga a remoção de um elemento da remoção de todos os elementos equivalentes.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> de <set> é um contentor associativo ordenado: cada elemento é também uma chave. Ao contrário de std::set, permite várias chaves equivalentes. O std::less<Key> predefinido estabelece uma ordem crescente para números; a iteração percorre os elementos pela ordem do comparador.
Compare tem de definir uma ordem fraca estrita. As chaves a e b são equivalentes quando se verifica !comp(a, b) && !comp(b, a), o que não significa necessariamente a == b. Não é possível modificar os elementos através de iteradores. Para alterar uma chave, pode eliminar o elemento e inserir um novo. Os iteradores são bidirecionais, não de acesso aleatório.
Para N elementos, a inserção normal e find, lower_bound e upper_bound têm custo O(log N). find devolve um elemento correspondente ou end(); count conta todos os equivalentes e equal_range determina o respetivo intervalo [first, last). A contagem custa O(log N + K), em que K é o número de correspondências.
Atenção: erase(key) elimina todos os elementos equivalentes e devolve o respetivo número. erase(it) elimina apenas o elemento indicado; passar end() é inválido. A inserção não invalida iteradores nem referências, enquanto a eliminação invalida apenas os que se referem aos elementos eliminados.
O exemplo destina-se a compilação com -std=c++23; o comportamento em execução num ambiente de produção não está atestado. A fonte é um projeto de norma em evolução, não uma publicação C++23 definitiva; esta entrada não aplica a C++23 as declarações constexpr mais recentes.
Exemplos
#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';
}
Resultado
count: 3 after one: 2 removed: 2 remaining: 1 2
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.