STL_containers.tex

\chapter{I contenitori della libreria STL}

Un contenitore, è un template di classe C parametrico sul tipo T degli elementi contenuti (alcuni invece sono parametrici su 2 tipi, come \textit{map} e \textit{multimap}).

Ogni classe contenitore definito nella STL ha tra i suoi membri i seguenti quattro tipi:

\begin{itemize}
	\item \textit{C::value\_type}: Il tipo T degli oggetti memorizzati nel contenitore deve essere assegnabile ma non deve necessariamente definire un costruttore di default.
	\item \textit{C::iterator}: Il tipo iteratore, usato per iterare sugli elementi del contenitore fornisce la ridefinizione di \textit{operator\textasteriskcentered} che ritorna un \textit{value\_type\&}
	\item \textit{C::const\_iterator}: \`{E} l'iteratore usato solo per accedere agli elementi del contenitore. Viene usato anche per accedere ad elementi di contenitori costanti.
	\item \textit{C::size\_type}: Rappresenta la distanza tra due iteratori.
\end{itemize}

\subsection{Costruttori, metodi e operatori}

Un contenitore della Standard Template Library offre i seguenti:

\subsubsection{Gestori della memoria}
\begin{itemize}
	\item \textit{C(const C\&)}: costruttore di copia ridefinito
	\item \textit{C\& operator=(const C\&)} ridefinizione dell'operatore di assegnazione
	\item \textit{$ \tilde{C()} $} distruttore 
\end{itemize}

\subsubsection{Metodi e operatori}
\begin{itemize}
	\item \textit{size\_type size()}: \`{E} un intero maggiore o uguale a zero e rappresenta la dimensione del contenitore, cioè il numero di elementi contenuti.
	\item \textit{bool empty()}: Equivalente a \textit{c.size() == 0} ritorna vero se il contenitore è vuoto, falso altrimenti.
	\item \textit{size\_type max\_size()}: Ritorna la massima dimensione che il contenitore c può avere.
	\item Nelle otto classi contenitore (\textit{vector},\textit{list},\textit{slist},\textit{deque},\textit{set},\textit{map},\textit{multiset},\textit{multimap}) gli elementi sono memorizzati in un'ordine ben definito, quindi vengono offerte anche le ridefinizioni di:
	\subitem \textit{operator==} e \textit{operator !=}: Ritornano rispettivamente \textit{true} se dati due contenitori b e c, \textit{b.size()==c.size()} se gli elementi contenuti in base al tipo sono uguali e \textit{false} altrimenti (l'inverso per l'altro operatore). Per confrontare i tipi sottostanti, viene invocato \textit{operator==} del tipo contenuto.
	\subitem \textit{operator<}, \textit{operator <=}, \textit{operator >}, \textit{operator >=}: \textit{operator<} ritorna \textit{true} se la sequenza del primo contenitore è minore a quella del secondo in base all'ordine lessicografico, \textit{false} altrimenti. Gli altri operatori hanno comportamenti simili. 
\end{itemize}

\section{Iteratori}
L'iteratore \textit{Past the end (PTE)} (non dereferenziabile) punta sempre alla posizione successiva all'ultimo elemento del contenitore.

Un iteratore è detto valido se è dereferenziabile, oppure è l'iteratore \textit{PTE}.

La classe contenitore se offre un iteratore, fornisce sempre due metodi pubblici:

\begin{itemize}
	\item \textit{C::iterator (oppure C::const\_iterator) begin()}: ritorna un iteratore al primo elemento del contenitore c, se c è vuoto ritorna l'iteratore \textit{PTE} 
	\item \textit{C::iterator (oppure C::const\_iterator) end()}: ritorna sempre l'iteratore \textit{PTE}
\end{itemize}

\subsection{Metodi e Operatori}
Oltre a rendere sempre disponibile una ridefinizione di \textit{operator\textasteriskcentered} un iteratore può offrire una ridefinizione degli operatori di incremento (e decremento) prefisso e postfisso:

\begin{itemize}
	\item \textit{C::iterator\& operator++()}: Incremento prefisso (notare il tipo di ritorno per riferimento), l'iteratore può diventare \textit{PTE} dopo l'incremento
	\item \textit{C::iterator\& operator--()}: Decremento prefisso, può ritornare un iteratore che punta all'ultimo elemento, se l'operatore è applicato all'iteratore \textit{PTE}
	\item \textit{C::iterator operator++(int)}: Incremento postfisso (notare il parametro e il tipo di ritorno per valore)
	\item \textit{C::iterator operator--(int)}: Decremento postfisso (notare il parametro e il tipo di ritorno per valore)
\end{itemize}

Per \textit{vector} e \textit{deque} sono disponibili iteratori ad accesso casuale (permettono di spostarsi di un numero arbitrario di elementi). Per questi iteratori vengono resi disponibili anche gli operatori di confronto.

Formule utilizzabili per iteratori ad accesso casuale, sia n una variabile intera e it,it1,it2 iteratori ad accesso casuale con $ 0\leq n \leq c.size() $:

\begin{description}
	\item \textit{it += n} equivalente a n volte ++it se n>0, n volte --it se n<0
	\item \textit{it + n} uguale a \item \textit{it += n} (col segno meno si effettuano i decrementi)
	\item \textit{it[n]} equivalente a \textit{\textasteriskcentered(it+n)} ritorna l'oggetto dereferenziando la posizione dell'iteratore dopo l'incremento (o il decremento)
	\item \textit{it1 < it2} ritorna \textit{true} se it1 punta ad un elemento precedente quello puntato da it2 all'interno del contenitore.
\end{description}

\section{Sequenze}
I contenitori sequenza permettono di memorizzare gli elementi in ordine lineare stretto, stabilito dall'utente del contenitore. Sono contenitori sequenza \textit{list}, \textit{slist}, \textit{vector} e \textit{deque}

\subsection{Funzionalità fornite}

\subsubsection{Costruttori}

\begin{description}
	\item \textit{C(C::size\_type n, C::value\_type t)}: Costruttore a due parametri. Costruisce il contenitore c contenente n copie dell'elemento t.
	\item \textit{C(C::size\_type n)}: Costruttore ad un parametro, costruisce c con n elementi inizializzati al valore di default del template. A patto che il tipo T al quale è istanziato il template renda disponibile il suo costruttore di default.
\end{description}

\subsubsection{Metodi di inserimento}

\begin{description}
	\item \textit{C::iterator insert(C::iterator it, C::value\_type t)}: Inserisce l'elemento t prima dell'elemento puntato da it e torna un iteratore all'elemento inserito
	\item \textit{void insert(C::iterator it, C::size\_type n, C::value\_type t)}: inserisce n copie di t prima dell'elemento puntato da it.
\end{description}

\subsubsection{Metodi di cancellazione}
Vengono forniti due metodi di erase:

\begin{description}
	\item \textit{C::iterator erase(C::iterator it)}: Distrugge l'elemento puntato da it e ritorna un iteratore che punta al successivo.
	\item \textit{C::iterator erase(C::iterator it1,C::iterator it2)}: \`{E} equivalente a rimuovere gli elementi compresi tra [it1,it2) e ritorna un iteratore all'elemento successivo a quello puntato da it2.
	\item \textit{void clear()}: \`{E} equivalente a \textit{c.erase(c.begin(), c.end()}, in pratica rimuove tutti gli elementi del contenitore.
\end{description}

\subsubsection{Metodi particolari}

Per i contenitori \textit{vector}, \textit{list} e \textit{deque} sono disponibili i metodi

\begin{description}
	\item \textit{void push\_back(C::value\_type t)}: Inserisce l'elemento t in coda al contenitore
	\item \textit{void pop\_back()}: rimuove l'elemento in coda al contenitore.
\end{description}

Per i contenitori \textit{list} e \textit{deque} sono disponibili i metodi

\begin{description}
	\item \textit{void push\_front(C::value\_type t)}: Inserisce l'elemento t in testa al contenitore
	\item \textit{void pop\_front()}: rimuove l'elemento in testa al contenitore.
\end{description}

\section{Contenitori Associativi}
I contenitori associativi permoettono un'accesso efficiente agli elementi tramite chiavi ma non è possibile inserire un elemento in una posizione specifica.

\textit{C::key\_type}: \`{E} il tipo della chiave e coincide con \textit{C::value\_type} in \textit{set} e \textit{multiset} dove gli elementi del contenitore sono anche le chiavi d'accesso. In \textit{map} e \textit{multimap} la chiave è una componente dell'elemento e quindi \textit{C::value\_type} non è modificabile. Dato it, un iteratore dereferenziabile, \textit{\textasteriskcentered it = t;} non compila.

\textit{set} e \textit{map} sono detti \textbf{unici}, non possono esistere due elementi con la stessa chiave.
\text{multiset} e \textit{multimap} sono detti \textbf{multipli} perché più elementi con la stessa chiave, sono permessi.

\subsection{Funzionalità fornite}
Ogni contenitore associativo offre le seguenti funzionalità:

\begin{description}
	\item \textit{C::size\_type count(C::key\_type)}: ritorna il numero di elementi con quella chiave.
	\item \textit{C::size\_type erase(C::key\_type)}: elimina gli elementi con quella data chiave e ritorna il numero di elementi eliminati.
	\item \textit{void erase(C::iterator)}: se it è dereferenziabile, distrugge l'elemento puntato da it e lo rimuove dal contenitore.
	\item \textit{void erase(C::iterator,C::iterator)}: distrugge gli elementi nell'intervallo [it1,it2) e li rimuove dal contenitore.
	\item \textit{void clear()}: distrugge e rimuove tutti gli elementi del contenitore.
	\item \textit{C::iterator find(C::key\_type)}: ritorna un iteratore all'elemento con la chiave cercata (se c'è), se non la trova ritorna un iteratore \textit{PTE}, se ci sono più elementi con la stessa chiave ritorna un iteratore ma non si sa a quale elemento.
\end{description}

I contenitori associativi visti qui, offrono sempre una ridefinizione di \textit{operator<}, in quanto sono contenitori ordinati.

\section{Vector}
Vector è un contenitore sequenza e consiste in un array dinamico ridimensionabile all'occorrenza.

Oltre alle funzionalità viste sopra, offre \textit{vector::size\_type capacity() const}: che ritorna il numero di elementi che v può contenere in totale. 
\textit{$ v.size() \leq v.capacity() $ è sempre true}

Per usare \textit{vector} occorre
\begin{enumerate}
	\item Includere la classe \textit{vector} con l'istruzione \textit{\#include<vector>}
	\item Usare la direttiva d'uso \textit{using namespace std} o \textit{using std::vector}
	\item Procedere all'istanziazione del tipo di \textit{vector} in quanto è un template.
\end{enumerate}

\section{Altri contenitori}

\subsection{list e slist}
\textit{list} è una lista doppiamente concatenata ed è un contenitore sequenza. \`{E} vantaggiosa per inserimenti e rimozioni ma non per l'accesso agli elementi.\\
\textit{slist} è una lista singolarmente concatenata.

\begin{description}
	\item \textit{void merge(list<T>\& )}: Su due liste distinte, rimuove gli elementi della lista passata per parametro e gli inserisce ordinatamente nella prima lista. Necessita di aver ridefinito \textit{operator<} sul tipo T.
	\item \textit{void reverse()}: Rovescia l'ordine degli elementi della lista.
	\item \textit{void sort()}: Ordina gli elementi della lista.  Necessita di aver ridefinito \textit{operator<} sul tipo T.
\end{description}

\subsection{deque}
\textit{deque} è un contenitore sequenza simile a \textit{vector} con inserimento e rimozione in testa e in coda in tempo costante, mentre nel mezzo in tempo lineare. \`{E} una \textit{double-ended queue} e non rende disponibile il metodo \textit{capacity()}.
 
\subsection{set e multiset}

\textit{set} e \textit{multiset} sono contenitori associativi. 
\textit{set} richiede la ridefinizione di \textit{operator<} per il tipo al quale verrà istanziato (cioè le chiavi devono essere ordinabili). La chiave coincide con il valore, quindi non sono ammessi valori duplicati.