Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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.

Fuentes