C++ Contenitori

Da Andreabont's Wiki.

Il C++11 esistono una serie di contenitori definiti nella libreria standard, in questa pagina verranno elencati i principali.

Strutture

Tuple

Arrow right blue.pngVedi anche la pagina: C++ Tuple.

Questo contenitore è pensato per raggruppare diversi tipi di dati in un unico tipo.

#include <tuple>
std::tuple<int, char> mytuple (10,'x');

Contenitori sequenziali

Questi contenitori gestiscono in modo implicito una sequenza di elementi. L'accesso avviene solitamente tramite l'operatore [] (subscript) contenente l'indice di posizione dell'elemento nel contenitore. Lo stesso comportamento è ottenibile attraverso il metodo "at" che in più esegue dei controlli per impedire l'accesso a elementi al di fuori del contenitore.

Array

Gli array della libreria standard sono concettualmente gli array del C (tralaltro usabili anche in C++), ma implementati secondo il paradigma ad oggetti. Sono una sequenza contigua di dimensione fissa di elementi di tipo specificato.

#include <array>
std::array<int, 4> myarray = {1, 2, 3, 4};

Vector

I vector sono una evoluzione degli array, sono sempre una sequenza contigua di elementi con la differenza che la dimensione viene gestita dinamicamente e può crescere in base alla richiesta.

#include <vector>
std::vector<int> myvector = {1, 2, 3, 4}; // 1, 2, 3, 4
std::vector<int> myvector(4,0);           // 0, 0, 0, 0

List

La list è una sequenza non contigua di elementi, implementata come lista doppiamente concatenata. Questo permette di scorrere la lista allo stesso modo di un array o di un vector, ma con la differenza di non supportare l'operatore di subscript []. La sua struttura facilita l'inserimento e la rimozione di elementi in un qualsiasi punto della lista, senza doverla riscrivere completamente.

#include <list>
std::list<int> mylist = {1, 2, 3, 4};

Valarray

Il Valarray è un tipo specifico di array pensato per contenere numeri. Questo contenitore fornisce un supporto esteso a tutte le operazioni matematiche e alla libreria annessa, rendendo possibile eseguire operazioni su vettori numerici con una sola espressione, risparmiando di scrivere i cicli necessari per l'esecuzione. L'accesso avviene attraverso l'operatore di subscript [].

#include <valarray>
#include <cmath>
std::valarray<int> a = {1,2,3};
std::valarray<int> b = {1,2,3};
std::valarray<int> c = a + b;          // Contiene {2,4,6}
std::valarray<int> d = std::pow(a, 2); // Contiene {1,4,9}

Contenitori insiemistici

Questi contenitori tengono solo elementi ordinati non contigui. L'accesso avviene solitamente tramite gli iteratori. Generalmente sono implementate con particolari tipi di albero.

Set

Il set mantiene un insieme ordinato di elementi univoci del tipo specificato. E' implementato con una struttura ad albero rosso-nero.

#include <set>
std::set<int> myset = {1, 2, 3, 4};

Multiset

Il multiset è come il set, con la differenza che permette l'inserimento di più elementi uguali. Le performance sono lievemente minori del set. Tipicamente sono implementati con una struttura a albero binario di ricerca.

#include <set>
std::multiset<int> myset = {1, 1, 2, 2};

Unordered set

La unordered set ottimizza l'accesso ai dati tramite una hash table.

#include <unordered_set>
std::unordered_set<int> myset = {1, 2, 3, 4};

Contenitori associativi

Arrow right blue.pngVedi anche la pagina: C++ Map.

Questi contenitori mantengono i dati nel formato chiave-valore, ogni elemento è associato ad una chiave (che può essere di un qualsiasi tipo, purché implementi gli operatori necessari), e l'accesso avviene proprio specificando questa chiave attraverso l'operatore [].

Map

La map mantiene gli elementi ordinati secondo la loro chiave, la chiave deve essere univoca. E' implementato con una struttura ad albero rosso-nero.

#include <map>
std::map<int, char> mymap = {{1, 'a'}, {2, 'b'}};

Multimap

La multimap permette l'inserimento di chiavi duplicate.

#include <map>
std::multimap<int, char> mymap = {{1, 'a'}, {1, 'b'}};

Unordered map

La unordered map ottimizza l'accesso ai dati tramite una hash table.

#include <unordered_map>
std::unordered_map<int, char> mymap = {{1, 'a'}, {2, 'b'}};

Contenitori LIFO/FIFO

Questi contenitori sono di fatto dei contenitori sequenziali che però implementano un'accesso secondo logiche LIFO o FIFO. Sono tendenzialmente implementati sopra una lista.

Stack

Lo stack (pila) implementa un accesso LIFO, ovvero, l'ultimo elemento inserito (tramite il metodo push) è anche il primo elemento estratto (tramite il metodo pop).

#include <stack>
std::stack<int> mystack;

Queue

La queue (coda) implementa un accesso FIFO, ovvero, l'ultimo elemento inserito (tramite il metodo push) è l'ultimo elemento ad essere estratto (tramite il metodo pop).

#include <queue>
std::queue<int> myqueue;

Booleani

Bitset

Il contenitore bitset permette di salvare una sequenza di 0 o 1 a piacimento, l'accesso avviene attraverso l'operatore [] oppure attraverso i metodi set, reset e flip.

#include <bitset>
std::bitset<8> mybitset; // Bitset per 8 bit

Considerazioni sulle prestazioni

  • std::list è molto lenta nella iterazione (a causa della non contiguità nella memoria)
  • std::list gestisce bene nodi grandi
  • std::vector gestisce bene nodi piccoli
  • std::deque gestisce bene nodi piccoli
  • std::deque gestisce bene gli inserimenti casuali

Contenitori delle librerie Boost