Funzioni set non ordinate C ++
Una tabella hash viene utilizzata per costruire un set non ordinato in cui i valori vengono convertiti in indici della tabella hash per garantire che l'inserimento di un valore sia sempre assegnato in modo casuale. Il fatto è che operano abbastanza bene e normalmente danno un'operazione di ricerca temporale costante. Tutte le funzioni sul set non ordinato di solito richiedono un tempo costante O (1). Sebbene, nella situazione peggiore, possano affrontare il tempo lineare O (N) in base all'algoritmo di hash operativo.
Il set non ordinato può includere chiavi di qualsiasi tipo, siano esse predefinite o definite dall'utente. Ma ogni volta che dichiariamo le chiavi delle strutture di dati definite dall'utente, dobbiamo quindi indicare il metodo di confronto utilizzato per confrontare le chiavi.
Differenza tra set e set non ordinato
Un set è una raccolta ordinata di chiavi distinte. Ma un set non ordinato è una raccolta di chiavi che potrebbero essere disposte in qualsiasi sequenza. L'implementazione di SET come struttura ad albero bilanciata consente di conservare l'ordine dei componenti. Le operazioni di impostazione hanno una complessità del tempo O (log n), ma un set non ordinato ha un O (1). Numerosi metodi sono definiti per il set non ordinato. Ma quelli più popolari sono le dimensioni e il metodo vuoto per l'archiviazione, trovando il valore della chiave e inserendo e rimozione per la configurazione. Solo le chiavi distinte sono supportate dal set non ordinato; Per le chiavi duplicate, può essere impiegato un multiset non ordinato.
Funzioni utilizzate per set non ordinati
Il set non ordinato ha i seguenti metodi:
- Insert (): questa funzione aggiunge un nuovo elemento al contenitore.
- FUNZIONE END (): restituisce un iteratore che punta all'elemento dopo la fine.
- Count () Funzione: conta il numero di volte in cui un elemento specifico appare in un set non ordinato.
- Trova () metodo: trova un componente nel set.
- Clear () Function: svuota un set non ordinato rimuovendo tutti i suoi componenti.
- Funzione cbegin (): restituisce un iteratore costante corrispondente al primo membro nel set non ordinato.
- Cend () Funzione: restituisce un iteratore costante con l'ultimo valore nel set non ordinato.
- bucket_size (): in un set non ordinato, questa funzione restituisce il conteggio totale degli elementi presenti in un determinato secchio.
- Funzione cancella (): elimina dall'inizio alla fine, sia che si tratti di un solo componente o di una raccolta di elementi.
- Funzione size (): fornisce il conteggio degli articoli del set non ordinato.
- Funzione swap (): consente di scambiare i dati di due set non ordinati.
- Funzione emplace (): aggiunge un elemento utilizzando questa funzione a un set non ordinato.
- Max_size (): questa funzione restituisce il maggior numero di elementi che un set non ordinato è in grado di contenere.
- Metodo vuoto (): verifica se un set non ordinato è vuoto.
- Uguale intervallo: restituisce un intervallo con tutti gli articoli che hanno il valore predeterminato come valore.
- Metodo hash (): questo è un metodo unario che accetta solo un parametro e costruisce il suo valore di restituzione su un valore di dimensione singolare_t.
- Riserva () Funzione: viene utilizzato per richiedere la modifica di un set non ordinato.
- Funzione bucket (): restituisce il numero di secchio dell'elemento.
- Funzione bucket_count (): il numero complessivo di set di un set non ordinato viene restituito con questo metodo.
- Load_factor (): restituisce il fattore di capacità che viene spesso impiegato sul set non ordinato.
- Funzione Rehash (): aumenta l'intervallo di secchi nell'imposta non ordinata sul numero definito o superiore.
- Max_load_factor (): restituisce l'indice di capacità di carico finale che il set non ordinato può supportare.
- Funzione EMPlace_hint (): con l'uso di un suggerimento, aggiunge solo un nuovo elemento a un set non ordinato se il valore aggiunto è distinto.
- Funzione key_eq (): fornisce un valore booleano in base al confronto.
L'esecuzione di diverse funzioni non ordinate nel linguaggio C ++ è trattata in questo articolo.
Esempio 1:
Il tempo medio di elaborazione per le funzioni find (), insert () e cancella () è costante. Se la chiave non è presente nel set definito, il metodo find () fornisce un iteratore alla funzione terminale (); Altrimenti, restituisce un iteratore all'attributo chiave. Per acquisire la chiave facendo riferimento ai valori della chiave con l'operatore *, l'iteratore funge da puntatore agli attributi chiave. Quella che segue è un'istanza di una dichiarazione per la ricerca (), insert () e le funzioni di iterazione in un set non ordinato.
#includereUtilizzo dello spazio dei nomi std;
int main ()
UNORDED_SETStrings;
stringhe.inserire ("i");
stringhe.inserire ("amore");
stringhe.inserire ("a");
stringhe.inserire ("gioco");
stringhe.inserire ("badminton");
String key = "like";
Se (stringhe.Trova (chiave) == stringhe.FINE())
cout<< key << " to explore " <
cout<< "explore " << key <
Se (stringhe.Trova (chiave) == stringhe.FINE())
cout<< key << " to explore\n" ;
altro
cout<< "explore " << key <
UNORDERD_SET :: iteratore I;
per (i = stringhe.inizio(); io != stringhe.FINE(); I ++)
cout<< (*i) <
Incorporiamo il file di intestazione all'inizio di questo codice. Quindi, inseriamo lo spazio dei nomi standard come std. Quindi, invochiamo la funzione principale (). All'interno di questa funzione, dichiariamo il set non ordinato. Qui, utilizziamo un set non ordinato per organizzare gli elementi dei set. Passiamo la stringa come parametro della funzione set non ordinata. Successivamente, inseriamo le diverse stringhe nei set. Passiamo le numerose stringhe come argomenti della funzione insert (). Quindi, specifichiamo il valore della chiave utilizzando la parola chiave "chiave". Il metodo find () viene utilizzato nel passaggio successivo. Questa funzione viene applicata per trovare la stringa richiesta del set.
Utilizziamo il metodo end () per terminare le stringhe. Questa funzione restituisce l'iteratore ogni volta che la chiave non esiste nel set. Il comando "cout" viene applicato per stampare l'istruzione. Quindi, inizializziamo di nuovo un valore per l'attributo "chiave". Troviamo il valore di un attributo nella stringa utilizzando la funzione find () e termina la stringa con l'aiuto del metodo end (). Applichiamo la dichiarazione "cout" per mostrare il risultato. Itegniamo sull'intero set e stampiamo il contenuto del set utilizzando l'istruzione "Cout". Usiamo il metodo set non ordinato e dichiariamo l'iteratore come "io". Il ciclo "per" è impiegato.
Innanzitutto, inizializziamo una variabile e quindi utilizziamo la funzione Begin () per avviare la stringa specificata. Inoltre, definiamo la condizione del ciclo. La funzione end () si chiama. Il valore dell'iteratore è incrementato di 1. Alla fine, l'istruzione "Cout" viene utilizzata per mostrare il valore dell'iteratore.
Esempio 2:
In questo caso, eseguiremo un codice in cui dichiariamo un elenco di valori diversi, e quindi troviamo tutti i duplicati da tale elenco mediante l'uso della funzione set non ordinata.
#includereUtilizzo dello spazio dei nomi std;
void printDuplicates (int a [], int b)
UNORDED_SETINTSET;
UNORDERD_SETDUPLICATE;
per (int j = 0; j < b; j++)
if (intset.trova (a [j]) == intset.FINE())
intset.inserire (a [j]);
altro
duplicare.inserire (a [j]);
cout<< "The list of duplicated elements: ";
UNORDERD_SET :: iterator IT;
per (it = duplicato.inizio(); Esso != duplicato.FINE(); It ++)
cout<< *it << " ";
int main ()
int a [] = 11, 30, 42, 21, 94, 35, 11, 77, 62, 89, 94, 35;
int b = sizeof (a) / sizeof (int);
printDuplicates (a, b);
restituzione 0;
Qui, includiamo la biblioteca. Nel passaggio successivo, utilizziamo lo spazio dei nomi standard come STD. Usiamo il metodo Print () per mostrare il replicato nell'array definito mediante l'uso di un set non ordinato. Forniamo un array e una variabile per stupire l'intero come argomenti del metodo PrintDuplicates ().
Ora, dichiariamo i set non ordinati per acquisire e salvare i duplicati. Viene utilizzata la funzione set non ordinata. Passiamo l'intero come parametro. Quindi, utilizziamo un'altra funzione set non ordinata per trovare gli elementi duplicati. Qui, applichiamo il ciclo "per". Dichiariamo una variabile del ciclo "per". Quindi, specifichiamo la condizione. Successivamente, aumentiamo il valore "J". Chiamiamo la funzione Find () per trovare l'elemento definito nell'array. Passiamo l'elemento specifico come argomento di questa funzione. Se l'articolo richiesto è già presente nell'array, inseriamo quell'elemento nel set duplicato.
Mostriamo i valori duplicati dell'array usando l'istruzione "cout". Dichiariamo la variabile "It" dell'iteratore per il set non ordinato. Viene applicato il ciclo "per". Quindi, i metodi Begin () e End () vengono utilizzati nel ciclo "per". Successivamente, chiamiamo la funzione principale (). Inizializziamo una variabile "a". Quindi, definiamo gli elementi per l'array e questo array è memorizzato in una variabile "A". Troviamo le dimensioni dell'array richiesto utilizzando il metodo sizeof (). Passiamo l'array come parametro di questa funzione.
Dividiamo il valore risultante per la dimensione dei numeri interi. Il valore che otteniamo dopo la divisione è memorizzato in una variabile "B". Visualizziamo i valori duplicati dell'array con l'aiuto del metodo printDuplicate (). Alla fine, utilizziamo il comando "return 0".
Esempio 3:
Un elemento di dati può essere aggiunto al contenitore set non ordinato utilizzando la funzione Libreria modello standard C ++ integrata - la funzione insert (). Ogni elemento in un set non ordinato ha un valore particolare e viene aggiunto solo se non è disponibile nel set. Poiché il contenitore impiega diversi metodi di hashing, l'inserimento viene effettuato automaticamente nel punto che soddisfa in modo ottimale il requisito. Di conseguenza, la dimensione del contenitore è considerevolmente migliorata dal numero di articoli recuperati.
Parametri di Insert () Metodo:
- Valore: definisce il valore che dovrebbe essere aggiunto al contenitore.
- Primo, ultimo: iteratori che forniscono una varietà di componenti. Si noti che l'intervallo comprende tutti i componenti tra il primo elemento e l'ultimo elemento, come quello specificato dal primo elemento ma termina l'elemento puntato dall'ultimo elemento.
Il metodo restituisce una coppia, con la coppia :: prima configurato in un iteratore che si riferisce al nuovo elemento aggiornato o al componente corrispondente già presente nel set. Se viene aggiunto un nuovo elemento di dati, la coppia :: secondo componente nella coppia viene regolata su true; Altrimenti, è specificato come falso se è già presente un articolo identico.
Il seguente programma dimostra la funzione di cui sopra:
#includere#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()
UNORDERD_SET set = "lunedì", "martedì";
String str = "mercoledì";
Impostato.inserire (STR);
cout<< "The set of week days is:"
<
cout<< m
<< " ";
cout<
Prima di tutto, integriamo i file di intestazione richiesti. È responsabile delle funzionalità di input e output. Il file di intestazione contiene la dichiarazione delle stringhe. Il terzo contiene tutti i set non ordinati. Utilizziamo lo spazio dei nomi standard come std. Quindi, iniziamo la codifica all'interno del corpo della funzione principale () dopo aver chiamato la funzione principale (). Utilizziamo il set di stringhe non ordinato.
Qui, definiamo gli elementi del mio set. Specifichiamo i due giorni della settimana. Ora indichiamo il valore della stringa che vogliamo essere inseriti nel set richiesto. Inseriamo quella stringa usando il metodo insert (). La dichiarazione "Cout" è impiegata per mostrare il testo "Il set dei giorni feriali è". Usiamo ancora una volta l'istruzione "cout" prima di inserire il comando "return 0". Questa dichiarazione "cout" stampa tutti i nomi dei giorni feriali.
Conclusione
L'uso delle funzioni set non ordinate C ++ è trattato in questo articolo. Abbiamo implementato i numerosi codici sul software Devc ++ in cui abbiamo utilizzato molte funzioni relative ai set non ordinati. I set non ordinati sono strutture di dati che possono contenere componenti diversi in qualsiasi ordine e fornire un accesso efficiente a elementi specifici in base al loro valore. In primo luogo, abbiamo utilizzato le molteplici funzioni di set non ordinate per esaminare come funziona il codice. Usando il metodo find (), abbiamo identificato un determinato elemento all'interno del set. Con l'aiuto della funzione end (), abbiamo terminato il set non ordinato. Nella seconda illustrazione, abbiamo costruito un array contenente vari numeri interi. Valori sia ripetuti che non ripetuti sono inclusi nell'array. Per trovare i valori duplicati nell'array specificato, abbiamo applicato il metodo find (). Il metodo insert () è stato utilizzato nell'ultimo esempio per aggiungere un valore al set non ordinato richiesto.