STL - find e find_if

Dal quinto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Algoritmi standard.

Sezione dedicata agli algoritmi che non modificano le sequenze su cui operano.

Ci sono due versioni dell'algoritmo di ricerca, a seconda se si voglia specificare o meno un predicato da applicare alla ricerca.

La find() cerca il primo elemento nella sequenza che sia uguale al parametro passato, la find_if() cerca il primo che soddisfi il predicato passato come parametro.

Ecco l'esempio che mostra l'uso di find_if():

#include<algorithm>
#include<vector>
#include<iostream>

using namespace std;

void display(int x) {
    cout << x << ' ';
}

class odd {
public:

    bool operator()(int x) { // odd argument yields true
        return x % 2;
    }
};

int main() {
    vector<int> v(8);
    for (size_t i = 0; i < v.size(); ++i)
        v[i] = 2 * i; // all even
    v[5] += 1; // an odd number

    // display
    for_each(v.begin(), v.end(), display);
    cout << endl;

    // search for odd number
    vector<int>::iterator it = find_if(v.begin(), v.end(), odd());
    if (it != v.end()) {
        cout << "The first odd number (" << *it << ") was found at position "
                << (it - v.begin()) << "." << endl;
    }
    else
        cout << "No odd number found." << endl;
}

STL - for_each

Dal quinto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Algoritmi standard.

Sezione dedicata agli algoritmi che non modificano le sequenze su cui operano.

L'algoritmo for_each() opera non modifica direttamente la sequenza su cui opera, ma la funzione, o il functor (function object), che accetta come parametro può farlo.

A seguire un esempio che illustra l'uso di for_each sia con una funzione che con un functor.

#include<algorithm>
#include<vector>
#include<iostream>

using namespace std;

static void display(int x) {
    cout << x << ' ';
}

class Increment { // functor class
private:
    int increment;

public:

    Increment(int i = 1) : increment(i) {
    }

    void operator()(int& x) { // mutating operator
        x += increment;
    }
};

int main() {
    vector<int> v(5); // vector of 5 zeros

    for_each(v.begin(), v.end(), display); // 0 0 0 0 0
    cout << endl;

    // v is changed by the functor, not by for_each:
    for_each(v.begin(), v.end(), Increment(2));


    for_each(v.begin(), v.end(), display); // 2 2 2 2 2
    cout << endl;
}

STL - map e multimap

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Parte dedicata ai container associativi ordinati.

Il container associativo map gestisce collezioni di dati acceduti per mezzo di una chiave, secondo la quale sono ordinati gli elementi.

Questo é un piccole esempio d'uso per map:

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

using namespace std;

typedef map<int, string> MyMap;
typedef MyMap::value_type MyValue;
typedef pair<map<int, string>::iterator, bool> InsRet;

int main() {
    MyMap myMap;
    InsRet ret = myMap.insert(MyValue(836361136, "Andrew"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(274635328, "Berni"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(260736622, "John"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(720002287, "Karen"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(138373498, "Thomas"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(135353630, "William"));
    if(ret.second == true) {
        cout << (*(ret.first)).second << " inserted." << endl;
    }
    ret = myMap.insert(MyValue(720002287, "Xaviera"));
    if(ret.second == false) {
        cout << "As expected, item not inserted: key duplicated" << endl;
    }

    myMap[420602587] = "Willie";
    myMap[420602587] = "Willie Nillie";

    cout << endl << "The map sorted by key:" << endl;
    
    for(MyMap::iterator it = myMap.begin(); it != myMap.end(); ++it) {
        cout << (*it).first << ':' << (*it).second << endl;
    }

    cout << endl << "Finding an element by key:  ";
    int key = 720002287;
    MyMap::iterator it = myMap.find(key);
    if(it != myMap.end()) {
        cout << key << " " << (*it).second << endl;
    }

    cout << "Same, using array notation: ";
    cout << key << " " << myMap[key] << endl;
}

La multimap permette di avere chiavi duplicate, questo porta a rendere impossibile implementare l'operatore []. Inoltre, in modo simile a quanto visto per la coppia di classi set/multiset, anche per multimap il metodo insert() ritorna un iteratore all'elemento appena inserito.

STL - set e multiset

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Parte dedicata ai container associativi ordinati.

Un set é una collezione di elementi distinti. Non ci possono dunque essere due elementi uguali in una collezione. Nella implementazione STL gli elementi sono ordinati anche se questo non sarebbe strettamente necessario, se non viene specificato un ordinatore, viene usato come default less<T>.

Un esempio d'uso di set:

#include<iostream>
#include<set>

using namespace std;

/**
* check the pair returned by an insert operation on set
*/
static void checkInsertResult(pair<set<int>::iterator, bool> res) {
   cout << "Insertion ";
   if(res.second == false)
       cout << "not ";
   cout << "performed";
   if(res.second == true)
       cout << " for " << *(res.first);
   cout << endl;
}

int main() {
   set<int> mySet;

   // inserting 10 elements
   for(int i = 0; i < 10; ++i)
       checkInsertResult(mySet.insert(i));

   // trying to insert an element twice does not succeed
   checkInsertResult(mySet.insert(4));

   // dump
   set<int>::iterator it = mySet.begin();
   for(it = mySet.begin(); it != mySet.end(); ++it)
       cout << *it << ' ';
   cout << endl;

   // looking for an element that is not there
   it = mySet.find(12);
   if(it == mySet.end())
       cout << "Can't find element 12 (as expected)" << endl;

   // checking for an element in the set
   if(mySet.count(4) == 1)
       cout << "The element 4 is in the set" << endl;

   // find and remove an element
   it = mySet.find(4);
   if(it != mySet.end()) {
       mySet.erase(it);
       cout << "The element 4 erased" << endl;
   }

   // erase an elment directly
   if(mySet.erase(6) == 1)
       cout << "The element 6 erased" << endl;
   if(mySet.erase(6) == 0)
       cout << "Can't erase element 6 (as expected)" << endl;

   // dump
   it = mySet.begin();
   while(it != mySet.end())
       cout << *it++ << ' ';
   cout << endl;
}

Esiste anche la classe multiset, che permette l'esistenza di elementi ripetuti; l'interfaccia é praticamente identica a quella di set, con la differenza sostanziale del metodo insert() che ritorna, in caso di successo, l'iteratore che punta all'elemento inserito nel container.

STL - container associativi ordinati

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Parte dedicata ai container associativi ordinati.

Un container associativo permette un veloce accesso ai dati per mezzo di una chiave che può anche non coincidere con i dati. Nei set e multiset i dati stessi sono usati come chiave, mentre in map e multimap chiavi e dati sono distinti.

STL mette a disposizione quattro tipi di container associativi:

• set: le chiavi coincidono con i dati, non ci sono elementi che abbiano la stessa chiave;
• multiset: é un set in cui possono esistere elementi con la stessa chiave;
• map: chiavi e dati sono distinti, le chiavi sono uniche;
• multimap: é una map in cui possono esistere elementi con la stessa chiave.

In più, questi container STL memorizzano le chiavi in modo ordinato.

STL - priority_queue

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann.

Una coda con priorità ritorna l'elemento che ha la priorità più alta. Il criterio con cui si determina la priorità va specificato all'atto della creazione della coda.

Nell'esempio che segue, creo prima una semplice coda con priorità che contiene interi e usa come container sottostante il default (vector, in alternativa é possibile usare anche deque) e come ordinamento ancora il default (less: il che vuol dire che il più grande intero é seleziona come primo). A seguire creo un'altra coda a priorità di interi che però usa come criterio di ordinamento greater, dunque il più piccolo intero della coda é considerato in testa:

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(20);
    pq.push(10);
    pq.push(30);

    while(pq.empty() == false) {
        cout << pq.top() << ' ';
        pq.pop();
    }
    cout << endl;

    priority_queue<int, vector<int>, greater<int> > pq2;

    pq2.push(20);
    pq2.push(10);
    pq2.push(30);

    while(pq2.empty() == false) {
        cout << pq2.top() << ' ';
        pq2.pop();
    }
    cout << endl;
}

STL - queue

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann.

La coda (queue) permette di inserire oggetti ad un suo estremo e rimuoverli dalla parte opposta. Gli elementi ad entrambi i lati possono essere letti senza essere rimossi.

Può essere implementata usando list o deque.

Questi i metodi messi a disposizione:

• bool empty() const;
• size_type size() const: il numero di elementi in coda;
• value_type& front(), const value_type& front() const: legge il valore all'inizio;
• value_type& back(), const value_type& back() const: legge il valore alla fine;
• void push(const value_type& x): immette un nuovo elemento in coda;
• void pop(): elimina il primo elemento;

Un esempio di uso di uno stack:

#include<iostream>
#include<queue>

using namespace std;

int main() {
   queue<int> aQueue;

   if(aQueue.empty()) {
       cout << "Empty queue created." << endl;
   }

   cout << "size is " << aQueue.size() << endl;

   aQueue.push(5);
   aQueue.push(7);
   cout << "size is " << aQueue.size() << endl;
   cout << "front is " << aQueue.front() << endl;

   aQueue.pop();
   cout << "size is " << aQueue.size() << endl;
   cout << "front is " << aQueue.front() << endl;

   aQueue.pop();
   cout << "size is " << aQueue.size() << endl;
   cout << "front is " << aQueue.front() << endl;
}

STL - stack

Dal quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann.

Lo stack é un container che permette inserimenti, letture, eliminazione a solo ad una estremità. Come tipo implicito é possibile usare ogni container sequenziale che supporti back(), push_back() e pop_back().

L'implementazione standard usa deque.

I metodi implementati sono:

• bool empty() const: true se non ci sono elementi;
• size_type size() const: numero di elementi;
• value_type& top(), const value_type& top() const: l'elemento in cima;
• void push(const value_type& x): aggiunge un elemento in cima;
• void pop(): rimuove l'elemento in cima.

Un piccolo esempio d'uso:

#include<iostream>
#include<stack>

using namespace std;

int main() {
  stack<int> aStack;

  if(aStack.empty()) {
      cout << "Empty stack created." << endl;
  }

  cout << "size is " << aStack.size() << endl;

  aStack.push(5);
  aStack.push(7);
  cout << "size is " << aStack.size() << endl;
  cout << "top is " << aStack.top() << endl;

  aStack.pop();
  cout << "size is " << aStack.size() << endl;
  cout << "top is " << aStack.top() << endl;

  aStack.pop();
  cout << "size is " << aStack.size() << endl;
  cout << "top is " << aStack.top() << endl;
}

STL - Abstract Data Types

Il quarto capitolo di Designing Components with the C++ STL, di Ulrich Breymann, é dedicato a stack, queue e priority_queue; e poi ai container associativi ordinati: set,
map, multiset e multimap.

Le classi template presentate qui sono chiamate anche container adaptor perché adattano un interfaccia. Ad esempio quando si usa un oggetto stack si usano i metodi i metodi propri di stack che usano un container che potrebbe essere un vector.

STL - deque

Dal terzo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato ai container.

Il container deque (double ended queue: coda a doppia terminazione), come vector, permette l'accesso casuale e, come una list, permette l'inserimento e rimozione di elementi agli estremi in tempo costante. Inserimento e rimozione nel suo mezzo sono invece relativamente costosi, O(n).

Metodi aggiuntivi per deque:

• reference operator[](n), const_reference operator[](n): ritorna una referenza all'ennesimo elemento.
• reference at(n), const_reference at(n): ritorna una referenza all'ennesimo elemento, o lancia una eccezione.
• void push_front(const T& t): inserisce un elemento all'inizio.
• void pop_front(): elimina il primo elemento.

STL - List

Dal terzo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato ai container.

Il container List ha una serie di metodi aggiuntivi:

• void merge(list&), void merge(list&, Compare_object): fonde due liste ordinate - complessità O(n). E' possibile specificare la modalità di comparazione.
• void push_front(const T& t): inserisce un elemento all'inizio.
• void pop_front(): elimina il primo elemento.
• void remove(const T& t): elimina tutti gli elementi uguali a t - O(n).
• void remove_if(Predicate P): elimina tutti gli elementi per cui vale il predicato passato.
• void reverse(): inverte l'ordine degli elementi nella lista.
• void sort(), void sort(Compare_object): ordina gli elementi in una lista usando Compare_object o l'operatore < definito per gli elementi. O(n log n).
• void splice(iterator pos, list& x): sposta il contenuto della lista x prima di pos.
• void splice(iterator pos, list&x, iterator it): sposta l'elemento di x puntato da it prima di pos.
• void splice(iterator pos, list& x, iterator first, iterator last): sposta gli elementi di x in [first, last) prima di pos. Se x == this pos deve essere esterno all'intervallo passato.
• void unique(), void unique(binaryPredicate): elimina gli elementi identici consecutivi, ad eccezione del primo, se applicato ad una lista ordinata lascia solo elementi unici.

Faccio un esempio che riassume, modificando leggermente, gli esempi proposti dal libro:

#include<iostream>
#include<iterator>
#include<list>

using namespace std;

void display(const list<int>& aList) {
   list<int>::const_iterator it = aList.begin();
   while (it != aList.end())
       cout << *it++ << ' ';
   cout << "[size is " << aList.size() << ']' << endl;
}

int main() {
   list<int> list1;
   list<int> list2;
   list<int> list3;

   for (int i = 0; i < 10; ++i) {
       list1.push_front(i * 2);
       list2.push_back(i * 2 + 1);
       list3.push_back(20 + i);
   }
   display(list1);
   cout << "Sorting:" << endl;
   list1.sort();
   display(list1);

   cout << "The other list:" << endl;
   display(list2);

   cout << "Merging:" << endl;
   list1.merge(list2);
   display(list1);
   display(list2);

   cout << "The third list:" << endl;
   display(list3);

   cout << "Splice:" << endl;
   list<int>::iterator it = list3.begin();
   advance(it, 4);
   list1.splice(list1.end(), list3, list3.begin(), it);
   display(list1);
   display(list3);
}

La funzioncina display() ci mostra la scansione sequenziale di una lista via iteratore. Le tre liste sono inizializzate usando push_front() e push_back(), la prima lista viene ordinata usando sort(), dopodichè viene fusa con list2 usando merge(). La terza lista viene utilizzata per farne uno splice() in list1: i suoi primi quattro elementi vengono spostati alla fine di list1.

STL - Vector

Dal terzo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato ai container.

Vediamo un esempio di uso di vettori.

Creiamo un vettore di interi specificandone la dimensione. Se non si specifica il valore con cui vogliamo inizializzarlo, si usa zero come default.

Usiamo il metodo size() per reperire la dimensione del vettore; aggiungiamo un elemento con insert(), incrementando la dimensione del vettore; scandiamo il vettore usando un iteratore; infine scambiamo il contenuto di due vettori usando swap().

#include<vector>
#include<iostream>
using namespace std;

int main() {
    vector<int> vectA(10);

    cout << "A vector of int is initialized with 0" << endl;
    for (size_t i = 0; i < vectA.size(); ++i)
        cout << vectA[i] << ' ';
    cout << endl;

    // fill vector, random access
    for (size_t i = 0; i < vectA.size(); ++i)
        vectA[i] = i;

    // vector increases on demand, append the number 100
    vectA.insert(vectA.end(), 100);

    // use as array
    for (size_t i = 0; i < vectA.size(); ++i)
        cout << vectA[i] << ' ';
    cout << endl;

    for (vector<int>::iterator it = vectA.begin(); it != vectA.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    vector<int> vectB(20);
    cout << "\nvectB = ";
    for (size_t i = 0; i < vectB.size(); ++i)
        cout << vectB[i] << ' ';
    cout << endl;

    // swap(): a very fast method for swapping two vectors.
    vectB.swap(vectA);
    cout << "\nvectB after swapping = ";
    for (size_t i = 0; i < vectB.size(); ++i)
        cout << vectB[i] << ' ';
    cout << "\n\nvectA = ";
    for (size_t i = 0; i < vectA.size(); ++i)
        cout << vectA[i] << ' ';
    cout << endl;
}

Un altro esempio con un vettore di stringhe. Non specificando il valore da copiare, si usa come default la stringa vuota. Vediamo poi come insert() e erase() cambino la dimensione del vettore. Finiamo iterando a rovescio sul vettore.

#include<vector>
#include<iostream>
#include<string>

using namespace std;

int main() {
    vector<string> vect(4);

    cout << "A string vector is initialized with empty strings: ";
    for (size_t i = 0; i < vect.size(); ++i)
        cout << '"' << vect[i] << "\" ";
    cout << endl;

    vect[0] = "First";
    vect[1] = "Second";
    vect[2] = "Third";
    vect[3] = "Fourth";

    cout << "Setting values: ";
    for (size_t i = 0; i < vect.size(); ++i)
        cout << '"' << vect[i] << "\" ";
    cout << endl;

    vect.insert(vect.end(), "Last");
    cout << "Inserting increases the size: " << vect.size() << endl;

    vector<string>::iterator it = ++vect.begin();
    cout << "Erasing the element next to begin: " << *it << endl;
    vect.erase(it);

    cout << "Inserting reduces the size: " << vect.size() << endl;
    for (it = vect.begin(); it != vect.end(); ++it)
        cout << '"' << *it << "\" ";
    cout << endl;

    cout << "Iterating backwards: ";
    typedef vector<string>::reverse_iterator rev_it;
    for (rev_it rit = vect.rbegin(); rit != vect.rend(); ++rit)
        cout << '"' << *rit << "\" ";
    cout << endl;
}

Si noti che il costo di una inserizione o rimozione alla fine del vettore ha costo costante, O(1), altrimenti bisogna tener conto che gli indici devono essere riallineati, causando un costo proporzionale al numero di elementi che devono essere spostati, O(n).

STL - Container

Dal terzo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato ai container.

Un container é un oggetto che é usato per gestire altri oggetti che in questo contesto sono detti elementi del container. Si occupa di allocare e deallocare memoria e di controllare l'inserimento e la rimozione degli elementi.

In questo capitolo sono descritti tre container: vector, list e deque.

Metodi di un container

Ogni container mette a disposizione un insieme di metodi. Eccone un elenco, dove X é il nome del tipo del container:

• X(): default ctor; crea un container vuoto;
• X(const X&): copy ctor;
• ~X(): dtor; chiama il dtor di tutti gli elementi del container;
• iterator begin(), const_iterator begin(): inizio del container;
• iterator end(), const_iterator end(): posizione dopo l'ultimo elemento;
• size_type max_size(): massima dimensione del container;
• size_type size(): dimensione corrente del container, calcolata come la distanza tra begin() e end();
• bool empty(): equivalente a size() == 0 o begin() == end();
• void swap(X&): scambio con il container passato;
• X& operator=(const X&): operatore di assegnamento;
• bool operator==(const X&);
• bool operator!=(const X&);
• bool operator<(const X&);
• bool operator>(const X&);
• bool operator<=(const X&);
• bool operator>=(const X&);

Per un container reversibile sono disponibili anche interatori inversi e i metodi rbegin() e rend().

Sequenze

Una sequenza é un container i cui elementi sono posizionati in modo strettamente lineare.

Questi sono i metodi aggiuntivi per una sequenza:

• X(n, t): crea una sequenza con n copie di t;
• X(i, j): crea una sequenza con gli elementi nell'intervallo [i, j) copiati nella nuova sequenza;
• iterator insert(p, t): inserisce una copia di t prima della locazione p, ritorna il puntatore al nuovo elemento;
• void insert(p, n, t): inserisce n copie di t prima di p;
• void insert(p, i, j): inserisce le copie degli elementi nell'intervallo [i, j) prima di p;
• iterator erase(q): elimina l'elemento puntato da q, ritorna il puntatore alla posizione seguente a q, o end();
• iterator erase(q1, q2): elimina gli elementi nell'intervallo [q1, q2), ritorna il puntatore a q2, che può essere anche end();
• void clear(): elimina tutti gli elementi, equivale a erase(begin(), end());

Nella STL ci sono tre tipi di container sequenziali: vector, list e deque.

La lista permette di gestire efficientemente le inserzioni e eliminazioni nel mezzo del container, la doppia coda (deque = double ended queue) é utile nel caso si operi prevalentemente sugli estremi, vector corrisponde all'array. L'accesso casuale é supportato da array e deque.

Altri metodi disponibili:

• void assign(n, t = T()): rimuove gli elementi del container e poi inserisce n elementi t;
• void assign(i, j): rimuove gli elementi del container e poi inserisce gli elementi nell'intervallo [i, j).
• reference front(), const_reference front(): fornisce una reference al primo elemento del container;
• reference back(), const_reference back(): fornisce una reference all'ultimo elemento del container;
• void push_back(t): inserisce t alla fine;
• void pop_back(): elimina l'ultimo elemento;
• void resize(n, t = T()): cambia la dimensione del container, elementi vengono aggiunti o eliminati alla fine del container;
• reverse_iterator rbegin(), const_reverse_iterator rbegin(): iteratore iniziale per la scansione al contrario;
• reverse_iterator rend(), const_reverse_iterator rend(): iteratore finale per la scansione del container al contrario;

STL - Iteratori su ostream

Dal secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato agli iteratori.

Il secondo paragrafo é dedicato agli iteratori su stream, usati per lavorare direttamente sugli stream di input e output.

L'iteratore per l'ostream ostream_iterator usa l'operatore = all'elemento ottenuto per dereferenziazione allo scopo di scrivere elementi di tipo T. Elementi consecutivi sono normalmente scritti direttamente nello stream, uno dopo l'altro, senza separatori. Di solito questa non é una buona idea, dato che il risultato é spesso illeggibile.

Per evitare questo é possibile passare un parametro di tipo char* al costruttore dell'iteratore. Quella stringa verrà utilizzata come separatore dopo ogni elemento.

Faccio qui un esempio minimale, mentre quello del libro si diffonde su come gestire tipi complessi:

#include<fstream>
#include<iterator>

using namespace std;

int main() {
    ofstream target("output.txt");
    ostream_iterator<int> pos(target, "\n");
    for(int i = 0; i < 10; ++i) {
        *pos++ = i;
    }
}

Da notare l'idioma utilizzato che prevede l'uso dell'operatore di postincremento sull'iteratore, anche se questo in realtà non fa nulla, per ragioni di omogenità con l'uso degli iteratori di output in altri contesti.

STL - Iteratori su istream

Dal secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato agli iteratori.

Il secondo paragrafo é dedicato agli iteratori su stream, usati per lavorare direttamente sugli stream di input e output.

L'iteratore per l'istream istream_iterator usa l'operatore >> per leggere elementi di tipo T con la proprietà che gli spazi bianchi (ovvero spazi, tabulatori, andate a capo) sono ignorati quando trovati prima di un elemento e interpretati come separatori quando trovati tra due elementi.

Quando viene costruito e con ogni avanzamento per mezzo dell'operatore ++ l'iteratore legge un elemento di tipo T. Alla fine dello stream l'iteratore diventa uguale all'iteratore end().

Ecco un esempio di lettura da file usando questo iteratore:

#include<fstream>
#include<iostream>
#include<iterator>
#include<string>

using namespace std;

int main() {
   ifstream source("d221.cpp");

   istream_iterator<string> pos(source);
   istream_iterator<string> end;

   if(pos == end) {
       cout << "File not found!" << endl;
       return -1;
   }

   while(pos != end) {
       cout << *pos << endl;
       ++pos;
   }
}

STL - Iteratori inversi

Dal secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato agli iteratori.

Un iteratore inverso si muove all'indietro in un container usando l'operatore ++. L'inizio e la fine di un container per un iteratore inverso sono marcati dalle funzioni rbegin() (punta all'ultimo elemento) e rend() (punta a prima dell'inizio).

La funzione base() ritorna la posizione corrente come un iteratore bidirezionale.

Ci sono due tipi di iteratori inversi:

• bidirezionale: praticamente uguale a un iteratore "normale" bidirezionale, con gli operatori ++ e -- che operano come reciproci.
• accesso causale: estende l'iteratore inverso bidirezionale con operazioni aritmetiche che permettono di muoversi a salti nel container.

STL - Categorie di iteratori

Dal secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato agli iteratori.

La STL fornisce cinque categorie di iteratori:

• iteratore di input
• iteratore di output
• iteratore di avanzamento (forward)
• iteratore bidirezionale
• iteratore ad accesso casuale

Iteratore di input

Ha lo scopo di permettere la lettura da uno stream di input sequenziale, ovvero da un istream. Non c'é accesso in scrittura all'oggetto, dunque il dereferenziamento dell'iteratore non fornisce un lvalue.

Ecco un esempio d'uso:

// sourceIterator is an input iterator
sourceIterator = stream_container.begin();
while(sourceIterator != stream_container.end()) {
  value = *sourceIterator;
  // further calculations with value ...
  ++sourceIterator;
}

Iteratore di output

Ha lo scopo di scrivere in un container e anche in uno stream di output sequenziale (ostream). Non é possibile accedere in lettura all'oggetto, la dereferenziazione dell'iteratore ha l'unico scopo di permettere l'assegnamento di un valore, in questo modo:

// destinationIterator is an output iterator
*destinationIterator = value;
++destinationIterator; // advance

Di solito le due istruzioni sono combinate:

*destinationIterator++ = value;

Nel caso si usi l'iteratore su uno stream, l'avanzamento é implicito nell'assegnamento. L'operatore ++ in questo caso non fa nulla, ed é presente solo per uniformità sintattica.

Iteratore di avanzamento

Viene utilizzato, ad esempio, per lavorare su una lista singly-linked.

Iteratore bidirezionale

Estende il concetto di iteratore di avanzamento, aggiungendo la capacità di muoversi all'indietro (--). Questo lo rende adatto per la gestione di una lista doubly-linked.

Iteratore ad accesso casuale

Estende il concetto di iteratore bidirezionale, a cui aggiunge l'accesso diretto per mezzo dell'operatore []. Questo permette una gestione analoga a quella dei puntatori in C:

// position is an iterator which points to a location somewhere inside table
n1 = position - table.begin();
cout << table[n1] << endl; // is equivalent to:
cout << *position << endl;
if(n1 < n2)
  cout << table[n1] << "lies before " << table[n2] << endl;

STL - Stati di un iteratore

Dal secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann.

L'iteratore é una generalizzazione del concetto di puntatore. Il suo scopo é di permettere di lavorare in modo omogeneo con diversi container.

Un iteratore può assumere diversi stati.

Se un iteratore viene generato senza essere associato ad un container, finché non viene associato non é dereferenziato. Lo si può comparare a un puntatore a NULL.

Tipicamente un iteratore, quando viene associato ad un container, punta all'inizio del container. Il metodo begin() del container ne fornisce la posizione iniziale. Se il container non é vuoto, l'iteratore può essere dereferenziato. Con l'eccezione della posizione end(), l'iteratore può essere dereferenziato per tutte i valori che possono essere raggiunti in seguito al suo incremento (++).

Il metodo end() di un container é sempre definito e indica la posizione successiva al suo ultimo elemento. Evidentemente non é possibile dereferenziare un iteratore che punti alla posizione dopo la fine del container.

STL - Iteratori

Il secondo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, tratta degli iteratori.

Gli iteratori sono usati dagli algoritmi per muoversi nei container. Si tratta quindi di una estensione del concetto di puntatore per un array.

Le proprietà essenziali per un iteratore sono:

• l'avanzamento (++);
• la dereferenziazione (*);
• il confronto (!= o ==).

Un semplice iteratore seguirà uno schema similie al seguente:

template<class T>
class Iterator {
  public:
    // constructors, destructor
    // ...
    
    bool operator==(const Iterator<T>&) const;
    bool operator!=(const Iterator<T>&) const;
    Iterator<T>& operator++(); // prefix
    Iterator<T> operator++(int); // postfix
    T& operator*() const;
    T* operator->() const;
  private:
    // association with the container ...
};

L'operatore -> permette di usare l'iteratore allo stesso modo di un puntatore.
Se il container associato al nostro iteratore fosse un vettore, sarebbe naturale aspettarsi che venga implementato anche operator--().

STL - Concetti Fondamentali

Inizio a leggere Designing Components with the C++ STL, di Ulrich Breymann, che mi sembra un buon libro per rivedersi la STL. A seguire alcune note relative.

I più importanti elementi della STL sono contenitori, iteratori e algoritmi.

I contenitori rendono disponibili iteratori, che sono usati dagli algoritmi.

Nel paragrafo 1.3.4 Breymann ci mostra un piccolo esempio che mostra questa interazione.

Nel libro si inizia da una piccola applicazione che non usa la STL e si modifica a poco a poco il codice per renderlo più generico e adattabile al cambiamento.

Il senso del codice é quello di confrontare l'input fornito dall'utente con un array contenente i primi cento numeri pari, ovvero da 0 a 198. Se il numero passato é nell'array si comunica all'utente a che indice é stato trovato. Per terminare l'esecuzione si immette un non-numero.

Il container utilizzato é un vector, i cui iteratori sono passati all'algoritmo find.

Il codice risultante, applicando anche l'ultimo passo che nel testo é lasciato al lettore, e con qualche piccolo cambiamento aggiuntivo dovuto ai gusti personali, é il seguente:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
 const int COUNT = 100;
 vector<int> aVector(COUNT);

 // fill container with even numbers
 for (int i = 0; i < COUNT; ++i)
     aVector[i] = 2 * i;

 while (true) {
     string buffer;
     cout << "Enter required number: ";
     cin >> buffer;

     if(isdigit(buffer[0])) {
         int number = atoi(buffer.c_str());
  
         vector<int>::iterator position = find(aVector.begin(), aVector.end(), number);
         if (position != aVector.end())
             cout << "found: " << (position - aVector.begin()) << endl;
         else
             cout << number << " not found!" << endl;
     }
     else
         return 0;
 }
}