Gli insiemi sono un tipo di contenitore associativo in cui ogni elemento deve essere unico perché il valore dell'elemento lo identifica. I valori vengono memorizzati in un ordine specifico, ovvero ascendente o discendente.
IL std::impostato fa parte della libreria di modelli standard (STL) C++ ed è definita all'interno di file di intestazione.
Sintassi:
.net tutorial
std::set set_name;>
Tipo di dati: Set può assumere qualsiasi tipo di dati a seconda dei valori, ad es. int, carattere, float, ecc.
Esempio:
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> Programma:
C++
// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> >std::set<>char>>a;> >a.insert(>'G'>);> >a.insert(>'F'>);> >a.insert(>'G'>);> >for> (>auto>& str : a) {> >std::cout << str <<>' '>;> >}> >std::cout <<>'
'>;> >return> 0;> }> |
>
>Produzione
F G>
Complessità temporale: O(N) // N è la dimensione dell'insieme.
Spazio ausiliario: SU)
Il motivo per cui ha stampato solo F e G è che set non accetta più stessi valori, accetta solo un valore univoco. Possiamo usare Multiinsieme se vogliamo memorizzare più stessi valori.
Imposta ordinato in ordine decrescente
Per impostazione predefinita, std::set è ordinato in ordine crescente. Tuttavia, abbiamo la possibilità di modificare l'ordinamento utilizzando la seguente sintassi.
std::set set_name;>
Esempio:
C++
'algoritmo di Kruskal'
// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> >set<>int>, greater<>int>>>s1;> >s1.insert(10);> >s1.insert(5);> >s1.insert(12);> >s1.insert(4);> >for> (>auto> i : s1) {> >cout << i <<>' '>;> >}> >return> 0;> }> |
>
>Produzione
12 10 5 4>
Complessità temporale: O(N) // N è la dimensione dell'insieme.
Spazio ausiliario: SU)
Nota: Possiamo utilizzare qualsiasi comparatore al posto del maggiore per impostare un ordinamento personalizzato.
Proprietà
- Memorizzazione dell'ordine – Il set memorizza gli elementi smistato ordine.
- Caratteristiche dei valori – Tutti gli elementi di un insieme hanno valori unici .
- Valori Natura – Il valore dell'elemento non può essere modificato una volta aggiunto all'insieme, sebbene sia possibile rimuovere e quindi aggiungere il valore modificato di quell'elemento. Quindi, i valori Sono immutabile .
- Tecnica di ricerca – I set seguono il Albero di ricerca binario implementazione.
- Organizzazione dell'ordine – I valori in un set sono non indicizzato .
Nota: Per memorizzare gli elementi in un ordine non ordinato (casuale), set_non ordinato() può essere utilizzata.
Alcune funzioni di base associate al set
- inizio() – Restituisce un iteratore al primo elemento del set.
- FINE() – Restituisce un iteratore all'elemento teorico che segue l'ultimo elemento dell'insieme.
- misurare() – Restituisce il numero di elementi nell'insieme.
- dimensione_massima() – Restituisce il numero massimo di elementi che l'insieme può contenere.
- vuoto() – Restituisce se il set è vuoto.
Le complessità temporali per eseguire varie operazioni sui set sono:
- Inserimento di Elementi – O(logN)
- Cancellazione di elementi – O(logN)
CPP
stringa.confronta C#
// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> >// empty set container> >set<>int>, greater<>int>>>s1;> >// insert elements in random order> >s1.insert(40);> >s1.insert(30);> >s1.insert(60);> >s1.insert(20);> >s1.insert(50);> >// only one 50 will be added to the set> >s1.insert(50);> >s1.insert(10);> >// printing set s1> >set<>int>, greater<>int>>>::iteratore itr;> >cout <<>'
The set s1 is :
'>;> >for> (itr = s1.begin(); itr != s1.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// assigning the elements from s1 to s2> >set<>int>>s2(s1.begin(), s1.end());> >// print all elements of the set s2> >cout <<>'
The set s2 after assign from s1 is :
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// remove all elements up to 30 in s2> >cout <<>'
s2 after removal of elements less than 30 '> >':
'>;> >s2.erase(s2.begin(), s2.find(30));> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >// remove element with value 50 in s2> >int> num;> >num = s2.erase(50);> >cout <<>'
s2.erase(50) : '>;> >cout << num <<>' removed
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// lower bound and upper bound for set s1> >cout <<>'s1.lower_bound(40) : '> ><< *s1.lower_bound(40) << endl;> >cout <<>'s1.upper_bound(40) : '> ><< *s1.upper_bound(40) << endl;> >// lower bound and upper bound for set s2> >cout <<>'s2.lower_bound(40) : '> ><< *s2.lower_bound(40) << endl;> >cout <<>'s2.upper_bound(40) : '> ><< *s2.upper_bound(40) << endl;> >return> 0;> }> |
>
>
npm svuota la cacheProduzione
The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60>
Diversa funzione di Set in C++ STL
| Funzione | Descrizione |
|---|---|
| inizio() | Restituisce un iteratore al primo elemento del set. |
| FINE() | Restituisce un iteratore all'elemento teorico che segue l'ultimo elemento del set. |
| rbegin() | Restituisce un iteratore inverso che punta all'ultimo elemento nel contenitore. |
| rendere() | Restituisce un iteratore inverso che punta all'elemento teorico subito prima del primo elemento nel contenitore dell'insieme. |
| crbegin() | Restituisce un iteratore costante che punta all'ultimo elemento nel contenitore. |
| cred() | Restituisce un iteratore costante che punta alla posizione appena prima del primo elemento nel contenitore. |
| cbegin() | Restituisce un iteratore costante che punta al primo elemento nel contenitore. |
| alcuni() | Restituisce un iteratore costante che punta alla posizione dopo l'ultimo elemento nel contenitore. |
| misurare() | Restituisce il numero di elementi nell'insieme. |
| dimensione_massima() | Restituisce il numero massimo di elementi che l'insieme può contenere. |
| vuoto() | Restituisce se il set è vuoto. |
| inserisci(const g) | Aggiunge un nuovo elemento 'g' al set. |
| inserimento dell'iteratore (posizione dell'iteratore, const g) | Aggiunge un nuovo elemento 'g' nella posizione puntata dall'iteratore. |
| cancella(posizione dell'iteratore) | Rimuove l'elemento nella posizione indicata dall'iteratore. |
| cancella(const g) | Rimuove il valore 'g' dall'insieme. |
| chiaro() | Rimuove tutti gli elementi dal set. |
| chiave_comp() / valore_comp() | Restituisce l'oggetto che determina come sono ordinati gli elementi nell'insieme ('<' per impostazione predefinita). |
| trova(const g) | Restituisce un iteratore all'elemento 'g' nel set, se trovato, altrimenti restituisce l'iteratore alla fine. |
| contare(cost g) | Restituisce 1 o 0 a seconda che l'elemento 'g' sia presente o meno nell'insieme. |
| limite_inferiore(const g) | Restituisce un iteratore al primo elemento che è equivalente a 'g' o sicuramente non andrà prima dell'elemento 'g' nel set. |
| limite_superiore(const g) | Restituisce un iteratore al primo elemento che andrà dopo l'elemento 'g' nel set. |
| intervallo_uguale() | La funzione restituisce un iteratore di coppie. (chiave_comp). La coppia si riferisce all'intervallo che comprende tutti gli elementi del contenitore che hanno una chiave equivalente a k. |
| posizionare() | Questa funzione serve per inserire un nuovo elemento nel contenitore dell'insieme, solo se l'elemento da inserire è unico e non esiste già nell'insieme. |
| emplace_hint() | Restituisce un iteratore che punta alla posizione in cui viene eseguito l'inserimento. Se l'elemento passato nel parametro esiste già, restituisce un iteratore che punta alla posizione in cui si trova l'elemento esistente. |
| scambio() | Questa funzione viene utilizzata per scambiare il contenuto di due set, ma i set devono essere dello stesso tipo, anche se le dimensioni possono differire. |
| operatore= | Il '=' è un operatore in C++ STL che copia (o sposta) un set in un altro set e set::operator= è la funzione dell'operatore corrispondente. |
| get_allocator() | Restituisce la copia dell'oggetto allocatore associato al set. |
Differenza tra insieme e insieme non ordinato
| Impostato | Insieme non ordinato |
|---|---|
| Imposta gli elementi del negozio in ordine ordinato | L'insieme non ordinato memorizza gli elementi in un ordine non ordinato |
| Imposta negozi/acquisisci solo elementi unici | L'insieme non ordinato memorizza/acquisisce solo valori univoci |
| Set utilizza alberi di ricerca binari per l'implementazione | Il set non ordinato utilizza le tabelle hash per l'implementazione |
| È possibile cancellare più di un elemento fornendo l'iteratore iniziale e finale | Possiamo cancellare quell'elemento per il quale è data la posizione dell'iteratore |
| imposta Nome_insieme; | set_non ordinatoNome_set_non ordinato; |
Per ulteriori informazioni è possibile fare riferimento all’articolo – Insiemi vs insieme non ordinato .