Unit Test

Non ho trovato niente di meglio come ambiente di testing per il C++ di CppUnit. Non che ne sia entusiasta, a dire il vero. Capisco che la reflection di Java sia un aiuto notevole per JUnit e che manchi qualcosa di simile per C++. C'é, é vero, la RTTI, ma si appoggia sulla vtable e quindi non é disponibile per tutte le classi C++, ed é inoltre molto rudimentale se paragonata alle funzionalità offerte dalla reflection di Java.

Però mi pare proprio che le varie soluzioni offerte per lo unit test in C++ siamo più farraginose di quello che potrebbero essere.

Ecco un esempio di testing per la classe Fibonacci, che ho mostrato nel post precedente:

#include <CppUnit/UI/Text/TestRunner.h>
#include <CppUnit/Extensions/HelperMacros.h>
#include "Fibonacci.h"

using namespace std;

class TestFibonacci : public CppUnit::TestFixture { 
public: 
  void fib0() {
    Fibonacci fib;
    CPPUNIT_ASSERT(fib.get(0) == 0);
  }

  void fib1() {
    Fibonacci fib;
    CPPUNIT_ASSERT(fib.get(1) == 1);
  }

  void fib2() {
    Fibonacci fib;
    CPPUNIT_ASSERT(fib.get(2) == 1);
  }

  void fib20() {
    Fibonacci fib;
    CPPUNIT_ASSERT(fib.get(20) == 6765);
  }

  void fibX3() {
    Fibonacci fib;
    CPPUNIT_ASSERT(fib.get(2) == 1);
    CPPUNIT_ASSERT(fib.get(20) == 6765);
    CPPUNIT_ASSERT(fib.get(3) == 2);
  }

  CPPUNIT_TEST_SUITE(TestFibonacci);
  CPPUNIT_TEST(fib0);
  CPPUNIT_TEST(fib1);
  CPPUNIT_TEST(fib2);
  CPPUNIT_TEST(fib20);
  CPPUNIT_TEST(fibX3);
  CPPUNIT_TEST_SUITE_END();
};

CPPUNIT_TEST_SUITE_REGISTRATION(TestFibonacci);

void testFibonacci() {
  CppUnit::TextUi::TestRunner runner;
  CppUnit::TestFactoryRegistry ®istry =
    CppUnit::TestFactoryRegistry::getRegistry();
  runner.addTest(registry.makeTest());

  runner.run("", false);
}

La classe TestFibonacci é una CppUnit::TestFixture che definisce le funzioni che verificano le funzionalità del codice relativo. La macro CPPUNIT_ASSERT si occupa di verificare che il valore risultante passatole sia true.

In coda alla classe una serie di macro creano la suite che raccoglie le funzioni che vogliamo includere nel testing. CPPUNIT_TEST_SUITE inizia il blocco, ricevendo in input il nome della classe, segue una CPPUNIT_TEST per ogni funzione da includere nella suite, e alla fine una CPPUNIT_TEST_SUITE_END completa la definizione della suite.

Dopo la creazione della classe, la macro CPPUNIT_TEST_SUITE_REGISTRATION si fa carico di registrare la suite in un registry apposito.

La funzione di test crea un runner (nel mio caso quello testuale) a cui viene aggiunto il test generato dal registry.

Resta da eseguire il testing usando il metodo run(), e guardare i risultati.

Fibonacci in multithreading

Un programmino di test per verificare l'uso della libreria boost thread.

La classe Fibonacci permette di calcolare il numero di fibonacci ma, per velocizzare le operazioni, quando la classe viene instanziata viene creato un nuovo thread che si prende carico di precalcolare i numeri di fibonacci.

Per evitare i problemi di overflow il numero più alto calcolabile é impostato a 40 (via la costante MAX_INDEX).

L'algoritmo per il calcolo del numero é di default quello di calcolo brutale, ma é possibile attivare l'ottimizzazione che permette di riutilizzare i valori già calcolati, velocizzando notevolmente l'esecuzione.

Qui il codice, a seguire qualche commento:

#include <iostream>
#include <vector>
#include <boost/thread.hpp>
#include <boost/thread/condition.hpp>

using namespace std;

class Fibonacci {
public:
  static const int MAX_INDEX = 40;

  Fibonacci(bool optim = false);
  ~Fibonacci();

  unsigned int get(unsigned int index);

private:
  std::vector<unsigned int> values;
  bool optim;

  boost::mutex mx;
  boost::condition cond;
  boost::thread tCalc;

  unsigned int getValue(unsigned int index);
  void precalc();
};

const int Fibonacci::MAX_INDEX;

unsigned int Fibonacci::getValue(unsigned int index) {
  if(optim)
  {
    boost::mutex::scoped_lock lock(mx);
    if(index < values.size())
      return values.at(index);
  }

  switch (index) {
  case 0:
    return 0;
  case 1:
    return 1;
  default:
    boost::this_thread::interruption_point();
    return getValue(index - 2) + getValue(index - 1);
  }
}

void Fibonacci::precalc() {
  for(int iteration = 0; iteration <= MAX_INDEX; ++iteration)
  {
    unsigned int value = getValue(iteration);
    boost::mutex::scoped_lock lock(mx);
    values.push_back(value);
    cond.notify_one();
  }
}

Fibonacci::Fibonacci(bool optim) : optim(optim) {
  values.reserve(MAX_INDEX);
  tCalc = boost::thread(&Fibonacci::precalc, this);
}

Fibonacci::~Fibonacci() {
  tCalc.interrupt();
  tCalc.join();
}

unsigned int Fibonacci::get(unsigned int index) {
  if(index < 0 || index > MAX_INDEX)
    return 0;
  boost::mutex::scoped_lock lock(mx);
  while(index >= values.size()) {
    cout << "Please wait ..." << endl;
    cond.wait(mx);
  }
  return values.at(index);
}


void fib() {
  Fibonacci fib;

  int input;
  while(true) {
    cout << "Your input [1 .. " << Fibonacci::MAX_INDEX << "]: ";
    cin >> input;
    if(input < 1 || input > Fibonacci::MAX_INDEX)
      break;
    cout << "Fibonacci of " << input << " is " << fib.get(input) << endl;
  }
  cout << "Bye" << endl;
}

Per usare la classe basta instanziarla, cosa che fa partire il thread che fa partire il precalcolo, e quindi chiamare il metodo get() specificando quale numero di fibonacci si voglia ottenere.

Il costruttore accetta un parametro opzionale che permette di ottimizzare l'algoritmo di calcolo. Nel test uso la versione senza ottimizzazione, in modo da osservare meglio il funzionamento del programma.

Altra cosa che fa il costruttore é istanziare un oggetto boost::thread sulla funzione Fibonacci::precalc() dell'oggetto corrente.

Il thread esegue la funzione precalc() che fa un loop determinato da MAX_INDEX per pre-calcolare i numeri di fibonacci. Delega alla funzione ricorsiva getValue() il calcolo del valore specifico, quindi mette un lock sul mutex che controlla il vettore, fa una push_back e quindi notifica alla condizione sul lock che qualcosa é cambiato nella cache.

La funzione getValue(), se l'ottimizzazione non é abilitata, genera il numero di fibonacci per ricorsione. Altrimenti ritorna il valore già calcolato e memorizzato nella cache - se esiste.

Da notare l'uso di boost::this_thread::interruption_point(); per definire un punto in cui é possibile interrompere l'esecuzione del thread.

Mentre un thread lavora per la generazione dei numeri di fibonacci, l'altro resta in attesa che l'utente immetta quale numero voglia calcolare.

La get() si occupa di andare a leggere nella cache se il numero richiesto sia già stato calcolato. Per far ciò crea un lock sul mutex che controlla l'accesso al vettore, se vede che il numero non é ancora stato generato, segnala all'utente che deve pazientare e si mette in attesa sulla condizione. Abbiamo visto sopra che ogni volta che un nuovo numero di fibonacci viene messo nella cache l'altro thread manda una notifica alla condizione. Ricevuta la notifica controlliamo di nuovo se la condizione é soddisfatta, e così via finché abbiamo il via libera all'accesso alla cache.

Ultima cosa che resta da vedere é il distruttore della classe, che manda un interrupt all'altro thread, e quindi fa una join.

Boost thread_specific_ptr

Nell'articolo di Bill Kempf su Dr.Dobb's che fa da introduzione alla libreria thread di boost si parla anche della possibilità di allocare memoria specifica ad un thread usando il supporto messo a disposizione dalla libreria boost thread.

In termini di prestazioni, usare la "thread local storage" o "thread specific storage", non é considerato in genere una idea molto brillante. Ma ci sono alcuni casi in cui questa risulta essere la soluzione più ragionevole.

La libreria boost thread mette a disposizione uno smart pointer, boost::thread_specific_ptr, che viene inizializzato a NULL della cui distruzione si fa carico la libreria stessa.

L'utilizzo di questo smart pointer viene mostrato nell'esempio a seguire:

#include <iostream>
#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/tss.hpp>

using namespace std;

namespace {
  boost::thread_specific_ptr<int> ptr;
  boost::mutex mio;

  class Count
  {
  private:
    int step;

  public:
    Count(int step) : step(step) { }

    void operator()()
    {
      if (ptr.get() == 0) {
        ptr.reset(new int(0));
      }

      for (int i = 0; i < 10; ++i)
      {
        *ptr += step;
        boost::mutex::scoped_lock lock(mio);
        cout << boost::this_thread::get_id() << ": "
             << *ptr << endl;
        boost::this_thread::sleep(boost::posix_time::milliseconds(15));
      }
    }
  };
}

void dd05()
{
  boost::thread t1(Count(1));
  boost::thread t2(Count(-1));
  t1.join();
  t2.join();
}

Vengono creati due thread, associati ad un functor che viene costruito col parametro passato che viene utilizzato in un loop per modificare un valore locale al thread.

Per prima cosa verifichiamo che l'istanza di boost::thread_specific_ptr sia NULL, e la inizializziamo come richiesto. Poi facciamo un loop che incrementa di passo in passo la nostra variabile locale al thread e la stampa su cout, opportunamente protetto da un lock su mutex. Ho aggiunto uno sleep sul thread in modo da rendere più movimentata la competizione dei thread sul mutex.

Boost mutex e condizioni

Proseguendo la lettura dell'articolo di Bill Kempf su Dr.Dobb's che fa da introduzione alla libreria thread di boost, arriviamo alle variabili di condizione.

A volte non basta un lock su una risorsa condivisa, dato che occorre che la risorsa sia in un particolare stato prima di poterla usare. E questo é proprio lo scopo delle variabili di condizione.

L'idea generale é che il thread blocca un mutex sulla risorsa condivisa e quindi verifica che lo stato sia quello atteso. Se non lo é si mette in attesa sulla condizione. Facendo ciò libera il mutex, permettendo l'accesso alla risorsa da parte di un altro thread. Quando lo stato diventa tale per cui il thread in attesa sulla condizione può tornare ad agire, riceve una notifica che gli permette di ripartire.

Nell'esempio che segue, tratto dall'articolo e leggermente modificato da me, vengono creati due thread, uno per leggere e uno per scrivere su di un buffer condiviso. Per essere sicuri che si inizi a leggere quando non c'é ancora niente da leggere - e quindi avere certamente una situazione in cui é necessario che il lettore venga messo in attesa - ho inserito una pausa nel thread principale tra la creazione del thread in lettura e quello in scrittura.

La funzione utilizzata é boost::this_thread::sleep() che fa "dormire" il thread per un determinato intervallo (o fino a un certo momento). Per specificare quanto tempo debba dormire il thread é possibile usare la funzione boost::posix_time::milliseconds() che converte un intero in millisecondi.

Le due funzioni reader e writer sono simmetriche, leggono e scrivono su di un buffer rappresentato dalla classe Buffer. Notiamo che mettono un lock su un mutex per accedere la risorsa condivisa cout.

La classe Buffer é praticamente un wrapper costruito intorno alla risorsa condivisa, una lista circolare di interi. Il nostro problema é che non possiamo leggere da questo container quando é vuoto, e nemmeno scriverci quando é pieno. Dunque, prima di leggere e scrivere dobbiamo verificare la sua condizione.

Vediamo la funzione put(). Per prima cosa crea uno scoped_lock sul mutex che sorveglia l'accesso al circular_buffer, quindi controlla se é pieno. Se questo é il caso, stampa un messaggio (controllando l'accesso a cout con uno scoped_lock sul mutex di competenza) e si mette in attesa sulla condizione relativa al lock.

Abbiamo dunque un mutex, un lock che usa il mutex per gestire l'accesso alla risorsa e una condizione sul lock che permette al thread di passare il controllo in attesa di tempi migliori.

Quando abbiamo la possibilità, mettiamo il valore passato nel container e notifichiamo alla condizione che ne abbiamo cambiato lo stato.

La get() funziona in modo equivalente: se il container é vuoto si mette in attesa. Appena possibile legge un elemento, lo elimina dal container e notifica alla condizione che lo stato del container é cambiato.

Questo il codice risultante:

#include <iostream>
#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#include <boost/circular_buffer.hpp>

using namespace std;

namespace {
  boost::mutex mio;

  class Buffer
  {
  private:
    static const int BUF_SIZE = 3;

    boost::mutex mcb;
    boost::condition cond;
    boost::circular_buffer<int> cb;

  public:
    Buffer(int size = BUF_SIZE) : cb(size) {}

    void put(int m) {
      boost::mutex::scoped_lock lock(mcb);
      if(cb.full())
      {
        {
          boost::mutex::scoped_lock lock(mio);
          cout << "Buffer is full. Waiting..." << endl;
        }
        while (cb.full())
          cond.wait(lock);
      }
      cb.push_back(m);
      cond.notify_one();
    }

    int get()
    {
      boost::mutex::scoped_lock lock(mcb);
      if (cb.empty())
      {
        {
          boost::mutex::scoped_lock lock(mio);
          cout << "Buffer is empty. Waiting..." << endl;
        }
        while (cb.empty())
          cond.wait(lock);
      }

      int i = cb.front();
      cb.pop_front();
      cond.notify_one();
      return i;
    }
  };

  const int Buffer::BUF_SIZE;

  Buffer buf;

  const int ITERS = 20;

  void writer()
  {
    for (int n = 0; n < ITERS; ++n)
    {
      {
        boost::mutex::scoped_lock lock(mio);
        cout << "sending: " << n << endl;
      }
      buf.put(n);
    }
  }

  void reader()
  {
    for (int x = 0; x < ITERS; ++x)
    {
      int n = buf.get();
      {
        boost::mutex::scoped_lock lock(mio);
        cout << "received: " << n << endl;
      }
    }
  }
}

Boost thread: functor o funzione

Ancora leggendo l'articolo di Bill Kempf su Dr.Dobb's che fa da introduzione alla libreria thread di boost.

Qui vediamo come passare al costruttore dell'oggetto boost::thread l'indirizzo di una funzione e parametri per la funzione stessa.

L'esempio del post precedente usava un functor nella creazione del thread, ma é possibile ottenere lo stesso effetto con una funzione.

Nelle versioni di qualche anno fa di boost, si otteneva l'effetto con un binding tra puntatore alla funzione e parametro, nelle versioni più recenti basta, ancor più semplicemente, passare i parametri alla funzione dopo il puntatore nel costruttore del thread.

L'esempio qui sotto riporta la "vecchia" implementazione, commentata, e la nuova:

#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/bind.hpp>
#include <iostream>

using namespace std;

namespace {
  boost::mutex mio;

  void count(int multi)
  {
    for (int i = 0; i < 10; ++i)
    {
      boost::mutex::scoped_lock lock(mio);
      cout << boost::this_thread::get_id() << ": "
           << multi * i << endl;
    }
  }
}

void dd03()
{
//  boost::thread t1(boost::bind(&count, 1));
//  boost::thread t2(boost::bind(&count, 2));

  boost::thread t1(&count, 1);
  boost::thread t2(&count, -1);

  t1.join();
  t2.join();
}

Boost mutex

Continuo la lettura dell'articolo di Bill Kempf su Dr.Dobb's che fa da introduzione alla libreria thread di boost.

Vediamo l'uso della mutua esclusione, ovvero mutex, al fine di permettere la gestione di risorse condivise tra diversi thread.

Ho leggermente modificato l'esempio proposto nell'articolo mantenendone l'impianto complessivo. Sono creati due thread che eseguono lo stesso functor. In pratica si esegue un ciclo for che stampa sulla consolle l'identificatore del thread a un valore funzione della variabile di ciclo e del parametro passato al functor.

La parte interessante é che i due thread operano su una risorsa condivisa, lo stream di output verso la consolle, che deve essere quindi regolamentata nel suo accesso, per evitare che le stringhe mandate a video si sovrappongano.

Per far ciò usiamo un mutex che fa da semaforo d'accesso alla regione critica, bloccando l'accesso per mezzo di un lock, per la precisione un boost::mutex::scoped_lock, ovvero un lock che termina automaticamente quando la variabile che lo determina esce di scopo. Così abbiamo la certezza che anche in caso di eccezioni il lock sul mutex venga tolto.

#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <iostream>

using namespace std;

namespace {
  boost::mutex mio;

  class Count
  {
    int multi;
  public:
    Count(int multi) : multi(multi) { }

    void operator()()
    {
      for (int i = 0; i < 10; ++i)
      {
        boost::mutex::scoped_lock lock(mio);
        cout << "Thread " << boost::this_thread::get_id()
             << ", result: " << i*multi << endl; 
      }
    }
  };
}

void dd02()
{
  boost::thread t1(Count(1));
  boost::thread t2(Count(-1));
  t1.join();
  t2.join();
}

Creare un thread con boost

Un buon modo per avere un'idea della libreria thread di boost é leggersi questo articolo di Bill Kempf su Dr.Dobb's.

E' un po' vecchiotto, maggio 2002, ma mi pare ancora utile. Per gli aggiornamenti si fa riferimento ad un articolo del 2008 firmato da Anthony Williams.

Per creare un nuovo thread con boost creiamo un oggetto boost::thread passando la funzione o il functor su cui insiste il nuovo thread.

Il primo esempio presentato, che ho leggermente modificato rispetto a quanto presentato nell'articolo, ci fa vedere come creare un thread che esegue il codice di una funzione:

#include <boost/thread/thread.hpp>
#include <iostream>

using namespace std;

namespace {
 void hello()
 {
  cout << "This is the thread " << boost::this_thread::get_id() << endl;
 }
}

void dd01()
{
 cout << "We are currently in the thread " << boost::this_thread::get_id() << endl;
 boost::thread t(&hello);
 t.join();
 cout << "Back to the thread " << boost::this_thread::get_id() << endl;
}

Basta passare al costruttore dell'oggetto boost::thread l'indirizzo della funzione. La funzione join(), poi, ci permette di terminare il thread.

Ho usato la funzione boost::this_thread::get_id(), di cui non si parla nell'articolo perché a quei tempi ancora non esisteva, per mostrare l'id dei due thread.

Boost bind

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

bind

La STL mette a disposizione bind1st e bind2nd per permettere il binding a functor già esistenti. Boost estende questo concetto con bind.

Per prima cosa, mi rivedo un uso di bind1st:

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;

int main () {
  int numbers[] = {10,20,30,40,50,10};
  int cx = count_if (numbers, numbers+6, bind1st(equal_to<int>(), 10) );
  cout << "There are " << cx << " elements that are equal to 10.\n";
}

Chiamo la count_if passando come predicato il functor equal_to che viene adattato dalla bind1st in modo da usare, oltre al parametro passato dalla count_if, ovvero l'elemento corrente nella scansione della sequenza, un valore fisso - 10 nel nostro caso.

Riscrivere questo specifico esempio con boost:bind non porta un gran vantaggio, anzi, a ben vedere, sembra piuttosto una soluzione peggiore, dato che occorre specificare il segnaposto (_1) utilizzato.

Ma boost:bind é più potente di bind1st, e lo vediamo quando vogliamo usare una funzione e non un functor (come é obbligatorio fare per bind1st).

Vero é che spesso é possibile adattare una funzione alle specifiche di bind1st ma questo comporta un appesentimento del codice, e non sempre é possibile farlo.

Altro punto a favore di boost::bind é la possibilità di innestare diverse chiamate, come nell'ultimo esempio d'uso che riporto.

#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <boost/bimap.hpp>

using namespace std;

class A {
    int value_;
public:

    A(int value) : value_(value) {
    }

    void print() {
        cout << "Value is: " << value_ << endl;
    }
};

void doSomething(int a, int b) {
    if (a == b) {
        cout << "done" << endl;
    }
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50, 10};

    int cx = count_if(numbers, numbers + 6, bind1st(equal_to<int>(), 10));
    cout << cx << endl;

    cx = count_if(numbers, numbers + 6, boost::bind(equal_to<int>(), _1, 10));
    cout << cx << endl;

    for_each(numbers, numbers + 6, boost::bind(&doSomething, _1, 10));

    vector<A> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    for (vector<A>::iterator it = v.begin(); it != v.end(); ++it) {
        it->print();
    }

    cout << "for_each:" << endl;
    for_each(v.begin(), v.end(), mem_fun_ref(&A::print));

    cout << "for_each w/ boost::bind:" << endl;
    for_each(v.begin(), v.end(), boost::bind(&A::print, _1));

    cout << "count w/ nested boost::bind:" << endl;
    int count = count_if(numbers, numbers + 6,
        boost::bind(logical_and<bool>(),
            boost::bind(greater<int>(), _1, 15),
            boost::bind(less_equal<int>(), _1, 40)));
    cout << count << endl;
}

Boost variant

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

variant

Con boost::variant si ha una miglior gestione di un tipo generico rispetto a quanto offerto da boost::any.

In particolare, all'atto della creazione di un oggetto possiamo specificare quali tipi sono accettabili in quel specifico caso.

Per estrarre l'oggetto dal variant possiamo usare la funzione get<>(), che funziona come any_cast<>(). Il suo svantaggio é che tende a rendere il programma ingestibile.

Quando possibile é opportuno usare un functor che specializzi la classe static_visitor. Questa deve avere l'implementazione dell'operator() per ogni tipo gestito dal variant che lo usa. Se ne manca uno, si ha un errore in compilazione.

Un esempio dovrebbe chiarire quanto scritto sopra:

#include <iostream>
#include <boost/variant.hpp>

using namespace std;

class Printer : public boost::static_visitor<void> {
public:
  void operator()(int& i) const {
    cout << "It's an int: " << i << endl;
  }

  void operator()(string& s) const {
    cout << "It's a string: " << s << endl;
  }

  void operator()(double& d) const {
    cout << "It's a double: " << d << endl;
  }
};

int main() {
    boost::variant<int,string,double> var("Hello");

    string hello = boost::get<string>(var);

    cout << "Var contains: " + hello << endl;

    try {
        int wrong = boost::get<int>(var);
        cout << "Unexpected: " << wrong << endl;
    }
    catch(const boost::bad_get& exc) {
        cout << "There's not an int in: " << exc.what() << endl;
    }

    int* pWrong = boost::get<int>(&var);
    if(pWrong == NULL) {
        cout << "There's not an int in var." << endl;
    }

    Printer p;
    boost::apply_visitor(p, var);
}

Boost any

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

any

La classe boost::any permette di trattare allo stesso modo oggetti di tipo diverso, permettendo ad esempio di usare un container STL per una collezione di oggetti eterogenei.

Nell'esempio che segue, metttiamo oggetti di svariati tipi in un container di boost::any. Dato che il costruttore di any non é esplicito, ci possiamo anche risparmiare la fatica di fare un cast che viene fatto, per l'appunto, implicitamente.

La funzione anyPrint() ci mostra come estrarre l'oggetto da any usando any_cast<> sull'indirizzo dell'oggetto any. Se l'oggetto non é del tipo atteso, any_cast<> ritorna NULL. Alternativamente, se il fallimento del casting fosse considerabile un errore, potremmo tentare di applicare any_cast<> sull'oggetto. In questo caso il fallimento porterebbe ad una eccezione - come si vede nel caso della gestione del tipo string nella stessa funzione.

#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "boost/any.hpp"

using namespace std;

class A {
public:

    void some_function() {
        cout << "A::some_function()" << endl;
    }
};

class B {
public:

    void some_function() {
        cout << "B::some_function()" << endl;
    }
};

class C {
public:

    void some_function() {
        cout << "C::some_function()" << endl;
    }
};

typedef pair<bool, double> BoolDouble;

void anyPrint(boost::any& a) {
    if (A* pA = boost::any_cast<A> (&a)) {
        pA->some_function();
    } else if (B* pB = boost::any_cast<B> (&a)) {
        pB->some_function();
    } else if (C* pC = boost::any_cast<C> (&a)) {
        pC->some_function();
    } else if (int* pInt = boost::any_cast<int> (&a)) {
        cout << *pInt << endl;
    } else if (BoolDouble* pPair = boost::any_cast<BoolDouble> (&a)) {
        if (pPair->first)
            cout << pPair->second << endl;
    } else {
        try {
            cout << boost::any_cast<string> (a) << '\n';
        } catch (boost::bad_any_cast&) {
            cout << "Oops!\n";
        }
    }
}

int main() {
    cout << "Example of using any.\n\n";

    vector<boost::any> store_anything;

    store_anything.push_back(A());
    store_anything.push_back(B());
    store_anything.push_back(C());

    // While we're at it, let's add a few other things as well
    store_anything.push_back(string("This is fantastic! "));
    store_anything.push_back(3);
    store_anything.push_back(make_pair(true, 7.92));
    store_anything.push_back(3.14);

    for_each(store_anything.begin(), store_anything.end(), anyPrint);
}

Boost regex

Per poter usare le esperessioni regolari di boost occorre per prima cosa generare la libreria regex.

Io uso cygwin in coppia con netbeans, e questi sono i passaggi che ho dovuto seguire per poter compilare ed eseguire un primo programma di prova in questo contesto.

Dalla directory /libs/regex/build ho richiamato la make con questa sintassi:

make -fgcc.mak

Il cui risultato finale é stato quello di generare due librerie (una "normale" e una di debug):

gcc/libboost_regex-gcc-1_40.a
gcc/libboost_regex-gcc-d-1_40.a

In Netbeans ho creato un progetto, nelle cui proprietà ho aggiunto nella sezione Build-Linker-Libraries la libreria regex ("normale") appena creata.

Ho aggiunto al progetto un file di esempio:

#include <boost/regex.hpp>
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
    boost::regex reg("(A.*)");

    if(boost::regex_match("Doesn't match", reg))
        cout << "unexpected!";
    if(boost::regex_match("A good match", reg))
        cout << "matching" << endl;
}

Ho creato la regex "(A.*)", e ho verificato che solo la seconda stringa le corrisponde.

Boost weak_ptr

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

weak_ptr

Un weak_ptr é un osservatore di un shared_ptr. Quando lo shared_ptr rilascia la risorsa associata, mette a null il puntatore associato a weak_ptr. In questo modo weak_ptr non assume la proprietà della risorsa, e non rischia di detenere un puntatore che potrebbe rimanere disassociato alla risorsa stessa.

Il metodo lock() di waek_ptr permette di ottenere un shared_ptr da un lock_ptr, gestendo il reference count come atteso.

Ecco un esempio per weak_ptr:

#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>

using namespace std;
using namespace boost;

int main() {

  boost::weak_ptr<int> w;
  if(w.expired())
      cout << "1: weak_ptr initialized as expired" << endl;

  {
    shared_ptr<int> p(new int);
    if(p.use_count()==1)
        cout << "2: reference count for shared_ptr set to 1" << endl;
    w=p;
    if(p.use_count()==1)
        cout << "3: weak_ptr observe without changing ref count" << endl;

    shared_ptr<int> p2(w);
    if(p.use_count()==2)
        cout << "4: creating a shared_ptr from a weak_ptr" << endl;
  }
  if(w.expired())
      cout << "5: weak_ptr expires" << endl;

  shared_ptr<int> p3=w.lock();
  if(p3 == false)
      cout << "6: shared_ptr from expired weak_ptr is not initialized" << endl;
}

Boost shared_ptr

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

shared_ptr

Lo smart pointer shared_ptr é reference counted allo scopo di permettere la condivisione dell'oggetto sottostante tra diverse istanze. Il distruttore dell'oggetto viene chiamato quando il reference count scende a zero.

Ecco un esempio con shared_ptr:

#include<iostream>
#include<boost/shared_ptr.hpp>

using namespace std;
using namespace boost;

class A {
    shared_ptr<int> no_;
public:
    A(shared_ptr<int> no) : no_(no) {
    }

    void value(int i) {
        *no_ = i;
    }
};

class B {
    shared_ptr<int> no_;
public:
    B(shared_ptr<int> no) : no_(no) {
    }

    int value() const {
        return *no_;
    }
};

int main() {
    shared_ptr<int> temp(new int(14));

    if (temp.unique())
        cout << "Unique" << endl;

    A a(temp);
    if (temp.unique() == false)
        cout << "Not anymore unique" << endl;

    B b(temp);
    cout << "Reference count now is " << temp.use_count() << endl;

    temp.reset();

    a.value(28);
    cout << "b value now is " << b.value() << endl;
}

Definiamo due classi che usano al loro interno un shared_ptr che viene creato per copia.

Nel main creiamo temp, un shared_ptr, verifichiamo che la risorsa sottostante sia inzialmente unica; creiamo un oggetto A, passando una copia di temp, verifichiamo che il reference count sia stato incrementato, unique() é ora false, creiamo un oggetto B e vediamo che ora il reference count é posto a tre. Con una chiamata a reset() sleghiamo temp dalla risorsa sottostante; cambiamo il valore associato ad a e vediamo che questo cambiamento si riflette in b.

Uno degli usi di shared_ptr é in combinazione dei container STL. Il bello é che anche il polimorfismo viene gestito correttamente, come vediamo in quest'altro esempio:

#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>

using namespace std;
using namespace boost;

class A {
public:
    virtual void sing() = 0;
protected:
    virtual ~A() {
    };
};

class B : public A {
public:
    virtual void sing() {
        cout << "Do re mi fa so la" << endl;
    }
};

shared_ptr<A> createA() {
    shared_ptr<A> p(new B());
    return p;
}

int main() {
    typedef vector<shared_ptr<A> > containerType;
    typedef containerType::iterator iterator;

    containerType container;
    for (int i = 0; i < 10; ++i) {
        container.push_back(createA());
    }

    cout << "The choir is gathered:" << endl;
    iterator end = container.end();
    for (iterator it = container.begin(); it != end; ++it) {
        (*it)->sing();
    }
}

Boost scoped_ptr

Da Beyond the C++ Standard Library: An Introduction to Boost, di Björn Karlsson.

scoped_ptr

Lo smart pointer scoped_ptr ricorda da vicino auto_ptr. La differenza sostanziale tra questi due tipi é che non é possibile copiare o assegnare uno scoped_ptr.

É utile usare scoped_ptr quando si prevede che non ci sia un passaggio di proprietà per il puntatore di riferimento.

Ecco un esempio che tocca le funzionalità offerte da scoped_ptr

#include <string>
#include <iostream>
#include "boost/scoped_ptr.hpp"

using namespace std;
using namespace boost;

void checkSize(scoped_ptr<string>& p) {
    if (p)
        cout << *p << " size is " << p->size() << endl;
    else
        cout << "p is NULL" << endl;
}

int main() {
    scoped_ptr p(new string("Hello"));
    checkSize(p);

    *p = "Just like a pointer";
    checkSize(p);
    cout << "p is still " << *p << endl;

    p.reset(0);
    checkSize(p);

    string* raw = p.get();
    if(raw == 0)
        cout << "raw is a null pointer" << endl;

    scoped_ptr<string> q(new string("Bye"));
    p.swap(q);
    cout << "p after swapping is " << *p << endl;
}

La funzione checkSize() accetta come parametro un riferimento a scoped_ptr. Nota che un oggetto di questo tipo non può essere passato per valore, dato che non é possibile farne una copia.

All'interno della funzione viene usato l'operatore ->, per chiamare la funzione size() del tipo sotteso allo smart pointer (string). Viene inoltre verificato il test contro NULL per il puntatore interno allo smart pointer, utilizzato come argomento dell'if.

Nel main() viene creato un oggetto scoped_ptr passandogli un puntatore a string costruito al volo.

Vediamo che usando l'operatore * in associazione con l'operatore assegnamento si ottiene di resettare il puntatore associato, nello stesso modo in cui si opererebbe con un puntatore grezzo. Si ottiene lo stesso effetto, come vediamo più sotto, utilizzando la funzione membro reset().

La funzione get() ritorna il puntatore grezzo. É una funzione che va utilizzata con prudenza, dato che occorre tenere bene in mente che la proprietà dell'oggetto resta comunque allo smart pointer.

Con swap() é possibile scambiare il contenuto di due scoped_ptr.

STL - accumulate

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

Sezione dedicata alle operazioni numeriche generali utilizzabili includendo numeric.

5.6.4: accumulate

Il comportamento standard di accumulate é quello di sommare tutti gli elementi della sequenza passata. É possibile passare un'altra operazione, ad esempio il prodotto, per ottenere differenti risultati.

Ecco un esempio di sommatoria e produttoria:

#include<algo.h>
#include<numeric>
#include<vector>

using namespace std;

int main() {
    vector<int> v(10);
    iota(v.begin(), v.end(), 1);

    vector<int>::const_iterator last = --(v.end());
    cout << "The sequence " << v[0] << ", " << v[1] << ", ..., " << *last;
    cout << " has sum " << accumulate(v.begin(), v.end(), 0)  << " and product ";
    cout << accumulate(v.begin(), v.end(), 1L, multiplies()) << endl;
}

STL - set_symmetric_difference

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6.4: set_symmetric_difference

Con set_symmetric_difference() si genera una sequenza che é l'"or-esclusivo" tra le due sequenze passate. Ovvero la sequenza risultante contiene tutti e soli gli elementi che sono in una delle due sequenze passate, ma non in entrambe.

Ad esempio:

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

using namespace std;

void dump(const set<int>& v) {
    set<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    int v1[] = {0, 1, 2, 3, 4, 5, 7, 99, 13};
    int v2[] = {-2, 5, 12, 7, 33};

    set<int> s1(v1, v1 + sizeof v1 / sizeof *v1);
    set<int> s2(v2, v2 + sizeof v2 / sizeof *v2);

    set<int> result;

    set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(result, result.begin()));

    cout << "The ex-or between: ";
    dump(s1);
    cout << "and: ";
    dump(s2);
    cout << "yields to: ";
    dump(result);
}

STL - set_difference

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6.4: set_difference

Con set_difference() si genera una sequenza che é la differenza tra le due sequenze passate. Ovvero la sequenza risultante contiene tutti e soli gli elementi che sono nella prima sequenza ma non nella seconda.

Ad esempio:

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

using namespace std;

void dump(const set& v) {
    set<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    int v1[] = {0, 1, 2, 3, 4, 5, 7, 99, 13};
    int v2[] = {-2, 5, 12, 7, 33};

    set<int> s1(v1, v1 + sizeof v1 / sizeof *v1);
    set s2(v2, v2 + sizeof v2 / sizeof *v2);

    set<int> result;

    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(result, result.begin()));

    cout << "The intersection between: ";
    dump(s1);
    cout << "and: ";
    dump(s2);
    cout << "yields to: ";
    dump(result);
}

STL - set_intersection

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6.3: set_intersection

La set_intersection() costruisce una sequenza che contiene gli elementi presenti in entrambe le sequenze ordinate passate in input. Dunque costruisce l'intersezione tra le due sequenze originali.

Ecco un esempio:

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

using namespace std;

void dump(const set<int>& v) {
   set<int>::const_iterator it = v.begin();
   while (it != v.end()) {
       cout << *it++ << ' ';
   }
   cout << endl;
}

int main() {
   int v1[] = {0, 1, 2, 3, 4, 5, 7, 99, 13};
   int v2[] = {-2, 5, 12, 7, 33};

   set<int> s1(v1, v1 + sizeof v1 / sizeof *v1);
   set<int> s2(v2, v2 + sizeof v2 / sizeof *v2);

   set<int> result;

   set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
           inserter(result, result.begin()));

   cout << "The intersection between: ";
   dump(s1);
   cout << "and: ";
   dump(s2);
   cout << "yields to: ";
   dump(result);
}

STL - set_union

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6.2: set_union

La set_union costruisce una sequenza ordinata che contiene tutti gli elementi che si trovano in almeno una delle due sequenze passate in input. Dunque la sequenza risultante é l'unione delle due sequenze di partenza.

Ecco un esempio:

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

using namespace std;

void dump(const set<int>& v) {
    set<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    int v1[] = {1, 2, 3, 4};
    int v2[] = {-2, 5, 12, 7, 33};

    set<int> s1(v1, v1 + sizeof v1 / sizeof *v1);
    set<int> s2(v2, v2 + sizeof v2 / sizeof *v2);

    set<int> result;

    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(result, result.begin()));

    cout << "The union between: ";
    dump(s1);
    cout << "and: ";
    dump(s2);
    cout << "yields to: ";
    dump(result);
}

STL - includes

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6.1: includes

La funzione includes richiede in input gli iteratori che determinano due sequenze, chiamiamole S1 e S2 e ritorna true se S2 é un sottoinsieme di S1. Dunque il risultato é true se e solo se tutti gli elementi di S2 sono uguali ad elementi di S1.

Segue un esempio che dovrebbe spiegare meglio la cosa:

#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

void dump(const set<int>& v) {
    set<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {

    int v1[] = {1, 2, 3, 4};
    int v2[] = {0, 1, 2, 3, 4, 5, 7, 99, 13};
    int v3[] = {-2, 5, 12, 7, 33};

    set<int> s1(v1, v1 + sizeof v1/sizeof *v1);
    set<int> s2(v2, v2 + sizeof v2/sizeof *v2);
    set<int> s3(v3, v3 + sizeof v3/sizeof *v3);

    if (includes(s2.begin(), s2.end(), s1.begin(), s1.end())) {
        cout << "This set: ";
        dump(s1);
        cout << "is a subset of: ";
        dump(s2);
    }
    if(includes(s2.begin(), s2.end(), s3.begin(), s3.end()) == false) {
        cout << "While this set: ";
        dump(s3);
        cout << "is not." << endl;
    }
}

STL - operazioni insiemistiche

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

Sezione dedicata operazioni insiemistiche su strutture ordinate.

5.6: Condizioni e limitazioni

Gli algoritmi di questa sezione hanno il limite che l'iteratore di output deve fare riferimento a un container che ha abbastanza spazio allocato per ricevere il risultato. In alternativa é possibile usare un iteratore di inserimento, ma in questo caso il container deve essere vuoto.

Nel primo caso, il rischio é che il container in output non sia dimensionato correttamente, e dunque occorre non considerare gli elementi in coda al container stesso, o addirittura, nel caso lo spazio sia insufficiente, si avrà un crash.

Usando un iteratore di inserimento il rischio é quello di operare su un container non vuoto, che avrà quindi elementi spuri al termine dell'operazione.

STL - inplace_merge

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

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.4: inplace_merge

Questa variazione dell'algoritmo merge() usa un buffer interno per eseguire la fusione sul posto (in-place) di due sequenze che si trovano nello stesso container.

Le due semisequenze devono essere ordinate e consecutive. All'algoritmo vengono passati i tre iteratori che le delimitano.

Ad esempio:

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

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    std::vector<int> v(16); // even number
    int middle = v.size() / 2;
    for (int i = 0; i < middle; ++i) {
        v[i] = 2 * i; // even
        v[middle + i] = 2 * i + 1; // odd
    }
    cout << "Before: ";
    dump(v);
    inplace_merge(v.begin(), v.begin() + middle, v.end());
    cout << "After : ";
    dump(v);
}

STL - merge

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

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.4: merge

Usando merge() possiamo unire due sequenze ordinate in una. Passo dopo passo, i primi elementi delle due sequenze sono confrontati e il minore (o quello che soddisfa il criterio di ordinamento passato) viene messo nella sequenza di output.

Ad esempio:

#include<iostream>
#include<algorithm>
#include<vector>
#include<algo.h>

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    vector<int> v1(6);
    iota(v1.begin(), v1.end(), 0);
    dump(v1);

    vector<int> v2(10);
    iota(v2.begin(), v2.end(), 0);
    dump(v2);

    vector<int> result(v1.size() + v2.size());
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    dump(result);
}

STL - Ricerca binaria

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

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.3: binary_search, lower_bound, upper_bound, equal_range

Questi algoritmi lavorano su una sequenza che é supposta ordinata in ordine crescente, o con lo stesso ordine specificato dal comparatore che passiamo alla funzione.

Con binary_search controlliamo se esiste un elemento nella sequenza passata che per cui valga la relazione (!(*i < value) && !(value < *i).

L'iteratore tornato da lower_bound punta alla prima posizione in cui possiamo inserire nella sequenza un valore senza alterarne l'ordinamento.

L'iteratore tornato da upper_bound punta all'ultima posizione in cui possiamo inserire nella sequenza un valore senza alterarne l'ordinamento.

La coppia di iteratori tornata da equal_range delimita l'intervallo in cui é possibile inserire il valore senza alterare l'ordinamento della sequenza.

Ecco un esempio:

#include<iostream>
#include<algorithm>
#include<list>
#include<string>

using namespace std;

void dump(const list<string>& v) {
    list<string>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    list<string> places;
    places.push_front("Bremen");
    places.push_front("Paris");
    places.push_front("Milan");
    places.push_front("Hamburg");
    places.sort(); // important precondition!
    dump(places);

    string city("Tokio");
    if (binary_search(places.begin(), places.end(), city) == false)
        cout << city << " does not exist in the list" << endl;

    city = "Milan";
    if (binary_search(places.begin(), places.end(), city))
        cout << city << " is already in the list" << endl;

    cout << "Duplicating " << city << " in the list ..." << endl;
    list<string>::iterator it = lower_bound(places.begin(), places.end(), city);
    places.insert(it, city);
    dump(places);

    // range of identical values
    pair<list<string>::const_iterator, list<string>::const_iterator> p =
            equal_range(places.begin(), places.end(), city);

    // The two iterators of the pair p limit the range in which City occurs:
    list<string>::difference_type n = distance(p.first, p.second);
    cout << city << " is contained " << n << " times in the list" << endl;
}

Inizializziamo la lista, la ordiniamo, verifichiamo con una prima chiamata a binary_search() che Tokio non sia nella lista, e con una seconda vediamo che Milan invece c'é. Con lower_bound() troviamo la prima posizione in cui é possibile inserire Milan mantenendo l'ordine nella lista. Con equal_range() troviamo gli iteratori all'inizio e alla fine del subintervallo contenente gli elementi "Milan", con distance() ne troviamo il numero.

STL - nth_element

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

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.2: nth_element

É possibile usare nth_element() per trovare l'ennesimo elemento di una sequenza a partire dal più piccolo o dal più grande.

L'algoritmo chiede che vengano passatati in input tre iteratori, all'inizio della sequenza, al ennesimo valore che vogliamo trovare, e alla fine della sequenza. Inoltre é possibile passare un comparatore, se non vogliamo utilizzare il default.

Se cerco il minore passerò come nth iteratore quello all'inizio della sequenza.

Vediamo un esempio:

#include<iostream>
#include<algorithm>
#include<deque>
#include<functional> // greater<>
#include<algo.h>

using namespace std;

void dump(const deque<int>& v) {
    deque<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    deque<int> d(15);

    cout << "Initializing:" << endl;
    iota(d.begin(), d.end(), 1);
    random_shuffle(d.begin(), d.end());
    dump(d);

    deque<int>::iterator nth = d.begin();
    nth_element(d.begin(), nth, d.end());
    cout << "Smallest element at the begin:" << (*nth) << endl;
    dump(d);

    nth_element(d.begin(), nth, d.end(), greater<int>());
    cout << "Greatest element at the begin:" << (*nth) << endl;
    dump(d);

    nth = d.end();
    --nth; // now points to the last element
    nth_element(d.begin(), nth, d.end());
    cout << "Greatest element at the end:" << (*nth) << endl;
    dump(d);

    nth = d.begin() + d.size() / 2;
    nth_element(d.begin(), nth, d.end());
    cout << "Median value :" << (*nth) << endl;
    dump(d);
}

In una deque faccio in modo di avere una serie di elementi rimescolati. Con la prima chiamata a nth_element() faccio in modo che in prima posizione ci sia l'elemento minore. La seconda chiamata usa come comparatore l'operatore "greater than", così in prima posizione ora viene messo l'elemento maggiore. Nel terzo caso specifichiamo che vogliamo vedere l'ultimo elemento secondo l'ordinamento standard, quindi troviamo in ultima posizione il maggiore. Infine cerchiamo il valore mediano, passando come nth iteratore quello che punta all'elemento centrale della sequenza.

STL - sort

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

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.1: sort e stable_sort

L'algoritmo sort() ordina gli elementi compresi tra i due iteratori passati. Può essere utilizzato solo da container che hanno iteratori ad accesso casuale, come vector e deque.

Per l'ordinamento di list é dunque necessario usare la funzione membro list::sort().

L'algoritmo non é stabile, dunque se ci sono due o più elementi che dal punto di vista del comparatore sono uguali, non é detto che mantangano la posizione relativa iniziale. Nel caso peggiore le prestazioni di questo algoritmo possono degaradare, si può ricorrere a stable_sort() se questo può essere un problema. Sono resi disponibili due versioni di sort(), una usa l'operatore '<', l'altra permette di usare una funzione o un functor Compare.

Nell'esempio vediamo l'uso di sort e stable_sort nei due casi:

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

using namespace std;

void dump(const vector<double>& v) {
    vector<double>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

bool integerLess(double x, double y) {
    return long(x) < long(y);
}

int main() {
    vector<double> v(20);

    srand(time(NULL));
    for (size_t i = 0; i < v.size(); ++i) {
        v[i] = (rand() % 3 + 1) + double((rand() % 100 + 1) / 1000.0);
    }
    random_shuffle(v.begin(), v.end());

    cout << "Original sequence" << endl;
    dump(v);

    vector<double> unstable = v;
    vector<double> stable = v;

    cout << endl << "Sorting using the standard operator less" << endl;

    // sorting with < operator:
    stable_sort(stable.begin(), stable.end());
    cout << "Stable sorting:" << endl;
    dump(stable);

    sort(unstable.begin(), unstable.end());
    cout << "Unstable sorting:" << endl;
    dump(unstable);

    cout << endl << "Sorting with custom comparator" << endl;

    unstable = v;
    stable = v;

    stable_sort(stable.begin(), stable.end(), integerLess);
    cout << "stable sorting (integer key):" << endl;
    dump(stable);

    sort(unstable.begin(), unstable.end(), integerLess);
    cout << "unstable sorting (integer key):\n";
    dump(unstable);
}

Inizializziamo l'array con valori decimali casuali in modo che in molti condividano la stessa parte intera.

Quando usiamo l'operatore '<' non c'é differenza nel risultato nell'uso di sort e stable_sort, ma usando la nostra funzione integerLess, che compara i valori interi, notiamo che solo la stable_sort permetta di mantenere la posizione relativa tra gli elementi dopo l'ordinamento.

STL - partition

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

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

5.4.13: partition e stable_partition

Usando partition() possiamo dividere una sequenza in due parti, in accordo con il predicato che passiamo alla funzione.

La funzione standard non garantisce che l'ordine interno alla sequenza sia mantenuto, in cambio risulta essere generalmente più efficiente.

La variante stable_partition() mantiene l'ordinamento interno, a patto di un aggravio prestazionale.

L'algoritmo ritorna un iteratore al primo elemento della seconda partizione.

Ecco un esempio:

#include<algorithm>
#include<vector>
#include<functional>
#include<algo.h>

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

bool isNegative(int value) {
    return value < 0;
}

class Comparator {
public:
    Comparator(int pivot) : _pivot(pivot) {
    }

    bool operator()(int value) {
        return value < _pivot;
    }
private:
    int _pivot;
};

int main() {
    vector<int> v(12);
    iota(v.begin(), v.end(), -6);
    random_shuffle(v.begin(), v.end());

    cout << "The original sequence :";
    dump(v); // –5 –1 3 2 –3 5 –4 –6 4 0 1 –2

    vector<int> unstable(v);
    vector<int> stable(v);
    vector<int>::const_iterator it;


    cout << "Partition into negative and non-negative elements" << endl;

    cout << "unstable partition :";
    it = partition(unstable.begin(), unstable.end(), isNegative);
    dump(unstable); // –5 –1 –2 –6 –3 –4 5 2 4 0 1 3
    cout << "The second range starts at " << *it << endl;


    cout << "stable partition :";
    it = stable_partition(stable.begin(), stable.end(), Comparator(0));
    dump(stable); // –5 –1 –3 –4 –6 –2 3 2 5 4 0 1
    cout << "The second range starts at " << *it << endl;
}

Il vettore v, inizializzato con numeri da -6 a +5, viene rimescolato usando random_shuffle(). Lo copiamo in altri due vettori, unstable e stable.

Partizioniamo unstable usando come predicato la funzione isNegative, mentre stable usiamo il functor Comparator.

Nota che la partizione é tra numeri negativi e non negativi, lo zero, quindi, viene considerato come un elemento qualunque della seconda sezione.

Quadrato creativo

Dato n, numero intero positivo, il suo quadrato é uguale alla somma dei primi n numeri dispari.

Usare questa curiosa proprietà per calcolare il quadrato dei primi dieci interi positivi.

In pratica dobbiamo sommare i primi n elementi della progressione aritmetica di ragione 2 con primo termine 1.
Qualcosa come 1 + 3 + 5 + 7 + 9 + ....

Questa l'implementazione che mi é venuta naturale:

    for (int i = 1; i < 11; ++i) {
        int sum = 1;
        for (int j = 1; j < i; ++j) {
            sum += (j*2)+1;
        }

        cout << sum << ' ';
    }
    cout << endl;

L'idea é che il ciclo for esterno reinizializza la sommatoria a 1, il primo elemento della successione, e poi aggiunge gli elementi successivi che possono essere calcolati in funzione dell'indice j in modo immediato. Il primo elemento, 3, é infatti pensabile come 2 + 1, il secondo 2*2 + 1, il terzo 3*2 + 1, eccetera.

Ma, a pensarci un attimo, l'uso del doppio loop for é ridondante. Dopotutto per calcolare il risultato per n basta appoggiarsi a quello per n-1.

Il che porta a questa implementazione:

    vector<int> results;

    results.push_back(1);
    for (int i = 1; i < 10; ++i) {
        results.push_back(results[i-1] + (i*2)+1);
    }

    vector<int>::const_iterator it = results.begin();
    while(it != results.end())
        cout << *it++ << ' ';
    cout << endl;

Il primo elemento é uno, lo mettiamo nel vettore dei risultati. Gli altri li calcoliamo aggiungendo al precedente elemento il successivo numero dispari.

A pensarci meglio, però, nel caso generale l'uso di vector non é che sia una idea geniale. Nel caso corrente non ci sono problemi, dato che sappiamo il nostro vector non cresce più di tanto, ma se pensiamo ad un caso in cui si vogliano trovare i quadrati per centinaia, migliaia o anche più interi conviene usare deque.

Ecco qui la mia implementazione in questo caso:

    deque<int> d;

    d.push_back(1);
    for (int i = 1; i < 10; ++i) {
        d.push_back(d.back() + (i*2)+1);
    }

    deque<int>::const_iterator it = d.begin();
    while(it != d.end())
        cout << *it++ << ' ';
    cout << endl;

STL - random_shuffle

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

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

5.4.13: random_shuffle

Questo algoritmo permette di mescolare l'ordine degli elementi in una sequenza che fornisce accesso casuale ai suoi elementi, come vector o deque. Usa un suo generatore di numeri causali, o é possibile passagliene uno a nostra scelta.

Nell'esempio usiamo sia un nostro generatore, Rand, sia quello di default:

#include<algorithm>
#include<vector>
#include<algo.h>

using namespace std;

class Rand {
public:

    Rand(long int seed = 1) : r(seed) {
    }

    int operator()(int x) {
        r = (125 * r) % 8192;
        return int(double(r) / 8192.0 * x);
    }
private:
    long int r;
};

void dump(const vector& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    vector<int> v(12);
    iota(v.begin(), v.end(), 0);

    random_shuffle(v.begin(), v.end());
    dump(v);

    random_shuffle(v.begin(), v.end());
    dump(v);

    Rand aRand;
    random_shuffle(v.begin(), v.end(), aRand);
    dump(v);
}

STL - rotate

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

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

5.4.12: rotate e rotate_copy

L'algoritmo rotate() tratta una sequenza come fosse un anello e applica una trasformazione che consiste nello spostare l'elemento puntato dal secondo iteratore passato all'inizio della sequenza, come identificata dal primo iteratore passato, e facendo in modo che tutti gli altri elementi siano spostati di conseguenza, ottenendo l'effetto di una rotazione.

Nella variante _copy la sequenza iniziale non viene modificata e il risultato della rotazione viene posto a partire dal quarto iteratore passato alla funzione in avanti.

Segue esempio per rotate():

#include<algorithm>
#include<vector>
#include<algo.h>

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    vector<int> v(10);
    iota(v.begin(), v.end(), 0);

    cout << "Original sequence:" << endl;
    dump(v);

    for (size_t shift = 1; shift < 3; ++shift) {
        cout << "Rotation by " << shift << endl;
        for (int i = 0; i < v.size() / shift; ++i) {
            rotate(v.begin(), v.begin() + shift, v.end());
            dump(v);
        }
    }
}

STL - reverse

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

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

5.4.11: reverse

L'algoritmo unique() inverte gli elementi della sequenza passata: il primo diventa l'ultimo, il secondo il penultimo, e così via. É necessario che il container sottostante supporti l'uso di iteratori bidirezionali.

L'esempio é banale:

#include<iostream>
#include<algorithm>
#include<vector>
#include<algo.h>

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    vector<int> vi(10);
    iota(vi.begin(), vi.end(), 3);
    dump(vi);

    reverse(vi.begin(), vi.end());
    dump(vi);
}

STL - unique

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

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

5.4.10: unique e unique_copy

L'algoritmo unique() elimina tutti gli elementi identici consecutivi, tranne uno e ritorna il nuovo iteratore alla fine della sequenza.

É disponibile anche nelle variazioni _copy che permettono di creare una copia della sequenza altrove.

Come remove(), anche unique() non elimina gli elementi superflui in coda alla sequenza. Se necessario, occorre rimuoverli esplicitamente, come faccio alla fine dell'esempio che segue:

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

using namespace std;

int main() {
    vector<int> v(20);
    for (int i = 0; i < v.size(); ++i)
        v[i] = i / 3;

    ostream_iterator<int> output(cout, " ");
    copy(v.begin(), v.end(), output);
    cout << endl;

    vector<int>::iterator last = unique(v.begin(), v.end());
    copy(v.begin(), last, output);
    cout << endl;

    copy(v.begin(), v.end(), output);
    cout << endl;

    v.erase(last, v.end());
    copy(v.begin(), v.end(), output);
    cout << endl;
}

STL - remove e varianti

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

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

5.4.9: remove, remove_if, remove_copy, remove_copy_ir

L'algoritmo remove(), con la sua variazioni, rimuove tutti gli elementi da una sequenza che sono uguali a un dato valore, o che soddifano il predicato passato, e ritorna la fine della sequenza. Le variazione _copy permettono di specificare una diversa destinazione e ritornano un iteratore in scrittura alla successiva posizione.

É da notare che remove() non fa "tutto" il lavoro. Gli elementi sono eliminati, ma il contenitore non viene "ripulito" degli elementi in coda, che risultano perciò duplicati.

Occorre quindi utilizzare l'iteratore tornato da remove() come nuovo "end" della sequenza, e, se necessario, rimuovere gli elementi duplicati in coda alla sequenza:

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
#include<string>
#include<cstring>
#include<algo.h>

using namespace std;

bool isVowel(char c) {
   return strchr("aeiouAEIOU", c) != 0;
}

int main() {
   vector<char> v(26);
   iota(v.begin(), v.end(), 'a');

   ostream_iterator<char> output(cout, "");
   copy(v.begin(), v.end(), output);
   cout << endl;

   cout << "remove 't': " << endl;
   vector<char>::iterator last = remove(v.begin(), v.end(), 't');
   copy(v.begin(), last, output);
   cout << endl;

   last = remove_if(v.begin(), last, isVowel);
   cout << "only consonants left: " << endl;
   copy(v.begin(), last, output);
   cout << endl;

   cout << "complete sequence up to end() (tail is messed up): " << endl;
   copy(v.begin(), v.end(), output);
   cout << endl;

   v.erase(last, v.end());
   cout << "complete 'clean' sequence: " << endl;
   copy(v.begin(), v.end(), output);
   cout << endl;
}

Creo un vettore di caratteri, inizializzato con tutte le lettere dell'alfabeto inglese, dalla a alla z, usando la funzione iota(); chiamo remove() per eliminare tutte le occorrenze di 't' nell'array (evidentemente ce ne era una sola); da qui in posi uso l'iteratore ritornato, last, invece di end(); chiamo remove_if() passando la funzione isVowel() per rimuovere tutte le vocali; rimuovo la coda del vettore, da last a end(), per ottenere un vettore "pulito".

STL - generate

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

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

5.4.8: generate e generate_n

L'algoritmo generate(), con la sua variazione generate_n(), permette di inizializzare, interamente o parzialmente, una collezione usando una funzione o un functor.

Nell'esempio che segue usiamo il functor Random per generare numeri casuale e la funzione powerOfTwo() per generare iterativamente le potenze di due:

#include<iostream>
#include<cstdlib> // rand() and RAND_MAX
#include<algorithm>
#include<vector>

using namespace std;

void dump(const vector<int>& v) {
    vector<int>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

class Random {
public:

    Random(int b) : range(b) {
        srand ( time(NULL) );
    }

    int operator()() {
        return (int) ((double) rand() * range / (RAND_MAX + 1.0));
    }
private:
    int range;
};

int powerOfTwo() {
    static int value = 1;
    return (value *= 2) / 2;
}

int main() {
    vector<int> v(12);

    generate(v.begin(), v.end(), Random(1000));
    dump(v);

    vector<int>::const_iterator it = generate_n(v.begin(), 10, powerOfTwo);
    dump(v); // 1 2 4 8 16 32 64 128 256 512 x y
    
    cout << "it in position = " << (it - v.begin())
            << ", *it = " << *it << endl;

}

STL - fill

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

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

5.4.7: fill e fill_n

L'algoritmo fill(), con la sua variazione fill_n(), permette di inizializzare, interamente o parzialmente, una collezione. L'iteratore ritornato da fill_n() punta al primo elemento successivo a quelli modificati:

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

using namespace std;

void dump(const vector<double>& v) {
    vector<double>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    vector<double> v(8);
    // initialize all values with 9.23
    fill(v.begin(), v.end(), 9.23);
    dump(v);

    vector<double>::const_iterator it = fill_n(v.begin(), 3, 1.01);
    dump(v);

    cout << "it is in position = " << (it - v.begin())
            << ", *it = " << *it << endl;
}

STL - replace e variazioni

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

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

5.4.6: replace, replace_if, replace_copy, replace_copy_if

L'algoritmo base di replace() sostituisce ogni occorrenza del valore specificato nell'intervallo passato con un nuovo valore indicato.

La variante replace_if() permette di delegare a un predicato la decisione se effettuare o meno la sostituzione.

Con replace_copy e replace_copy_if l'algoritmo viene generalizzato permettendo di specificare dove vogliamo che vengano copiati i valori dell'intervallo passato.

Nell'esempio che segue vediamo all'opera replace() e le sue varianti:

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

using namespace std;

void dump(vector<string>& v) {
    vector<string>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

// unary predicate as functor

class Citrus {
public:

    bool operator()(const std::string& a) {
        return a == "lemon" || a == "orange" || a == "lime";
    }
};

int main() {
    vector<string> basket(3), crate(3);
    basket[0] = "apple";
    basket[1] = "orange";
    basket[2] = "lemon";
    dump(basket); // apple orange lemon

    cout << "replace apple with quince:" << endl;
    replace(basket.begin(), basket.end(), string("apple"), string("quince"));
    dump(basket); // quince orange lemon

    cout << "replace_if citrus fruits with plums:" << endl;
    replace_if(basket.begin(), basket.end(), Citrus(), string("plum"));
    dump(basket); // quince plum plum

    cout << "replace_copy: plums with limes:" << endl;
    replace_copy(basket.begin(), basket.end(), crate.begin(),
            string("plum"), string("lime"));
    dump(crate); // quince lime lime

    cout << "replace_copy_if: citrus fruits with tomatoes:" << endl;
    replace_copy_if(crate.begin(), crate.end(), basket.begin(), Citrus(),
            string("tomato"));
    dump(basket); // quince tomato tomato
}

Il functor Citrus fa da predicato; replace() sostituisce nel basket apple con quince; replace_if() usa il predicato per sostituire gli agrumi nel basket con plum; replace_copy() copia gli elementi dal basket al crate, sostituendo plum con lime; replace_copy_if() copia gli elementi del crate nel basket, sostituendo gli agrumi con tomato.

STL - transform

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

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

5.4.5: transform

Se oltre a copiare elementi di un container vogliamo anche applicare dei cambiamenti, l'algoritmo da utilizzare é transform() che é disponibile in due variazioni, a seconda del fatto se vogliamo lavorare su uno o due elementi alla volta.

I parametri passati sono gli iteratori che delimitano la sequenza su cui lavorare e l'operazione, unaria o binaria, che vogliamo applicare sugli elementi stessi.

Nell'esempio che segue definiamo l'operazione unaria come funzione e la binaria come functor - poteva essere anche il contrario. Facciamo prima una modifica unaria "in place" e poi una binaria il cui output é mandato in un altro container.

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

using namespace std;

// unary operation as function
string toUppercase(string s) {
    for (size_t i = 0; i < s.length(); ++i)
        if (s[i] >= 'a' && s[i] <= 'z')
            s[i] -= 'a'-'A';
    return s;
}

// binary operation as functor
class Join {
public:

    string operator()(const string& a, const std::string& b) {
        return a + " and " + b;
    }
};

int main() {
    vector<string> gals(3), guys(3), couples(3);

    gals[0] = "Annabella";
    gals[1] = "Scheherazade";
    gals[2] = "Xaviera";
    guys[0] = "Bogey";
    guys[1] = "Amadeus";
    guys[2] = "Wladimir";

    // transformation in place
    transform(guys.begin(), guys.end(), guys.begin(), toUppercase);

    // copy and transform
    transform(gals.begin(), gals.end(), guys.begin(), couples.begin(), Join());

    vector<string>::const_iterator it = couples.begin();
    while(it != couples.end()) {
        cout << *it++ << endl;
    }
}

La prima chiamata a transform() modifica tutti gli elementi di guys usando la funzione toUppercase(), e mettendo il risultato ancora in guys, sempre a partire dal primo elemento - dunque la variazione viene fatta in place.

La seconda volta prendiamo in input tutti gli elementi di gals e guys, li modifichiamo usando il functor Join e mettiamo i risultati in couples.

STL - swap

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

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

5.4.4: swap, iter_swap e swap_ranges

Si tratta di algoritmi per scambiare elementi di container.

Lo swap scambia due elementi che possono essere nello stesso o in differenti container.

Lo iter_swap prende due iteratori che fanno riferimento allo stesso o a differenti container e scambia gli elementi associati.

Lo swap_ranges permette di scambiare due intervalli che possono essere nello in differenti o nello stesso container - in questo caso bisogna fare attenzione al fatto che gli intervalli non si sovrappongano.

Per vedere il risultato dello swap sul vettore uso questa funzioncina d'appoggio:

void dump(vector& v) {
    vector::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

Questo il resto del codice d'esempio:

#include<algorithm>
#include<algo.h>
#include<vector>

using namespace std;

int main() {
    vector<int> v(15);
    iota(v.begin(), v.end(), 10);
    dump(v);

    cout << "Swap elements v[3] and v[5]:\n";
    swap(v[3], v[5]); // swap
    dump(v);

    cout << "swap first and last elements via iterator:" << endl;
    vector<int>::iterator first = v.begin();
    vector<int>::iterator last = v.end();
    --last;
    iter_swap(first, last); // swap
    dump(v);

    int third = v.size() / 3;
    cout << "swap head and tail " << "(" << third << " positions):" << endl;
    vector<int>::iterator middle1 = v.begin();
    advance(middle1, third); // end of first third
    vector<int>::iterator middle2 = v.end();
    advance(middle2, -third); // beginning of second third
    swap_ranges(first, middle1, middle2); // swap

    dump(v);
}

Inizializzo il vettore usando la solita iota. Faccio un primo swap, passando due elementi dell'array per reference. Poi un secondo swap, passando l'iteratore che punta al primo e all'ultimo (valido) elemento dell'array.

Infine faccio uno swap di intervallo, scambiando il primo terzo del vettore con l'ultimo.

STL - copy e copy_backward

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

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

5.4.2: copy e copy_backward

Questo algoritmo copia elementi da un intervallo ad una destinazione. La destinazione può essere l'inizio o la termine (nel caso di copy_backward) della copia. É un algoritmo che va usato con cautela, infatti c'é il rischio di sovrapposizione tra input e output, cosa che può causare risultati indefiniti.

Nell'esempio inizializziamo un vettore usando iota, poi lo copiamo in un altro vettore.

Più interessante il secondo utilizzo di copy, che copia il vettore in un ostream_iterator diretto verso cout e con l'uso di un asterisco come separatore. In pratica la copia risulta essere un dump del vettore sulla console.

Segue infine una backward_copy con sovrapposizione (benigna) dell'intervallo di input con quello di output.

#include<algorithm>
#include<vector>
#include<iterator>
#include<algo.h>

using namespace std;

int main() {
    vector<int> v1(7), v2(7, 0);
    iota(v1.begin(), v1.end(), 0);

    vector<int>::const_iterator it = v2.begin();
    while(it != v2.end()) {
        cout << *it++;
    }
    cout << endl;

    copy(v1.begin(), v1.end(), v2.begin());
    it = v2.begin();
    while(it != v2.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;

    // copy v1 to cout, separator *
    ostream_iterator<int> output(cout, "*");
    copy(v1.begin(), v1.end(), output); // 0*1*2*3*4*5*6*
    cout << endl;

    // overlapping ranges:
    vector<int>::iterator last = v1.begin();
    advance(last, 4); // 4 steps forward
    copy_backward(v1.begin(), last, v1.end());

    copy(v1.begin(), v1.end(), output); // 0*1*2*0*1*2*3*
    cout << endl;
}

STL - iota

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

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

5.4.1: iota

Non é un algoritmo incluso nello standard C++, ma spesso viene reso disponibile. Nel mio caso cygwin lo mette a disposizione includendo l'header algo.h; il suo scopo é quello di inizializzare la sequenza passatagli con valori crescenti, a partire dal valore passato come terzo parametro.

Nell'esempio qui sotto un vettore viene inizializzato a partire dal valore 3 (seguono 4, 5, ...):

#include<algo.h>
#include<vector>
#include<iostream>

using namespace std;

int main() {

    vector<int> v(5);
    for(size_t i = 0; i < v.size(); ++i)
        cout << v[i] << ' ';
    cout << endl;

    iota(v.begin(), v.end(), 3);

    for(size_t i = 0; i < v.size(); ++i)
        cout << v[i] << ' ';
    cout << endl;
}

STL - search

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.

5.3.9: search

L'algoritmo search cerca una sequenza di dimensione N per vedere se contiene una seconda sequenza di dimensione G.

Ritorna un iteratore al punto in cui inizia la seconda sequenza all'interno della prima, o end().

Nell'esempio che segue creiamo due vettori di interi tali che il secondo sia una sottosequenza del primo.

La search, evidentemente, avrà successo e ritornerà l'iteratore che punta al primo elemento della sottosequenza all'interno del primo vettore.

Cambiamo ora segno alla sottosequenza e ripetiamo la ricerca utilizzando come predicato usando il functor AbsIntCompare che ritorna true in caso di uguaglianza dei valori passati in termini assoluti. Otterremo lo stesso risultato del passaggio precedente.

Naturalmente quando chiamiamo search senza passare il predicato per la sottosequenza negativizzata la search fallisce, ovvero ritorna l'iteratore end() del primo vettore.

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

using namespace std;

class AbsIntCompare { // ignore signs
public:

    bool operator()(int x, int y) {
        return abs(x) == abs(y);
    }
};

int main() {
    vector<int> v1(12);
    for (size_t i = 0; i < v1.size(); ++i)
        v1[i] = i; // 0 1 2 3 4 5 6 7 8 9 10 11 12
    vector<int> v2(4);
    for (size_t i = 0; i < v2.size(); ++i)
        v2[i] = i + 5; // 5 6 7 8

    vector<int>::const_iterator where;

    cout << "Search for substructure v2 in v1: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (where != v1.end()) {
        cout << "v2 starts at position " << (where - v1.begin()) << endl;
    }

    // change signs
    for (size_t i = 0; i < v2.size(); ++i)
        v2[i] *= -1; // –5 –6 –7 –8

    cout << "Search for substructure v2 in v1, ignoring signs: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end(), AbsIntCompare());
    if (where != v1.end()) {
        cout << "v2 starts at position " << (where - v1.begin()) << endl;
    }

    // can't find the negative sequence with the standard search
    cout << "Search for substructure v2 in v1: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (where == v1.end()) {
        cout << "can't find v2." << endl;
    }
}

STL - equal

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.

5.3.8: equal

confronta due container, con una variante che usa un predicato binario. É quindi molto simile a mismatch con la differenza fodnamentale che ritorna un booleano, sappiamo solo se le due sequenze sono uguali o no, ma non dov'é la prima differenza.

A seguire l'esempio visto per mismatch, riscritto per equal:

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

using namespace std;

int main() {
    vector<int> v(8);
    for (size_t i = 0; i < v.size(); ++i)
        v[i] = 2 * i; // sorted sequence
    set<int> s(v.begin(), v.end()); // initialize set with v

    if (equal(v.begin(), v.end(), s.begin()))
        cout << "No mismatch found." << endl;

    ++v[3]; // insert mismatch

    // comparison for match with iterator pair ’where’
    if (equal(v.begin(), v.end(), s.begin()) == false) {
        cout << "Mismatching sequences detected." << endl;
    }
}

STL - mismatch

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.

5.3.7: mismatch

confronta due container, con una variante che usa un predicato binario.

Come esempio creo un vettore di otto interi, inizializzati con i primi numeri pari. Copio gli elementi in un set di interi, usando il costruttore di set che accetta in input gli iteratori che delimitano i valori che voglio copiare.

Definisco un pair il cui primo elemento é un iteratore a un vettore di interi e il secondo un iteratore a un set di interi.

La funzione mismatch() ritornerà, per l'appunto, un pair di questo tipo, dato che gli passiamo gli iteratori di quel tipo.

Dato che le due sequenze sono identiche per costruzione, ci aspettiamo che il risultato della chiamata a mismatch() sia che non si sono trovate differenze, ovvero, il primo elemento del pair sarà uguale all'iteratore end() del vettore.

Modifichiamo un elemento del vettore e ripetiamo la chiamata a mismatch(). Ora ci aspettiamo di trovare una differenza, e questa sarà segnalata dal fatto che il primo elemento del pair sarà un iteratore diverso dall'end() del vettore, e in particolare punterà alla diffenza.

Ecco il codice:

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

using namespace std;

int main() {
    vector<int> v(8);
    for (size_t i = 0; i < v.size(); ++i)
        v[i] = 2 * i; // sorted sequence
    set<int> s(v.begin(), v.end()); // initialize set with v

    pair<vector<int>::iterator, set<int>::iterator> where;

    where = mismatch(v.begin(), v.end(), s.begin());
    if (where.first == v.end())
        cout << "No mismatch found." << endl;

    ++v[3]; // insert mismatch

    // comparison for match with iterator pair ’where’
    where = mismatch(v.begin(), v.end(), s.begin());
    if (where.first != v.end()) {
        cout << "First mismatch (" << *where.first << " != "
            << *where.second << ") found at position "
            << (where.first - v.begin()) << "." << endl;
    }
}