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

CKTIS / C++

std::set — uma coleção ordenada de chaves únicas

std::set, de <set>, armazena chaves únicas pela ordem do comparador. Aprende a inserir e pesquisar, conhece as diferenças entre find, contains, count e equal_range e sabe como verificar end() em segurança.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <set>
std::set<Key> values;
auto [it, inserted] = values.insert(key);
auto found = values.find(key);
bool present = found != values.end();
bool exists = values.contains(key);
auto occurrences = values.count(key);
auto [first, last] = values.equal_range(key);

std::set<Key> de <set> é um contentor associativo ordenado. Cada elemento é também uma chave; o comparador predefinido std::less<Key> ordena os números inteiros por ordem crescente. Unicidade significa equivalência segundo o comparador: !comp(a, b) && !comp(b, a), não necessariamente a == b. O comparador tem de estabelecer uma ordem fraca estrita.

A sobrecarga habitual de std::set::insert(key) para um único valor devolve um par: um iterador para o elemento inserido ou já existente e um bool que indica se ocorreu a inserção. Uma chave equivalente não é adicionada novamente. std::set::find(key) devolve um iterador para um elemento equivalente ou std::set::end(). end() aponta para depois do último elemento: verifica it != values.end() antes de desreferenciares o resultado de uma pesquisa.

std::set::contains(key) devolve um valor booleano que indica se a chave está presente. std::set::count(key) devolve o número de elementos equivalentes, aqui sempre 0 ou 1. std::set::equal_range(key) devolve dois iteradores que descrevem o intervalo semiaberto [first, last) dos elementos equivalentes: vazio ou com um elemento. Um intervalo vazio significa first == last, mas não necessariamente first == values.end().

A inserção habitual de um único valor e as operações de pesquisa indicadas têm complexidade O(log n); end() demora tempo constante. Não é possível modificar as chaves através de iteradores. O exemplo destina-se a ser compilado com -std=c++23. O documento fornecido é um rascunho em evolução, não uma publicação C++23 definitiva; a opção do compilador do repositório não comprova o suporte em execução em produção.

Exemplos

#include <iostream>
#include <set>

int main() {
    std::set<int> values{3, 1, 3};
    auto [it, inserted] = values.insert(2);
    auto duplicate = values.insert(3);

    std::cout << std::boolalpha;
    std::cout << "insert: " << *it << ' ' << inserted << '\n';
    std::cout << "duplicate: " << duplicate.second << '\n';
    std::cout << "ordered:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';

    auto found = values.find(2);
    if (found != values.end()) {
        std::cout << "find: " << *found << '\n';
    }
    std::cout << "contains 4: " << values.contains(4) << '\n';
    std::cout << "count 3: " << values.count(3) << '\n';

    auto [first, last] = values.equal_range(2);
    std::cout << "equal_range 2:";
    for (auto current = first; current != last; ++current) {
        std::cout << ' ' << *current;
    }
    std::cout << '\n';
}

Resultado

insert: 2 true
duplicate: false
ordered: 1 2 3
find: 2
contains 4: false
count 3: 1
equal_range 2: 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