Differences

This shows you the differences between two versions of the page.

Link to this comparison view

appunti3s:stl [2018/04/25 07:55] (current)
Line 1: Line 1:
 +====== Standard Template Library ======
 +===== Premessa =====
 +
 +La libreria standard del linguggio C++ (ISO) contiene numerosi header file, tra cui: <​array>,​ <​bitset>,​ <​complex>, ​ <​exception>,​ <​fstream>,​ <​hardware>,​ <​hash_map>,​ <​hash_set>,​ <​iomanip>, ​ <​ios>,​ <​iosfwd>,​ <​iostream>,​ <​istream>,​ <​limits>,​ <​locale>,​ <​new>,​ <​ostream>,​ <​random>​ , <​regex>,​ <​slist>,​ <​sstream>,​ <​stdexcept>,​ <​streambuf>,​ <​string>,​ <​strstream>,​ <​tuple>,​ <​typeinfo>,​ <​type_traits>,​ <​unordered_map>,​ <​unordered_set>,​ <​valarray>​
 +
 +I seguenti appartengono alla **Standard Template Library**, cioè sono dedicati alla dichiarazione di [[appunti3s:​template]] (modelli generici utilizzabili per qualsiasi tipo di dato definito dall'​utente):​
 +<​algorithm>,​ <​deque>,​ <​functional>,​ <​iterator>,​ <​list>,​ <​map>,​ <​memory>,​ <​numeric>,​ <​queue>,​ <​set>,​ <​stack>,​ <​utility>, ​ <​vector> ​
 +
 +I seguenti permettono di usare funzioni del C++ in C: <​fstream.h>,​ <​iomanip.h>,​ <​iostream.h>,​ <​new.h>​
 +
 +I seugenti permettono di usare funzioni del C in C++: <​cassert>,​ <​ccomplex>,​ <​cctype>,​ <​cerrno>,​ <​cfenv>,​ <​cfloat>,​ <​cinttype>,​ <​ciso646>,​ <​climits>,​ <​clocale>,​ <​cmath>,​ , <​csetjmp>,​ <​csignal>,​ <​cstdarg>,​ <​ccstdbool>,​ <​cstddef>,​ <​cstdint>,​ <​cstdio>,​ <​cstdlib>,​ <​cstring>,​ <​ctgmath>,​ <​ctime>,​ <​cwchar>,​ <​cwctype>​
 +
 +>> A parte il caso degli operatori //new// e //delete//, ogni altro operatore si trova nel namespace //std//
 +
 +===== STL =====
 +
 +La Standard Template Library contiene:
 +  * container: generici contenitori per dati (60 tipi di container)
 +  * algorithm: operazioni sui dati (10 tipi di algoritmi)
 +  * sequence: sequenze che iniziano con un iteratore e terminano con un iteratore (che è oltre la fine)
 +  * iterator: ogni tipo di container ha il proprio tipo di iterator
 +
 +iteratore= serve per accedere indirettamente (per puntare) ad un elemento di una sequenza
 +
 +==== Container ====
 +
 +Tipi di dato generici (template) e astratti, non è necessario sapere come sono fatti realmente
 +
 +Esempi: vector, lista, coda, stringa, mappa, albero...
 +  * Sequence containers: vector, list, deque
 +  * Associative containers: map, set, multimap, multiset
 +  * "​almost containers":​ array, string, stack, queue, priority_queue
 +==== Algorithm ====
 +Le operazioni accedono ai dati tramite gli iterator. ​
 +Ad esempio, esistono funzioni utili a trovare elementi per posizione, per contenuto, per proprietà
 +  * funzioni di inserimento,​ modifica, eliminazione dati
 +  * funzioni di ordinamento,​ di ricerca ​
 +  * funzioni comuni, pronte all'​uso e riutilizzabili (usandole è più facile leggere il codice)
 +  * funzioni standard che si possono applicare su diversi tipi di dato (parametrizzate)
 +
 +==== Sequence ====
 +
 +Rappresentare graficamente una sequenza e una seq. vuota. con gli iteratori come frecce.
 +
 +==== Iterator ====
 +
 +Su un oggetto iterator è sempre possibile eseguire almeno queste tre operazioni:
 +  * ++ incremento
 +  * * deferenziazione (leggere il contenuto)
 +  * == confronto sul contenuto
 +
 +===== Esempio =====
 +Operazioni molto comuni nell'​uso di container sono:
 +  - verificare la fine di una struttura dati
 +  - leggere un elemento di una struttura dati
 +  - passare all'​elemento successivo di una struttura dati
 +
 +Anticipando qualche concetto sulla struttura //​std:​vector//,​ si può tradurre le tre precedenti operazioni nel seguente frammento di codice:
 +<​code>#​include <​vector>​
 +std::​vector<​float>​ v1;
 +std::​vector<​float>::​iterator p1 = v1.begin();</​code>​
 +
 +  - <​code>​p1==v1.end();</​code>​
 +  - <​code>​std::​cout << *p1;        //​deferenziare l'​iterator come un puntatore</​code>​
 +  - <​code>​++p1;</​code>​
 +
 +
 +===== vector =====
 +Per usarli si deve includere
 +<​code>#​include <​vector></​code>​
 +Si può presentare la struttura di un //vector// facendo alcuni esempi:
 +
 +  * esempio che crea la struttura e la inizializza correttamente ​
 +    * <​code>​std::​vector<​double>​ voti;</​code>​ {{ :​appunti3s:​vector0.png |}}
 +  * esempio che __copia__ l'​elemento passato (aggiornando la dimensione della struttura)
 +    * <​code>​voti.push_back(6.5);</​code>​ {{ :​appunti3s:​vector1.png |}}
 +  * esempio che copia in fondo l'​elemento passato (aggiornando la dimensione della struttura)
 +    * <​code>​voti.push_back(7.5);</​code>​ {{ :​appunti3s:​vector2.png |}}
 +
 +  * La funzione push_back() permette di inserire una __copia__ di un elemento in fondo al vector senza preoccuparsi di quale sia la sua posizione.
 +  * Per rimuovere un elemento a partire dal fondo si usa la funzione pop_back().
 +<file c vector1.cpp>​
 +// inserire alcuni voti in un vector:
 +#include <​vector>​
 +int main()
 +{
 +    std::​vector<​double>​ voti;      // per inserire dei voti in formato double
 +    std::cout << "​inserire voti terminando con uno zero"
 +    double temp=-1.0; ​             // una variabile per contenere un solo voto
 +    while (temp)
 +    {
 +       ​std::​cin >> temp;           // cin legge un valore e lo mette in temp
 +       ​voti.push_back(temp); ​      // memorizzo il valore di temp nel vector
 +    }
 +    // ... aggiungere eventuale elaborazione dei voti ...
 +    }
 +
 +</​file>​
 +  * Non è necessario specificarne la dimensione nella dichiarazione
 +  * Sono allocati in modo dinamico, ma non se ne deve preoccupare direttamente il programmatore
 +  * I dati sono allocati in modo continuo
 +  * L'​accesso ai dati è di tipo diretto (viene restituito un reference agli elementi del vector)
 +
 +Un //vector// può contenere qualsiasi tipo di oggetti, ad esempio //string//:
 +
 +<file c vector2.cpp>​
 +// inserire alcuni voti in un vector:
 +#include <​vector>​
 +#include <​iostream>​
 +int main()
 +{
 +    std::​vector<​std::​string>​ parole; ​   // per inserire delle parole in formato string
 +    std::cout << "​inserire parole terminando con invio/​n";​
 +    std::string temp=" "; ​              // una variabile per contenere una parola
 +    while (temp!=""​)
 +    {
 +       ​std::​cin >> temp;                // cin legge una parola e la mette in temp
 +       ​parole.push_back(temp); ​         // memorizzo la parola in temp nel vector
 +    }
 +    // ... aggiungere eventuale elaborazione ...
 +}
 +</​file>​
 +====Accesso agli elementi====
 +Gli elementi del vector sono indicizzati con un numero che parte da ZERO.
 +In precedenza si è visto come si può inserire una copia dell'​elemento in fondo usando la funzione push_back(). ​
 +Per la lettura, invece, si può accedere agli elementi di un vector in due modalità:
 +  * usando il tipo //​iterator//​ (come un puntatore)
 +  * usando il tipo //​size_type//​ (come un indice numerico della posizione)
 +===iterator===
 +Si è già parlato del concetto di iterator come puntatore. Nel seguente esempio vengono prima inseriti dei voti e poi visualizzati. Invece di iterator si usa il tipo const_iterator che consente l'​accesso agli elementi in sola lettura.
 +
 +<file c vector3.cpp>​
 +#include <​vector>​
 +#include <​iostream>​
 +
 +int main()
 +{
 +  float voto;
 +  std::​vector<​float>​ voti;
 +  std::cout << "​inserire 10 voti" << std::endl;
 +  for (int i=0; i<10; i++)
 +  {  ​
 +     ​std::​cin >> voto;
 +     ​voti.push_back(voto);​
 +  }
 +  for (std::​vector<​float>::​const_iterator p=voti.begin();​ p!=voti.end();​ p++)
 +     ​std::​cout << *p << std::endl;
 +
 +  return 0;
 +}
 +</​file>​
 +===size_type===
 +Esistono due usi dei size_type per accedere agli elementi di un vector: ​
 +    * accesso controllato
 +    * accesso non controllato
 +L'​accesso controllato differisce da quello "non controllato"​ nel fatto che viene effettuato automaticamente un controllo del superamento della lunghezza reale del vector.
 +L'​accesso controllato si effettua usando la funzione membro at(), mentre l'​accesso non controllato si effettua usando il classico operatore di indicizzazione con le parentesi quadrate: %%[ ]%%.
 +<​code>​
 +std::​vector<​float>::​size_type i = 0;    // funziona anche int i=0;
 +std::cout << v1.at(i); ​                 // accesso controllato,​ meno efficiente...
 +std::cout << v1[i]; ​                    // accesso non controllato
 +</​code> ​
 +Esempio in cui vengono prima inseriti e poi visualizzati dei voti
 +<file c vector4.cpp>​
 +#include <​vector>​
 +#include <​iostream>​
 +
 +int main()
 +{
 +  float voto;
 +  std::​vector<​float>​ voti;
 +  std::cout << "​inserire 10 voti" << std::endl;
 +  for (int i=0; i<10; i++)
 +  {    ​
 +     ​std::​cin >> voto;
 +     ​voti.push_back(voto);​
 +  }
 +  for (int i=0; i<10; i++)   //​size_type puo' essere sostituito da un intero...
 +     ​std::​cout << voti.at(i) << std::endl;
 +
 +  return 0;
 +}
 +</​file>​
 +
 +Lo stesso esempio si può ripetere sostituendo l'​istruzione
 +<​code>​std::​cout << voti.at(i) << std::​endl;</​code>​
 +con l'​istruzione
 +<​code>​std::​cout << voti[i] << std::​endl;</​code>​
 +===== Altre funzioni =====
 +Altre funzioni (inserimento/​eliminazione dati).
 +Queste ultime alterano quasi sempre la posizione del resto degli elementi del container e quindi alterano anche gli iterator, eccetto che nel caso delle liste...
 +<​code>​
 +v1.erase(p1);​
 +v1.insert(p1,​dato);​
 +</​code>​
 +
 +Un'​altra funzione disponibile per vector è find() che permette di trovare la posizione di un valore dato:
 +<​code>​
 +p1 = find(v.begin(),​v.end(),​valore);​
 +</​code>​
 +=== Cenni agli oggetti funzione (function objects)===
 +header <​functional>​
 +<​code>​
 +p1 = find_if(v1.begin(),​v1.end,​Odd()); ​           //oggetto funzione
 +p1 = find_if(v1.begin(),​v1.end,​Less_than(dato)); ​ //oggetto funzione
 +</​code>​
 +Sono stati utilizzati negli ultimi due esempi e sono molto usate nella LTS
 +  * permettono di emulare la programmazione funzionale in C++
 +  * permettono di scrivere codice semplice ed efficiente ​
 +  * permettono di scrivere codice che sarebbe impossibile scrivere in modo tradizionale
 +
 +
  
  • appunti3s/stl.txt
  • Last modified: 2018/04/25 07:55
  • (external edit)