Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::set — una raccolta ordinata di chiavi univoche

std::set, definito in <set>, memorizza chiavi univoche nell’ordine del comparatore. Scopri l’inserimento e la ricerca, le differenze tra find, contains, count ed equal_range e come controllare end() in sicurezza.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#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> di <set> è un contenitore associativo ordinato. Ogni elemento è anche una chiave; il comparatore predefinito std::less<Key> ordina gli interi in modo crescente. L’unicità significa equivalenza secondo il comparatore: !comp(a, b) && !comp(b, a), non necessariamente a == b. Il comparatore deve definire un ordinamento stretto debole.

La normale versione di std::set::insert(key) per un singolo valore restituisce una coppia: un iteratore all’elemento inserito o già presente e un bool che indica se l’inserimento è avvenuto. Una chiave equivalente non viene aggiunta una seconda volta. std::set::find(key) restituisce un iteratore a un elemento equivalente oppure std::set::end(). end() punta oltre l’ultimo elemento: verifica it != values.end() prima di dereferenziare il risultato di una ricerca.

std::set::contains(key) restituisce un valore booleano che indica la presenza della chiave. std::set::count(key) restituisce il numero di elementi equivalenti, qui sempre 0 o 1. std::set::equal_range(key) restituisce due iteratori che descrivono l’intervallo semiaperto [first, last) degli elementi equivalenti: vuoto o contenente un elemento. Un intervallo vuoto significa first == last, ma non necessariamente first == values.end().

Il normale inserimento di un singolo valore e le operazioni di ricerca elencate hanno complessità O(log n); end() richiede tempo costante. Le chiavi non possono essere modificate tramite iteratori. L’esempio è pensato per essere compilato con -std=c++23. Il documento fornito è una bozza in evoluzione, non una pubblicazione C++23 definitiva; il flag del compilatore del repository non attesta il supporto in esecuzione in produzione.

Esempi

#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';
}

Risultato

insert: 2 true
duplicate: false
ordered: 1 2 3
find: 2
contains 4: false
count 3: 1
equal_range 2: 2

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti