Contenitori univoci e ordinati in C++

6, 10, 2, 8, 4 è un insieme; 2, 4, 6, 8, 10 è un insieme degli stessi numeri interi, disposti in ordine crescente. In matematica, un insieme ha elementi univoci (elementi distinti), e cioè nessun elemento si verifica più di una volta. Inoltre, un multiinsieme è un insieme, in cui ogni elemento può verificarsi più di una volta. 6, 6, 10, 2, 2, 8, 4, 4, 4 è un multiinsieme. 2, 2, 4, 4, 4, 6, 6, 8, 10 è lo stesso multiinsieme, ma con gli elementi disposti in ordine crescente. Questo articolo non si occupa di multiset. Si occupa della struttura dati C++ chiamata, set.

Una mappa nel software è come un array, ma è un array con due colonne invece di una. La prima colonna ha le chiavi e la seconda colonna ha i valori. Ogni riga è una coppia, creando una coppia chiave/valore. Una chiave è direttamente correlata al suo valore.

Un esempio di mappa è 'c',30, 'b',20, 'd',30, 'e',40, 'a',10. La prima coppia chiave/valore inserita qui è 'c',3, dove 'c' è la chiave e 30 è il valore. Questa mappa non è ordinata per chiavi. Ordinare questa mappa per chiavi produce 'a',10, 'b',20, 'c',30, 'd',30, 'e',40. Nota che possono esserci valori duplicati, ma non chiavi duplicate. Una mappa ordinata è una mappa ordinata per chiavi.

Un multiset sta a un insieme, come un multimap sta a una mappa. Ciò significa che ci sono mappe con chiavi duplicate. Un esempio di multimappa è 'a',10, 'b',20, 'b',20, 'c',30, 'c',30, 'd ',30, 'e',40. E come detto sopra, questo articolo non si occupa di multimappa, piuttosto, si occupa della struttura dati C++ chiamata, mappa.

In C++, una struttura dati è una struttura con proprietà (membri dati) e metodi (funzioni membro). I dati della struttura sono un elenco; un insieme è una lista; una mappa è un elenco di coppie chiave/valore.

Questo articolo discute le basi degli insiemi e delle mappe in C++ e, per comprendere meglio questo articolo, il lettore dovrebbe avere una conoscenza di base del C++.

Contenuto dell'articolo:

Classe e i suoi oggetti
Creare un set o una mappa
Nozioni di base sull'iteratore
Accesso agli elementi per set e mappa
Ordine degli elementi in un insieme o mappa
Altre funzioni membro comunemente utilizzate
Conclusione

Classe e suoi oggetti:

In C++, l'insieme, la mappa e altre strutture simili sono chiamate contenitori. Una classe è un'unità generalizzata con membri dati, che sono variabili, e funzioni membro che sono correlate. Quando ai membri dei dati vengono assegnati valori, viene formato un oggetto. Tuttavia, un oggetto viene formato in un processo chiamato istanziazione. Poiché una classe può portare a valori diversi per le stesse variabili membro dei dati, è possibile creare un'istanza di oggetti diversi dalla stessa classe.

In C++, un insieme inutilizzabile è una classe, così come una mappa inutilizzabile. Quando un oggetto viene istanziato dall'insieme inutilizzabile o dalla mappa inutilizzabile, l'oggetto diventa la struttura dati reale. Con le strutture dati set e map, il membro dati principale è una lista. Ebbene, l'insieme e la mappa formano un gruppo di contenitori chiamati contenitori associativi ordinati. Esistono anche il set non ordinato e la mappa non ordinata, ma sfortunatamente non vengono affrontati in questo articolo.

Creazione di un set o di una mappa:

Istanziare un set dalla sua classe set è creare un set; istanziare una mappa dalla sua classe map sta creando una mappa. All'oggetto così creato viene dato un nome a scelta del programmatore.

Per creare un set, il programma dovrebbe iniziare con:

#includere
#includere
usando lo spazio dei nomi std;

Nota la direttiva “#include ", che include la libreria set che ha la classe set da cui verranno istanziate le strutture dati set.

Per creare una mappa, il programma dovrebbe iniziare con:

#includere
#includere
usando lo spazio dei nomi std;

Nota la direttiva “#include ", che include la libreria di mappe che ha la classe map da cui verranno istanziate le strutture dati della mappa.

La sintassi per creare un insieme vuoto è:

impostato nomeoggetto

Esempio:

impostato setOggetto;

Un esempio per creare un set con contenuto è:

impostato setObj(6, 10, 2, 8, 4);

La sintassi per creare una mappa vuota è:

carta geografica nomeoggetto

Esempio:

carta geografica mapObj;

Un esempio per creare una mappa con contenuto è:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Nozioni di base sull'iteratore:

Un iteratore è un puntatore elaborato, che può essere utilizzato per attraversare l'elenco della struttura dati dall'inizio alla fine.

La funzione membro begin()

La funzione membro begin() restituisce un iteratore che punta al primo elemento della lista. L'esempio seguente illustra questo per il set:

impostato setObj(6, 10, 2, 8, 4);
impostato::iterator iter = setObj.inizio();
cout << *iter << '\n';

Nota il modo in cui begin() è stato utilizzato con setObj e l'operatore punto. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto. Come usato con iter, restituisce il primo elemento dell'insieme; il primo elemento è 2 invece di 6 - vedi spiegazione sotto.

L'esempio seguente illustra l'uso della funzione begin() per la mappa:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carta geografica::iterator iter = mapObj.inizio();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota il modo in cui begin() è stato utilizzato con mapObj e l'operatore punto. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. "primo", come usato qui, si riferisce alla chiave. “secondo” si riferisce al valore corrispondente al tasto. Osserva come sono stati usati con iter per ottenere i componenti dell'elemento iniziale della lista. Il primo elemento è a,10 invece di c,30 - vedi spiegazione sotto.

La funzione membro "begin() const"

La funzione membro "begin() const" restituisce un iteratore che punta al primo elemento dell'elenco quando la dichiarazione dell'insieme inizia con const (per costante). In questa condizione, il valore nell'elenco, a cui fa riferimento l'iteratore restituito, non può essere modificato dall'iteratore. L'esempio seguente ne illustra l'uso per il set:

const set setObj(6, 10, 2, 8, 4);
impostato::const_iterator iter = setObj.inizio();
cout << *iter << '\n';

Nota il modo in cui begin() è stato utilizzato con setObj e l'operatore punto. Non è stato digitato "const" subito dopo begin(). Tuttavia, "const" ha preceduto la dichiarazione. iter qui è l'oggetto iteratore costante restituito, che è diverso dal normale iteratore. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; come usato con iter, restituisce il primo elemento dell'insieme. Il primo elemento è 2 invece di 6 - vedi spiegazione sotto.

L'esempio seguente illustra l'uso della funzione "begin() const" per la mappa:

mappa costante mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carta geografica::const_iterator iter = mapObj.inizio();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota il modo in cui begin() è stato utilizzato con mapObj e l'operatore punto. Non è stato digitato "const" subito dopo begin(). Tuttavia, "const" ha preceduto la dichiarazione. iter qui è l'oggetto iteratore costante restituito, che è diverso dal normale iteratore. Inoltre, nota il modo in cui è stato dichiarato. "primo", come usato qui, si riferisce alla chiave; "secondo", come usato qui, si riferisce al valore corrispondente alla chiave. Osserva come sono stati usati con iter per ottenere i componenti dell'elemento iniziale della lista. Il primo elemento è a,10 invece di c,30 - vedi spiegazione sotto.

La funzione membro end()

La funzione membro end() restituisce un iteratore che punta subito dopo la fine dell'elenco. L'esempio seguente illustra questo per il set:

impostato setObj(6, 10, 2, 8, 4);
impostato::iterator iter = setObj.fine();
cout << *iter << '\n';

Nota il modo in cui end() è stato utilizzato con setObj e l'operatore punto. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; come usato con iter, restituisce l'ultimo + 1 elemento dell'insieme. Nel computer dell'autore, quest'ultimo elemento+1 è 5, che non è nell'elenco. Quindi, attenzione a non usare questo elemento.

L'esempio seguente illustra l'uso della funzione end() per la mappa:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carta geografica::iterator iter = mapObj.fine();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota il modo in cui end() è stato usato con mapObj e l'operatore punto. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; come usato con iter, restituisce l'ultimo + 1 elemento della mappa. Nel computer dell'autore, quest'ultimo elemento+1 è ,0, che non è nell'elenco. Quindi, attenzione a non usare questo elemento.

La funzione membro "end() const"

La funzione membro "end() const" restituisce un iteratore che punta subito dopo la fine dell'elenco quando la dichiarazione dell'insieme inizia con const (per costante). In questa condizione, il valore nell'elenco, a cui fa riferimento l'iteratore restituito, non può essere modificato dall'iteratore. L'esempio seguente ne illustra l'uso per il set:

const set setObj(6, 10, 2, 8, 4);
impostato::const_iterator iter = setObj.fine();
cout << *iter << '\n';

Nota il modo in cui end() è stato utilizzato con setObj e l'operatore punto. Nessun "const" è stato digitato subito dopo end(). Tuttavia, "const" ha preceduto la dichiarazione. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; come usato con iter, restituisce l'ultimo + 1 elemento dell'insieme.

L'esempio seguente illustra l'uso della funzione "end() const" per la mappa:

mappa costante mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carta geografica::const_iterator iter = mapObj.fine();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota il modo in cui end() è stato usato con mapObj e l'operatore punto. Nessun "const" è stato digitato subito dopo end(). Tuttavia, "const" ha preceduto la dichiarazione. iter è l'oggetto iteratore costante restituito, che è diverso dal normale iteratore. Inoltre, osserva attentamente il modo in cui è stato dichiarato.

Accesso agli elementi per set e mappa:

Impostato

Con l'insieme, l'elemento viene letto utilizzando l'operatore indiretto. I primi due elementi di un insieme vengono letti nell'esempio seguente:

impostato setObj(6, 10, 2, 8, 4);
impostato::iterator iter = setObj.inizio();
cout << *iter << '\n';
++iterare;
cout << *iter << '\n';

L'output è 2, quindi seguito da 4 - vedere la spiegazione di seguito. Per puntare all'elemento successivo dell'elenco, l'iteratore viene incrementato.

Nota: un elemento non può essere modificato utilizzando l'operatore indiretto per l'insieme. Ad esempio, "*iter = 9;" non è possibile.

carta geografica

Una mappa è costituita da coppie chiave/valore. Un valore può essere letto utilizzando il tasto corrispondente e modificato utilizzando lo stesso tasto. Il seguente segmento di codice illustra questo:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';

L'uscita è:

20
55

L'operatore punto non è stato utilizzato qui. Invece, è stato utilizzato l'operatore parentesi quadre, che prende come contenuto la chiave.

Ordine degli elementi in un insieme o mappa:

Gli elementi possono essere inseriti in un set, in qualsiasi ordine. Tuttavia, una volta inserito, l'insieme riordina i suoi elementi in ordine crescente. L'ordine crescente è l'ordine predefinito. Se è necessario un ordine decrescente, l'insieme deve essere dichiarato come nell'esempio seguente:

impostato > setObj(6, 10, 2, 8, 4);

Quindi, dopo il tipo, e.g., int, per il modello, c'è una virgola, seguita da "maggiore” tra parentesi angolari.

Gli elementi possono essere inseriti in una mappa in qualsiasi ordine. Tuttavia, una volta inserita, la mappa riordina i suoi elementi in ordine crescente per chiave (solo) mantenendo la relazione tra ogni chiave e il suo valore. L'ordine crescente è l'ordine predefinito; se è necessario un ordine decrescente, la mappa deve essere dichiarata come nell'esempio seguente:

carta geografica > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Quindi, dopo la coppia di tipi, e.g., "char, int", per il modello, c'è una virgola, seguita da "maggiore” tra parentesi angolari.

Attraversare un set

Il ciclo while o for con l'iteratore può essere utilizzato per attraversare un set. L'esempio seguente utilizza un ciclo for per attraversare un insieme che è stato configurato in ordine decrescente:

impostato > setObj(6, 10, 2, 8, 4);
per (set::iterator iter = setObj.inizio(); iterare != setObj.fine(); ++iter)

cout << *iter << ";

L'uscita è:

10 8 6 4 2

L'incremento di un iteratore lo punta all'elemento successivo.

Attraversare una mappa

Il ciclo while o for con l'iteratore può essere utilizzato per attraversare una mappa. L'esempio seguente utilizza un ciclo for per attraversare una mappa che è stata configurata in ordine decrescente:

carta geografica > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
per (mappa::iterator iter = mapObj.inizio(); iterare != mapObj.fine(); ++iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

L'uscita è:

e, 40, d, 30, c, 30, b, 20, a, 10,

L'incremento di un iteratore lo punta all'elemento successivo. “primo”, nel codice, si riferisce alla chiave e “secondo” si riferisce al valore corrispondente. Nota come questi valori sono stati ottenuti per l'output.

Altre funzioni membro comunemente utilizzate:

La funzione size()

Questa funzione restituisce un intero, che è il numero di elementi nella lista. Esempio di set:

impostato > setObj(6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

L'uscita è 5.

Esempio di mappa:

carta geografica > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj.size() << '\n';

L'uscita è 5.

La funzione insert()

impostato

set non consente duplicati. Quindi, qualsiasi duplicato inserito viene silenziosamente rifiutato. Con il set, l'argomento della funzione insert() è il valore da inserire. Il valore viene inserito in una posizione in cui l'ordine nell'insieme rimane crescente o decrescente. Esempio:

impostato setObj(6, 10, 2, 8, 4);
setObj.inserire(6);
setObj.inserire (9);
setObj.inserire(12);
per (set::iterator iter = setObj.inizio(); iterare != setObj.fine(); ++iter)

cout << *iter << ";

L'uscita è:

2 4 6 8 9 10 12

Nota: la funzione membro insert() può essere utilizzata per popolare un set vuoto.

carta geografica

la mappa non consente la duplicazione tramite chiave. Quindi, qualsiasi duplicato inserito viene silenziosamente rifiutato. Con la mappa, l'argomento della funzione insert() è la coppia chiave/valore tra parentesi graffe. L'elemento viene inserito in una posizione tramite chiave, in cui l'ordine nella mappa rimane crescente o decrescente. Esempio:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
mappaObj.insert('e',80);
mappaObj.inserisci('f',50);
mappaObj.inserisci('g',60);
per (mappa::iterator iter = mapObj.inizio(); iterare != mapObj.fine(); ++iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

L'uscita è:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Nota: la funzione membro insert() può essere utilizzata per popolare una mappa vuota.

La funzione empty()

Questa funzione restituisce true se l'elenco è vuoto e false in caso contrario. Esempio di set:

impostato setObj(6, 10, 2, 8, 4);
bool ret = setObj.vuoto();
cout << ret << '\n';

L'output è 0 per false, il che significa che il set qui non è vuoto.

Esempio di mappa:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
bool ret = mapObj.vuoto();
cout << ret << '\n';

L'output è 0 per false, il che significa che la mappa qui non è vuota.

La funzione cancella()()

impostato

Considera il seguente segmento di codice:

impostato setObj(10, 20, 30, 40, 50);
impostato::iterator iter = setObj.inizio();
impostato::iterator itr = setObj.cancella(iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.cancella(itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

L'uscita è:

nuova dimensione: 4
valore successivo: 20
nuova dimensione: 3
valore successivo: 30

La funzione erase() accetta un iteratore che punta a un elemento come argomento. Dopo aver cancellato l'elemento, la funzione erase() restituisce un iteratore che punta all'elemento successivo.

carta geografica

Considera il seguente segmento di codice:

carta geografica mapObj('a',10,'b',20,'c',30,'d',40,'e',50);
carta geografica::iterator iter = mapObj.inizio();
carta geografica::iterator itr = mapObj.cancella(iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.cancella(itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

L'uscita è:

nuova dimensione: 4
coppia di valori successiva: b,20
nuova dimensione: 3
coppia di valori successiva: c,30

La funzione erase() accetta un iteratore che punta a un elemento come argomento. Dopo aver cancellato l'elemento, la funzione erase() restituisce un iteratore che punta all'elemento successivo.

La funzione clear()

La funzione clear() rimuove tutti gli elementi nell'elenco. Esempio di set:

impostato setObj(6, 10, 2, 8, 4);
setObj.chiaro();
cout << setObj.size() << '\n';

L'uscita è 0.

esempio di mappa:

carta geografica mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
mappaObj.chiaro();
cout << mapObj.size() << '\n';

L'uscita è 0.

Conclusione:

Una struttura dati impostata in C++ è una struttura in cui l'elenco degli elementi è memorizzato in ordine crescente per impostazione predefinita o in ordine decrescente per scelta del programmatore. Tutti gli elementi del set sono unici. Una struttura dati mappa in C++ è una struttura in cui l'elenco è un hash di coppie chiave/valore, memorizzato in ordine crescente di chiavi per impostazione predefinita o in ordine decrescente di chiavi per scelta del programmatore. Anche le chiavi sono univoche e possono esserci valori duplicati. Il membro dati principale di una delle strutture è l'elenco. Entrambe le strutture hanno funzioni membro, alcune delle quali sono comunemente usate.