In questa lezione parliamo di Contenitori anche detti Collezioni, classi specializzate per la gestione di raccolte di oggetti con modalità di accesso differenti.

Le Collezioni possono essere di 4 tipi:

vediamo in dettaglio le loro caratteristiche.

LE LISTE
Le Liste sono contenitori di oggetti simili ai vettori,  di dimensioni dinamiche e modalità di accesso indicizzata, questo significa che in una lista potete aggiungere tutti i valori oppure gli oggetti che volete ed ognuno di essi può essere identificato da un valore numerico chiamato indice, come per i vettori, il primo indice corrisponde al valore 0.

L'immagine seguente mostra la struttura di una lista, che contiene i riferimenti di tre oggetti di tipo Persona:

Attenzione persona1, persona2 e persona3 corrispondono agli indirizzi di memoria (riferimenti) delle posizioni dove sono stati istanziati i tre oggeti di tipo Persona.

In C++ per  inserire valori oppure oggetti all'inizio di una lista, si usa il metodo push_front(), per inserirli alla fine, si usa il metodo push_back(), mentre per puntare al primo oppure all'ultimo elemento si usano i metodi pop_front() e pop_back().  Per leggere ed eliminare il primo oppure l'ultimo elemento di una lista si usano i metodi front() e back().

L'immagine seguente mostra come si gestisce una lista in C++.

Per conoscere quanti elementi sono presenti in una lista, potete usare il metodo size(), altri metodi importatnti sono:

empty() restituisce true se la lista è vuota false se contiene elementi;
clear() elimina tutti gli elementi di una lista;
erase(posizione) oppure erese(da,a) elimina dalla lista uno specifico elemento oppure un intervallo di elementi;
insert(posizione,valore) inserisce il valore prima della posizione indicata.

Per passare alla partica, vediamo un esempio, scritto in linguaggio C++,

Esempio 1

// Calcola il totale dei valori interi inseriti nella lista
#include <iostream>
#include <list>
using namespace std;

int main ()
{
// Dichiarazione lista che contiene valori interi. Valori è il riferimento che contiene l'indirizzo di dove è stata allocata la lista
list<int> valori;
int somma=0;
// Inserimento alla fine della lista di valori interi
valori.push_back (10);
valori.push_back (20);
valori.push_back (30);
// Mentre la lista è piena, viene letto l'ultimo valore ed aggiunto alla variabile somma. Successivamente il valore letto viene rimosso. Alla fine del ciclo la lista sarà vuota
while (!valori.empty())
  {

    // Legge l'ultimo valore della lista e allo stesso tempo lo elimina. Il metodo back() legge ed elimina.
    // Per leggere senza eliminare il valore dovete usare un iteratore
    somma+=valori.back();
   // Punta all'ultimo elemento disponibile nella lista
    valori.pop_back();
  }
// Visualizza il Totale contenuto nella variabile somma e va a capo (endl='\n')
  cout << "Totale:" << somma << endl;
  return 0;
}

Per ordinare una lista in C++, si usa il metodo sort(),  al metodo potete anche passare un metodo in cui vengono indicate le modalità di comparazione da usare per l'ordinamento.

Gli esempi seguenti mostrano come ordinare una lista di numeri interi, sia in modo crescente, sia in modo decrescente.

Esempio 2

// Lista ordinata in modo crescente
#include <iostream>
#include <list>

using namespace std;

int main(){
    list<int> valori;
    valori.push_back(50);
    valori.push_back(40);
    valori.push_back(30);
    valori.push_back(10);
    valori.push_back(20);
    valori.push_back(35);
    valori.push_back(60);
    valori.push_back(45);
    valori.push_back(23);
    valori.push_back(15);
    // Ordina la lista in modo crescente
    valori.sort();
    while (!valori.empty())
    {
         // Legge il primo valore della lista e allo stesso tempo lo elimina. Il metodo front() legge ed elimina.
         // Per leggere senza eliminare il valore dovete usare un iteratore
        cout << valori.front() << endl;
       // Punta al primo elemento disponibile nella lista
        valori.pop_front();
    }
      return 0;
}

Esempio 3

// Lista ordinata in modo decrescente
#include <iostream>
#include <list>

using namespace std;

int main(){
    list<int> valori;
    valori.push_back(50);
    valori.push_back(40);
    valori.push_back(30);
    valori.push_back(10);
    valori.push_back(20);
    valori.push_back(35);
    valori.push_back(60);
    valori.push_back(45);
    valori.push_back(23);
    valori.push_back(15);
    // Ordina la lista in modo decrescente, il metodo greater<int>() permette d'indicare il metdo di comparazione decrescente
    valori.sort(greater<int>());
    while (!valori.empty())
    {
         // Legge il primo valore della lista e allo stesso tempo lo elimina. Il metodo front() legge ed elimina.
         // Per leggere senza eliminare il valore dovete usare un iteratore
        cout << valori.front() << endl;
        valori.pop_front();
    }
      return 0;

}

Come avete potuto notare dagli esempi precedenti, in C++, ogni volta che si usano i metodi back() e front(), per leggere un valore dalla lista, il valore viene eliminato, questo significa che se leggete tutti i valori, alla fine la lista sarà vuota.  Per evitare di svuotare le liste dopo la lettura dei valori, usare un iteratore, un riferimento dinamico che può essere incrementato oppure decrementato, che permette di puntare ad un elemento qualsiasi della lista. Dopo aver creato l'iteratore, per ottenere il riferimento del primo elemento di una lista si usa il metodo begin(), mentre il metodo end() restituisce l'indirizzo che corrisponde alla fine della lista.

L'immagine seguente mostra il funzionamento degli iteratori in C++:

I due esempi seguenti mostrano come si usano gli iteratori per visualizzare i valori di una lista con C++:

Esempio 4

#include <iostream>
#include <list>

using namespace std;

int main ()
{
  // Vettore con i valori da inserire nella lista
  int vlista[]= {10,30,20,30,5};
  // Creo una lista passando al costruttore i valori del vettore vlista
  // L'argomento vlista è l'indirizzo del primo valore, vlista+4 è l'indirizzo dell'ultimo valore - lista (da,a)
  list<int> lista (vlista,vlista+4);
  list<int>::iterator iterLista;
  // Assegno all'iteratore l'indirizzo del primo valore della lista
  iterLista=lista.begin();
  cout << "Elenco valori nella lista:" << endl;
  // Il ciclo serve per incrementare per 5 volte l'indirizzo memorizzato nell'iteratore e visualizzare il contenuto della lista
  for(int x=0;x<lista.size();x++){
    // *iterLista visualizza il valore corrispondente all'indirizzo memorizzato nell'iteratore
    // successivamente ++ incrementa l'indirizzo corrente di una posizione per puntare la valore seguente
    cout << *iterLista++ << endl;
  }
  // Rimuove tutti i valori 30 dalla lista
  lista.remove(30);
  cout << "Elenco valori nella lista dopo la cancellazione:" << endl;
  // Visualizza tutti i valori della lista usando l'iteratore
  for (iterLista=lista.begin(); iterLista!=lista.end(); ++iterLista) {
    cout << *iterLista << endl;
    }
  return 0;
}

Esempio 5

// Lista di nomi ordinata in modo crescente
#include <iostream>
#include <list>
#include <string>
#include <cctype>

using namespace std;

// compara i nomi della lista trascurando la differenza tra maiuscolo e minuscolo (not case sensitive)
bool compara_nocase (const string& prima, const string& seconda)
{
  unsigned int i=0;
// Il ciclo continua ad essere eseguito mentre il valore della variabile è minore della lunghezza del primo nome e del secondo nome
  while ( (i<prima.length()) && (i<seconda.length()) )
  {
    // Se il carattere iesimo del primo nome e minore del carattere iesimo del secondo nome viene restituito true altrimenti false
    if (tolower(prima[i])<tolower(seconda[i])) return true;
    else if (tolower(prima[i])>tolower(seconda[i])) return false;
    ++i;
  }
  return ( prima.length() < seconda.length() );
}

int main ()
{
  int i;
  list<string> nomi;
  list<string>::iterator iterNomi;
  nomi.push_back ("Mario");
  nomi.push_back ("Alessandra");
  nomi.push_back ("Carlo");
  nomi.push_back ("mario");
  nomi.push_back ("ALESSANDRA");
  nomi.push_back ("carlo");
  nomi.push_back ("Marianna");
  nomi.push_back ("ROBERTA");
  nomi.push_back ("ROBERTO");
  nomi.sort();
  i=0;
  cout << "Elenco nomi ordinati considerando la differenza tra maiuscolo e minuscolo:"  << endl;
  for (iterNomi=nomi.begin(); iterNomi!=nomi.end(); ++iterNomi)
    cout << ++i << ' ' << *iterNomi << endl;
  cout << endl;
  nomi.sort(compara_nocase);
  i=0;
  cout << "Elenco nomi ordinati senza considerare la differenza tra maiuscolo e minuscolo:" << endl;
  for (iterNomi=nomi.begin(); iterNomi!=nomi.end(); ++iterNomi)
    cout << ++i << ' ' << *iterNomi  << endl;
  cout << endl;

  return 0;
}

COME INSERIRE OGGETTI IN UNA LISTA

L'esempio seguente mostra come si gestisce una lista di oggetti di tipo Persona con C++.

Esempio 6

LE MAPPE
Le Mappe sono contenitori che permettono di associare un valore oppure un oggetto ad una chiave. In pratica è come indirizzare un vettore con una valore qualsiasi invece che con un indice numerico.
Anche le Mappe sono contenitori di dimensioni dinamiche e modalità di accesso indicizzata.

L'immagine seguente mostra la struttura di una mappa che contiene i riferimenti di oggetti di tipo Persona:

In C++ per aggiungere un valore ad una  mappa potete usare i comandi seguenti:

1) mappa["dieci"]=10;

oppure

2) mappa.insert(pair<string,int>("dieci", 10));

In entrambi i casi la chiave scelta, "dieci", è di tipo stringa, mentre il valore associato, 10, è di tipo intero.

Attenzione le chiavi associate ai valori oppure agli oggetti di una mappa possono essere di qualunque tipo, nell'esempio sono chiavi di tipo stringa.

Il metodo insert(...) permette d'inserire in una mappa la struttura pair che corrisponde ad una tupla con due campi first (chiave) e second (valore):

mappa->first corrisponde alla chiave di tipo stringa "dieci";

mappa->second corrisponde al valore di tipo intero 10;

Vediamo tre esempi sviluppati con C++:

Esempio 7

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main ()
{
map<string,int> mappa;
// Inserimento valori interi nella mappa
mappa["primo"] = 1;
mappa["secondo"] = 2;
mappa["terzo"] = 3;
mappa["quarto"] = 4;
mappa["quinto"] = 5;
// Visualizzazione valori attraverso l'uso delle chiavi associate ai valori
cout << "1) Accesso diretto attraverso la chiave:" << endl;
cout << mappa["primo"] << endl;
cout << mappa["secondo"] << endl;
cout << mappa["terzo"] << endl;
cout << mappa["quarto"] << endl;
cout << mappa["quinto"] << endl;
// Dichiarazione iteratore
map<string,int>::iterator iteraMappa;
cout << "2) Accesso attraverso un iteratore:" << endl;
// Visualizzazione valori attraverso l'uso dell'iteratore
for (iteraMappa=mappa.begin();iteraMappa!=mappa.end();++iteraMappa) {
    cout << iteraMappa->first << ": " << iteraMappa->second << endl;
  }

  return 0;
}

Come potete vedere l'iteratore ordina le chiavi in modo crescete.

Esempio 8

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main ()
{
map<string,int> mappa;
map<string,int>::iterator iteraMappa;
// Inserimento valori attraverso l'uso di una tupla di tipo pair
mappa.insert(pair<string,int>("primo", 0));
mappa.insert(pair<string,int>("secondo", 0));
mappa.insert(pair<string,int>("terzo", 0 ) );
mappa.insert(pair<string,int>("quarto",0));
mappa.insert(pair<string,int>("quinto",0));
// Il metodo at(chiave) permette di modificare il valore associato alla chiave
mappa.at("primo") = 1;
mappa.at("secondo") = 2;
mappa.at("terzo") = 3;
mappa.at("quarto") = 4;
mappa.at("quinto") = 5;
// Visualizzazione valori attraverso l'uso dell'iteratore
cout << "Accesso attraverso un iteratore:" << endl;
for (iteraMappa=mappa.begin();iteraMappa!=mappa.end();++iteraMappa) {
    cout << iteraMappa->first << ": " << iteraMappa->second << endl;
  }

  return 0;
}

Esempio 9

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main ()
{
map<string,int> mappa;
// Inserimento valori interi nella mappa
mappa["primo"] = 1;
mappa["secondo"] = 2;
mappa["terzo"] = 3;
mappa["quarto"] = 4;
mappa["quinto"] = 5;
// Dichiarazione iteratore
map<string,int>::iterator iteraMappa;
// Visualizzazione valori attraverso l'uso dell'iteratore
cout << "2) Accesso attraverso un iteratore:" << endl;
for (iteraMappa=mappa.begin();iteraMappa!=mappa.end();++iteraMappa) {
    cout << iteraMappa->first << ": " << iteraMappa->second << endl;
  }
// Il metodo find cerca nella mappa la chiave fornita come argomento ed assegna all'iteratore l'indirizzo corrispondente alla posizione della chiave cercata
iteraMappa=mappa.find("secondo");
// Il metodo erase cancella l'elemento all'indirizzo memorizzato nell'iteratore
mappa.erase(iteraMappa);
iteraMappa=mappa.find("quarto");
mappa.erase(iteraMappa);
cout << "2) Elenco valori dopo cancellazione:" << endl;
for (iteraMappa=mappa.begin();iteraMappa!=mappa.end();++iteraMappa) {
    cout << iteraMappa->first << ": " << iteraMappa->second << endl;
  }

  return 0;
}

COME INSERIRE OGGETTI IN UNA MAPPA

In una  mappa si possono anche inserire oggetti, l'esempio seguente mostra come si gestisce una mappa di oggetti di tipo Persona con C++:

Esempio 10

GLI INSIEMI
Gli Insiemi sono contenitori di valori oppure di oggetti distinti (detti anche componenti o membri) dello stesso tipo. A differenza delle liste e delle mappe gli elementi di un insieme non possono essere duplicati, cioè un insieme non può contenere valori uguali oppure oggetti con lo stesso contenuto.

Il numero di elementi di un insieme è detto cardinalità.

I due esempi seguenti mostrano come si gestisce un insieme di numeri interi , con C++:

Esempio 11

int main(){
    // Dichiarazione di un insieme di numeri interi
    set<int> valori;
    // Dichiarazione di un iteratore
    set<int>::iterator iterValori;
   // Inserimento valori interi nell'insieme
    valori.insert(50);
    valori.insert(40);
    valori.insert(30);
    valori.insert(10);
    valori.insert(20);
    valori.insert(30);
    valori.insert(50);
    valori.insert(40);
    valori.insert(20);
    valori.insert(10);
   // Visualizzazione cardinalità e contenuto dell'insieme attraverso l'uso di un iteratore
    cout << "Cardinalita':" << valori.size() << endl << endl;
    for (iterValori=valori.begin(); iterValori!=valori.end(); ++iterValori){
         cout << *iterValori << endl;
    }
    return 0;
}

Esempio 12

#include <iostream>
#include <set>

using namespace std;

int main(){
    set<int> valori;
    // Dichiarazione di un iteratore
    set<int>::iterator iterValori;
   // Inserimento valori interi nell'insieme
    valori.insert(50);
    valori.insert(40);
    valori.insert(30);
    valori.insert(10);
    valori.insert(20);
    valori.insert(30);
    valori.insert(50);
    valori.insert(40);
    valori.insert(20);
    valori.insert(10);
   // Visualizza la cardinalità ed il contenuto dell'insieme attraverso l'uso di un iteratore
    cout << "Cardinalita':" << valori.size() << endl;
    for (iterValori=valori.begin(); iterValori!=valori.end(); ++iterValori){
         cout << *iterValori << endl;
    }
    // Il mtodo find cerca il valore fornito come argomento ed assegna all'iteratore l'indirizzo della posizione nell'insieme
    iterValori=valori.find(20);
   // Il metodo erase utilizza la posizione memorizzata nell'iteratore per eliminare l'elemento corrispondente
    valori.erase(iterValori);
    iterValori=valori.find(40);
    valori.erase(iterValori);
   // Visualizzaza la cardinalità ed il contenuto dell'insieme attraverso l'uso di un iteratore dopo l'eliminazione dei due elementi
    cout << "Cardinalita' dopo la cancellazione dei valori:" << valori.size() << endl;
    for (iterValori=valori.begin(); iterValori!=valori.end(); ++iterValori){
         cout << *iterValori << endl;
    }
    return 0;
}

COME INSERIRE OGGETTI IN UN INSIEME

Se in un insieme  vengono inseriti oggetti, dovete sovrascrivere l'operatore <, come mostra l'esempio seguente:

bool operator<(const Persona& x) const {
    string strPersona1, strPersona2;
    bool esito=false;
    stringstream seta1;
    stringstream seta2;
    seta1 << eta;
    seta2 << x.eta;
    strPersona1=cognome+nome+seta1.str();
    strPersona2=x.cognome+x.nome+seta2.str();
    return strPersona1<strPersona2;
 }

Il programma seguente mostra come si gestisce un insieme di oggetti di tipo Persona, con C++:

Esempio 13

LE CODE
Le Code sono pile sequenziali di valori oppure oggetti di tipo FIFO (First In First Out - Il primo ad entrare è il primo ad uscire) oppure di tipo LIFO (Last In First Out - L'ultimo ad entrare è il primo ad uscire).

L'immagine seguente mostra il comportamento di una coda di tipo FIFO (Queue) :

Gli elementi di una coda di tipo FIFO (Queue) si comportano come le persone che fanno la fila ad una cassa.

L'immagine seguente mostra il comportamento di una coda di tipo LIFO (Stack):

Gli elementi di una coda di tipo LIFO (Stack) si comportano come una pila di piatti.

In C++, per aggiungere un valore oppure un oggetto ad una coda si usa il metodo push(), per puntare al successivo elemento si usa il metodo pop(), per estrarlo da una coda, si usa il metodo front(), per estrarlo da uno stack, si usa il metodo top(),come mostrano gli esempi seguenti:

Esempio 14

#include <iostream>
#include <queue>

using namespace std;

int main()
{
  // Dichiarazione coda di valori interi di tipo FIFO
  queue <int> coda;
 // Inserimento valori nella coda
  coda.push(10);
  coda.push(20);
  coda.push(30);
  coda.push(5);
  coda.push(15);
  coda.push(25);
  coda.push(50);
  coda.push(60);
  coda.push(40);
  coda.push(30);
  cout << "Dimensione coda:" << coda.size() <<endl;
 // Legge i valori dalla coda mentre non è vuota
  while (!coda.empty())
  {
   // Legge ed elimina il valore corrente dalla coda
    cout << coda.front() << endl;
   // Punta al valore successivo da leggere
    coda.pop();
  }
  cout << "Dimensione coda:" << coda.size() <<endl;
  return 0;
}

Esempio 15

#include <iostream>
#include <stack>

using namespace std;

int main()
{
  // Dichiarazione coda di valori interi di tipo LIFO
  stack <int> coda;
 // Inserimento valori nella coda
  coda.push(10);
  coda.push(20);
  coda.push(30);
  coda.push(5);
  coda.push(15);
  coda.push(25);
  coda.push(50);
  coda.push(60);
  coda.push(40);
  coda.push(30);
  cout << "Dimensione coda:" << coda.size() <<endl;
  while (!coda.empty())
  {
   // Legge ed elimina il valore corrente dalla coda
    cout << coda.top() << endl;
   // Punta al valore successivo da leggere
    coda.pop();
  }
  cout << "Dimensione coda:" << coda.size() <<endl;
  return 0;
}

Esempio 16

Esempio 17

Nella prossima lezione faremo un confronto tra C++ e Java.

<< Lezione precedente

  Clicca qui per scaricare i laboratori di questa lezione  (Per eseguire i laboratori installate Code Block sul vostro computer)

Laboratori di Logica di Programmazione in C