Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes