User Tools

Site Tools


appunti3s:stl

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 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:

  1. verificare la fine di una struttura dati
  2. leggere un elemento di una struttura dati
  3. 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:

#include <vector>
std::vector<float> v1;
std::vector<float>::iterator p1 = v1.begin();
  1. p1==v1.end();
  2. std::cout << *p1;        //deferenziare l'iterator come un puntatore
  3. ++p1;

vector

Per usarli si deve includere

#include <vector>

Si può presentare la struttura di un vector facendo alcuni esempi:

  • esempio che crea la struttura e la inizializza correttamente
    • std::vector<double> voti;

  • esempio che copia l'elemento passato (aggiornando la dimensione della struttura)
    • voti.push_back(6.5);

  • esempio che copia in fondo l'elemento passato (aggiornando la dimensione della struttura)
    • voti.push_back(7.5);

  • 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().
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 ...
    }
  • 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:

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 ...
}

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.

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;
}

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: [ ].

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

Esempio in cui vengono prima inseriti e poi visualizzati dei voti

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;
}

Lo stesso esempio si può ripetere sostituendo l'istruzione

std::cout << voti.at(i) << std::endl;

con l'istruzione

std::cout << voti[i] << std::endl;

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…

v1.erase(p1);
v1.insert(p1,dato);

Un'altra funzione disponibile per vector è find() che permette di trovare la posizione di un valore dato:

p1 = find(v.begin(),v.end(),valore);

Cenni agli oggetti funzione (function objects)

header <functional>

p1 = find_if(v1.begin(),v1.end,Odd());            //oggetto funzione
p1 = find_if(v1.begin(),v1.end,Less_than(dato));  //oggetto funzione

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: 2020/06/08 22:20 (external edit)