CKTIS / C++
std::multiset — un contenedor ordenado con duplicados
std::multiset, de <set>, almacena claves en el orden definido por el comparador y permite claves equivalentes. Aprende cómo funcionan la búsqueda y el recuento, y distingue entre eliminar un elemento y eliminar todos los equivalentes.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> de <set> es un contenedor asociativo ordenado: cada elemento es también una clave. A diferencia de std::set, permite varias claves equivalentes. El std::less<Key> predeterminado establece un orden ascendente para los números; la iteración recorre los elementos en el orden del comparador.
Compare debe definir un orden débil estricto. Las claves a y b son equivalentes cuando se cumple !comp(a, b) && !comp(b, a), lo que no implica necesariamente a == b. No se pueden modificar los elementos mediante iteradores. Para cambiar una clave, puedes borrar el elemento e insertar uno nuevo. Los iteradores son bidireccionales, no de acceso aleatorio.
Para N elementos, la inserción ordinaria y find, lower_bound y upper_bound tienen un coste de O(log N). find devuelve un elemento coincidente o end(); count cuenta todos los equivalentes y equal_range determina su intervalo [first, last). El recuento cuesta O(log N + K), donde K es el número de coincidencias.
Atención: erase(key) elimina todos los elementos equivalentes y devuelve su cantidad. erase(it) elimina solo el elemento indicado; pasar end() no es válido. La inserción no invalida iteradores ni referencias, mientras que el borrado solo invalida los que hacen referencia a los elementos eliminados.
El ejemplo está pensado para compilarse con -std=c++23; no se certifica su comportamiento en tiempo de ejecución en producción. La fuente es un borrador de norma en evolución, no una publicación definitiva de C++23; esta entrada no aplica a C++23 sus declaraciones constexpr más recientes.
Ejemplos
#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
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.