Contenitori unici e ordinati in C ++

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

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

Un esempio di una 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 da tasti. Ordinare questa mappa per keys produce 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Si noti che ci possono essere valori duplicati, ma non chiavi duplicate. Una mappa ordinata è una mappa ordinata da tasti.

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

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

Questo articolo discute le basi di set e mappe in C ++ e per comprendere meglio questo articolo, il lettore avrebbe dovuto avere una conoscenza di base di C++.

Contenuto dell'articolo:

• Classe e i suoi oggetti
• Creazione di un set o una mappa
• Nozioni di base sull'iteratore
• Accesso agli elementi per set e mappa
• Ordine di elementi in un set o mappa
• Altre funzioni dei membri comunemente usati
• Conclusione

Classe e i suoi oggetti:

In C ++, il set, la mappa e altre strutture simili sono chiamati contenitori. Una classe è un'unità generalizzata con membri dei dati, che sono variabili, e funzioni dei membri correlati. Quando i membri dei dati vengono forniti valori, viene formato un oggetto. Tuttavia, un oggetto si forma in un processo chiamato istanziazione. Poiché una classe può portare a valori diversi per le stesse variabili del membro dei dati, oggetti diversi possono quindi essere istanziati dalla stessa classe.

In C ++, un set inutilizzabile è una classe e una mappa inutilizzabile. Quando un oggetto viene istanziato dal set inutilizzabile o dalla mappa inutilizzabile, l'oggetto diventa la struttura dei dati reali. Con le strutture di dati set e mappa, il membro dei dati principali è un elenco. Bene, il set e la mappa formano un gruppo di contenitori chiamato, contenitori associativi ordinati. Esistono anche set non ordinati e mappa non ordinata, ma purtroppo non sono affrontati in questo articolo.

Creazione di un set o una mappa:

L'istanza di un set dalla sua classe set sta creando un set; istanziare una mappa dalla sua classe di mappe è la creazione di una mappa. L'oggetto così creato viene dato un nome di scelta del programmatore.

Per creare un set, il programma dovrebbe iniziare con:

#includere
#includere
Utilizzo dello spazio dei nomi std;

Nota la direttiva "#include", che include la libreria set che ha la classe set da cui verrà istanziata le strutture di dati impostate.

Per creare una mappa, il programma dovrebbe iniziare con:

#includere
#includere
Utilizzo dello spazio dei nomi std;

Nota la direttiva "#include", che include la libreria di mappe che ha la classe mappa da cui verrà istanziata le strutture di dati della mappa.

La sintassi per creare un set vuoto è:

impostato ObjectName

Esempio:

impostato setObj;

Un esempio per creare un set con il contenuto è:

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

La sintassi per creare una mappa vuota è:

carta geografica ObjectName

Esempio:

carta geografica mapobj;

Un esempio per creare una mappa con il 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 dei dati dall'inizio alla fine.

La funzione membro Begin ()

La funzione membro Begin () restituisce un iteratore che indica il primo elemento dell'elenco. Il seguente esempio lo illustra per il set:

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

Nota Il modo in cui inizio () è stato utilizzato con setObj e l'operatore DOT. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indirezione. Come usato con ITER, restituisce il primo elemento del set; Il primo elemento è 2 anziché 6 - vedi spiegazione di seguito.

Il seguente esempio illustra l'uso della funzione iniziale () 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 inizio () è stato utilizzato con MAPOBJ e l'operatore DOT. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. "Prima", come usato qui, si riferisce alla chiave. "Second" si riferisce al valore corrispondente alla chiave. Osserva come sono stati usati con iter per ottenere i componenti dell'elemento iniziale dell'elenco. Il primo elemento è a, 10 invece di c, 30 - vedi spiegazione di seguito.

La funzione membro "inizio () const"

La funzione membro "Begin () const" restituisce un iteratore che indica il primo elemento dell'elenco quando la dichiarazione del set inizia con const (per costante). In questa condizione, il valore nell'elenco, indicato dall'iteratore restituito, non può essere modificato dall'iteratore. Il seguente esempio 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 inizio () è stato utilizzato con setObj e l'operatore DOT. Nessun "const" è stato digitato subito dopo l'inizio (). Tuttavia, "const" ha preceduto la dichiarazione. iter ecco l'oggetto iteratore costante restituito, che è diverso dall'iteratore normale. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; Come usato con iter, restituisce il primo elemento del set. Il primo elemento è 2 anziché 6 - vedi spiegazione di seguito.

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

mappa const 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 inizio () è stato utilizzato con MAPOBJ e l'operatore DOT. Nessun "const" è stato digitato subito dopo l'inizio (). Tuttavia, "const" ha preceduto la dichiarazione. iter ecco l'oggetto iteratore costante restituito, che è diverso dall'iteratore normale. Inoltre, nota il modo in cui è stato dichiarato. "Prima", 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 dell'elenco. Il primo elemento è a, 10 invece di c, 30 - vedi spiegazione di seguito.

La funzione membro end ()

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

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

Nota La via end () è stata utilizzata con setObj e l'operatore DOT. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; Come usato con iter, restituisce l'ultimo elemento+1 del set. Nel computer dell'autore, quest'ultimo elemento+1 è 5, che non è nella lista. Quindi, attento a non usare questo elemento.

Il seguente esempio 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 La via end () è stata utilizzata con MAPOBJ e l'operatore DOT. iter è l'oggetto iteratore restituito. Inoltre, nota il modo in cui è stato dichiarato. * è l'operatore indiretto; Come usato con iter, restituisce l'ultimo elemento+1 della mappa. Nel computer dell'autore, quest'ultimo elemento+1 è , 0, che non è nell'elenco. Quindi, attento 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 del set inizia con const (per costante). In questa condizione, il valore nell'elenco, indicato dall'iteratore restituito, non può essere modificato dall'iteratore. Il seguente esempio 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 La via end () è stata utilizzata con setObj e l'operatore DOT. Nessun "const" è stato digitato subito dopo la fine (). 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 elemento+1 del set.

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

mappa const 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 La via end () è stata utilizzata con MAPOBJ e l'operatore DOT. Nessun "const" è stato digitato subito dopo la fine (). Tuttavia, "const" ha preceduto la dichiarazione. ITER è l'oggetto iteratore costante restituito, che è diverso dall'iteratore normale. Inoltre, osservi attentamente il modo in cui è stato dichiarato.

Accesso agli elementi per set e mappa:

Impostato

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

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

L'output è 2, quindi seguito da 4 - vedi spiegazione di seguito. Per indicare l'elemento successivo dell'elenco, l'iteratore viene incrementato.

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

carta geografica

Una mappa è costituita da coppie chiave/valore. Un valore può essere letto usando la chiave corrispondente e modificato usando la stessa chiave. 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'output è:

20
55

L'operatore DOT non è stato utilizzato qui. Invece, è l'operatore delle staffe quadrate, che prende la chiave come contenuto, che è stato utilizzato.

Ordine di elementi in un set o mappa:

Gli elementi possono essere inseriti in un set, in qualsiasi ordine. Tuttavia, una volta inserito, il set riorganizza i suoi elementi in ordine crescente. L'ordine ascendente è l'ordine predefinito. Se è necessario un ordine decrescente, il set 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 "maggiori" nelle staffe angoli.

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

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" nelle parentesi angolari.

Attraversando un set

Il circuito while o per loop con l'iteratore possono essere utilizzati per attraversare un set. L'esempio seguente utilizza un per loop per attraversare un set che è stato configurato in ordine decrescente:

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

cout << *iter << ";

L'output è:

10 8 6 4 2

Incrementare un iteratore lo punta all'elemento successivo.

Attraversando una mappa

Il circuito while o per loop con l'iteratore possono essere utilizzati per attraversare una mappa. Il seguente esempio utilizza un per loop 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(); iter != MAPOBJ.FINE(); ++ iter)

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

L'output è:

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

Incrementare un iteratore lo punta all'elemento successivo. "Prima", nel codice, si riferisce alla chiave e al "secondo" si riferisce al valore corrispondente. Nota come sono stati ottenuti questi valori per l'output.

Altre funzioni dei membri comunemente usati:

La funzione size ()

Questa funzione restituisce un numero intero, che è il numero di elementi nell'elenco. Imposta esempio:

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

L'output è 5.

Esempio di mappa:

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

L'output è 5.

La funzione insert ()

impostato

Il set non consente il duplicato. Quindi, qualsiasi duplicato inserito viene silenziosamente rifiutato. Con il set, l'argomento alla funzione insert () è il valore da inserire. Il valore è montato in una posizione, in cui l'ordine nel set rimane ascendente o discendente. Esempio:

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

cout << *iter << ";

L'output è:

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 il duplicato per chiave. Quindi, qualsiasi duplicato inserito viene silenziosamente rifiutato. Con la mappa, l'argomento alla funzione insert () è la coppia chiave/valore in parentesi graffe. L'elemento è montato in una posizione per chiave, in cui l'ordine nella mappa rimane ascendente o discendente. Esempio:

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

L'output è:

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

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

La funzione vuota ()

Questa funzione restituisce vero se l'elenco è vuoto e falso se altrimenti. Imposta esempio:

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'output è:

Nuove dimensioni: 4
Valore successivo: 20
Nuove dimensioni: 3
Valore successivo: 30

La funzione cancella () prende un iteratore che indica un elemento come argomento. Dopo aver cancellato l'elemento, la funzione cancella () restituisce un iteratore che indica l'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'output è:

Nuove dimensioni: 4
Coppia di valore successivo: b, 20
Nuove dimensioni: 3
Coppia di valore successivo: c, 30

La funzione cancella () prende un iteratore che indica un elemento come argomento. Dopo aver cancellato l'elemento, la funzione cancella () restituisce un iteratore che indica l'elemento successivo.

La funzione clear ()

La funzione Clear () rimuove tutti gli elementi nell'elenco. Imposta esempio:

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

L'output è 0.

Esempio di mappa:

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

L'output è 0.

Conclusione:

Una struttura di 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 dei dati della mappa in C ++ è una struttura in cui l'elenco è un hash di coppie chiave/valore, memorizzata in ordine crescente di chiavi per impostazione predefinita o in ordine decrescente di chiavi per la scelta del programmatore. Le chiavi sono anche uniche e ci possono essere valori duplicati. Il principale membro dei dati di una delle strutture è l'elenco. Entrambe le strutture hanno funzioni membri, alcune delle quali sono comunemente usate.