Alan M. Turing: 2010

Tante teste per Tom

Tom, rapito da uno scienziato pazzo, si risveglia legato ad una sedia in una stanza completamente oscura.

Gli viene detto che sul tavolo di fronte a lui ci sono cento monete, dieci di queste mostrano la testa, le altre novanta croce.

Per aver salva la vita deve dividere le cento monete in due gruppi, tale che il numero di teste sia uguale.

Gli viene slegato un braccio, in modo da poter riorganizzare a suo piacimento le monete, e gli viene lasciato solo un minuto di tempo, poi verrà accesa la luce e si verificherà il risultato.

Come procedere?

Inutile pensare di contare sul senso del tatto e cercare di distinguere teste da croci, Tom non ha questa capacità e, in ogni caso, il poco tempo a disposizione lo sconsiglia.

Se si potesse solo muovere le monete, senza girarle, Tom sarebbe probabilmente spacciato. Ma c'è una scappatoia: non gli è stato vietato di cambiare la proporzione tra teste e croci.

Dunque è possibile girare le monete. Il problema è che, data l'oscurità, non è possibile sapere che faccia mostrava prima la moneta che giriamo, e nemmeno che faccia ha assunto.

Tom potrebbe magari pensare a varianti creative (tipo ingoiare tutte e cento le monete e dire di averle partizionate in due gruppi di zero monete, ognuno dei quali ha zero teste) ma difficilmente queste soddisferebbero il suo rapitore.

Le cento monete devono restare sul tavolo e, quando la luce verrà accesa, dovranno essere divise in due gruppi che mostrano lo stesso numero di teste.

Notiamo che non ci viene chiesto di dividere le monete in gruppi uguali, e ci viene da pensare che anche questo sia un indizio interessante.

Proviamo a semplificare il problema: diciamo che sulle cento monete ce ne sia solo una che mostra testa e pensiamo di creare un gruppo contenente una sola moneta, lasciandone 99 dall'altra parte. Consideriamo la nostra moneta singola. Se fosse testa, dall'altra parte devono essere tutte croci; se fosse croce, dall'altra parte c'é una testa. Dunque mi basta girarla per ottenere la soluzione. Se era l'unica testa, adesso è croce, e ho diviso i due gruppi in modo che hanno entrambi zero teste; se era croce, adesso è testa, e i due gruppi hanno entrambi una testa.

Se ci fossero due teste, dividerei la popolazione in due gruppi con 2 e 98 monete, e girerei entrambe le monete del primo gruppo. E così via fino ad arrivare alla soluzione per il problema come enunciato.

In pochi secondi, Tom isola dieci monete e le volta. E, qualunque ora sia il numero di teste sul tavolo, lui salva la propria.

Roulette russa

In genere la roulette russa si fa in due, usando un revolver. Si mette uno o più proiettili nel tamburo, lo si fa girare, si punta l'arma alla propria testa e si tira il grilletto.

Si itera finché qualcuno non trova un proiettile.

Consideriamo un revolver che abbia spazio per 6 proiettili, e per il quale ogni foro del tamburo abbia la stessa probabilità di finire in linea con il grilletto, a prescindere dal numero di proiettili che inseriamo.

Il problema è questo: due persone si affrontano alla roulette, il primo è sopravvissuto e, prima di passare l'arma al secondo, gli chiede se vuole girare il tamburo o preferisce tirare direttamente.

Cosa deve fare il secondo per avere le migliori probabilità di non spararsi?

Si analizzi il caso per un proiettile; due proiettili contigui; due proiettili non contigui.

Si tratta di puro calcolo delle probabilità.

Vediamo il primo caso: un unico proiettile nel tamburo.

Se faccio girare il tamburo, ho una probabilità su sei (0,167 circa) di trovare il proiettile.

Se il mio avversario ha appena superato la prova, ho una informazione aggiuntiva: nella camera di scoppio, quando ha tirato il grilletto, non c'era un proiettile. Dunque ora ho una possibilità di trovare un proiettile su cinque (0,2), e non più sei.

Dunque mi conviene far girare il tamburo.

Secondo caso: due proiettili contigui.

Se faccio girare il tamburo, ho due probabilità su sei (0,333) di trovare un proiettile.

Il mio avversario è ancora vivo, dunque non ha trovato il proiettile. Ma allora posso escludere che il grilletto sia sul secondo dei due proiettili contigui (dato che al mio avversario non è capitato il primo) e su uno dei fori non utilizzati (quello che è capitato al mio avversario). Ho dunque 4 possibili posizioni, di cui una occupata da un proiettile, ovvero una possibilità su quattro (0,25) di trovare un proiettile.

Mi conviene non far girare il tamburo.

Terzo caso: due proiettili non contigui.

Se faccio girare il tamburo, come nel caso precedente, ho due probabilità su sei (0,333) di trovare un proiettile.

Uso l'informazione che nel turno precedente il grilletto non era su uno dei due proiettili. Dunque ora è in una tra le quattro posizioni seguenti ai quattro fori non utilizzati. Due di queste sono occupate dai due proiettili, due sono libere. Due probabilità su quattro (0,5) di finire male.

Perciò faccio girare il tamburo.

Grandi attese per un piccolo incremento

Abbiamo ricevuto l'incarico di scrivere una funzione in C++ che deve rispettare le seguenti specifiche:

input: un vettore di interi positivi
output: un long

Il long in output deve essere generato in modo tale che sia pari al valore più elevato ottenibile come produttoria dei valori passati in input, considerando che possiamo incrementare di una unità uno e un solo elemento dell'array.

Ad esempio, se in input ci viene passato {4,3,2} dobbiamo scegliere se tornare (4+1)*3*2 = 30, 4*(3+1)*2 = 32, o 4*3*(2+1) = 36.

Intermezzo fornito da Belle & Sebastian.

In pratica il requisito può essere tradotto come una richiesta di identificare il minore tra i valori passati, incrementarlo, e ritornare la produttoria. Per autoconvincerci di questo fatto pensiamo ad un caso limite, in cui l'input è composto da {1, 100}. Aggiungendo 1 al primo elemento otteniamo il raddoppio del suo valore, e quindi dell'intera produttoria. Se aggiungessimo 1 al secondo, quel valore crescerebbe solo di un centesimo.

Una prima idea potrebbe essere quella di ordinare in modo crescente il vettore, incrementare il primo elemento, eseguire la produttoria sul vettore modificato:


#include <vector>
#include <algorithm>

long prodPlus1(vector<int> input) // 1.
{
    sort(input.begin(), input.end());
    ++input[0];

    long res = 1;
    for_each(input.begin(), input.end(), [&res] (int i) {res *= i;}); // 2.
    return res;
}

1. Dato che dobbiamo comunque creare una copia del vettore, tanto vale farla implicitamente nell'intestazione della funzione
2. Con for_each scandiamo l'intero vettore, e la funzione lambda si occupa di mettere il risultato della produttoria nella variabile locale res, che poi torneremo al chiamante.

Non è malaccio, come codice. Soprattutto dà una certa soddisfazione scrivere la riga col for_each e la funzione lambda. Ma lascia un po' l'amaro in bocca la copia e il sorting del vettore, entrambe operazioni non necessarie. Infatti, in realtà, a noi interessa trovare e modificare solo un elemento, tutto il resto potremmo risparmiarcelo.

Invece di sort, usiamo allora min_element(), e poi spezziamo il for_each() in due parti, tenendo l'iteratore all'elemento minore del vettore come separatore tra i due tronconi.

Il codice risultante potrebbe dunque essere questo:


#include <vector>
#include <algorithm>

long prodPlus2(const vector<int>& input)
{
    vector<int>::const_iterator it = min_element(input.begin(), input.end());

    long res = (*it) + 1;
    for_each(input.begin(), it, [&res] (int i) {res *= i;});
    for_each(it+1, input.end(), [&res] (int i) {res *= i;});
    return res;
}

Singleton

Appunti presi durante la lettura di Modern C++ Design: Generic Programming and Design Patterns Applied, di Andrei Alexandrescu.

Dal capitolo sei: Implementazione dei singleton.

Il pattern Singleton è semplice nella descrizione ma presenta alcune difficoltà non irrilevanti nella sua implementazione.

In pratica un singleton è una variabile globale migliorata, nel senso che non è possibile creare più di un oggetto di quel determinato tipo.

In genere le difficoltà vengono nel gestire il ciclo di vita di un singleton. È relativamente semplice controllarne la creazione, può diventare un incubo controllarne la distruzione.

Il singleton di Meyers

L'idea del singleton di Meyers è quella lasciare al compilatore l'onere di gestire il ciclo di vita dell'oggetto. Per far questo lo si definisce come variabile statica locale alla funzione che ne ritorna l'istanza. In questo modo l'oggetto viene effettivamente creato al momento del primo utilizzo e deallocato al termine dell'esecuzione del programma.

A seguire, un esempio che dovrebbe chiarire l'idea:


#include <iostream>

using namespace std;

class MeyersSingleton
{
public:
  static MeyersSingleton& getInstance();
  void doSomething();
private:
  MeyersSingleton();
  MeyersSingleton(const MeyersSingleton&); // not implemented
  MeyersSingleton& operator=(const MeyersSingleton&); // not implemented
  ~MeyersSingleton();
};

MeyersSingleton& MeyersSingleton::getInstance()
{
  static MeyersSingleton obj;
  return obj;
}

MeyersSingleton::MeyersSingleton()
{
  cout << "MeyersSingleton ctor" << endl;
}

MeyersSingleton::~MeyersSingleton()
{
  cout << "MeyersSingleton dtor" << endl;
}

void MeyersSingleton::doSomething()
{
  cout << "MeyersSingleton doSomething" << endl;
}

void tech60() {
  cout << "get singleton I" << endl;
  MeyersSingleton& ms = MeyersSingleton::getInstance();
  ms.doSomething();

  cout << "get singleton II" << endl;
  MeyersSingleton& ms2 = MeyersSingleton::getInstance();
  ms2.doSomething();

  cout << "done testing singleton" << endl;
}

Una soluzione semplice ed elegante.

Le cose si complicano se vogliamo un maggiore controllo sul ciclo di vita del singleton, dato che bisogna gestire il problema della possibile morte dell'oggetto quando in realtà ne sarebbe ancora richiesto l'uso da qualche altra componente dell'applicazione. Un altra complicazione nasce dal fatto che il singleton potrebbe far uso di qualche risorsa che potrebbe non essere liberata propriamente al termine dell'applicazione. Il metodo indicato dall'Alexandrescu si basa sull'uso della funzione atexit(), che permette di registrare una funzione per l'esecuzione nella fase terminale del programma.

E una ulteriore complicazione ce la dà la gestione dei singleton in ambiente multithreading. In realtà, se seguiamo l'idea di Meyers possiamo non occuparci del problema, dato che lo deleghiamo al compilatore. Sarà lui a doversi fare carico di gestire possibili condizioni di racing al momento dell'effettiva generazione dell'oggetto. Ma se, per un motivo o per un altro, decidiamo di usare lo schema standard per la creazione di un singleton, mettendo l'oggetto creato nello heap, dobbiamo curare questo passaggio con attenzione.

La soluzione indicata da Alexandrescu è quella del pattern del lock con doppio controllo (double-checked locking pattern), con l'avvertenza di aggiungere un ulteriore controllo per verificare che l'hardware su cui gira la nostra applicazione lo supporti (ci consiglia di fare attenzione soprattutto in caso di ambienti multiprocessore simmetrico che implementino il cosiddetto modello di memoria rilassato).

In pratica usiamo un mutex, un lock, e controlliamo due volte che l'istanza dell'oggetto non sia stata creata. Lo scopo del doppio controllo è quello di evitare di utilizzare il lock appena sia possibile, dato che si tratta del collo di bottiglia prestazionale della vicenda.

Usando boost questa è la parte del codice rilevante:


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

using namespace std;

namespace {
  boost::mutex mtx;
}

class MultithreadedSingleton
{
public:
  static MultithreadedSingleton& getInstance();
  void doSomething();
private:
  MultithreadedSingleton();
  MultithreadedSingleton(const MultithreadedSingleton&); // not implemented
  MultithreadedSingleton& operator=(const MultithreadedSingleton&); // not implemented
  ~MultithreadedSingleton();

  static MultithreadedSingleton* pInstance_;
};

MultithreadedSingleton* MultithreadedSingleton::pInstance_ = 0;

MultithreadedSingleton& MultithreadedSingleton::getInstance()
{
  if (pInstance_ == 0)
  {
    boost::mutex::scoped_lock lock(mtx);
    if (pInstance_ == 0)
    {
      pInstance_ = new MultithreadedSingleton;
    }
  }

  return *pInstance_;
}

// ...

Static check

Appunti presi durante la lettura di Modern C++ Design: Generic Programming and Design Patterns Applied, di Andrei Alexandrescu.

Dal secondo capitolo: Tecniche

Asserzioni durante la compilazione.

Un problema nell'uso dei template in C++ è come assicurare la correttezza del codice. Diciamo di aver scritto una funzione template che rende più sicura la reinterpret_cast aggiungendo un asserzione:


template 
To safe_reinterpret_cast(From from)
{
assert(sizeof(From) <= sizeof(To));  return reinterpret_cast(from);
}

Ora prima di eseguire una reinterpret_cast si verifica che il tipo in output sia di dimensione tale da non causare una perdita di byte significativi.

E' sicuramente un passo in avanti rispetto a una reinterpret_cast senza controllo ma sarebbe ancora meglio se potessimo fare il controllo in fase di compilazione e non esecuzione.

Per far questo ci viene in aiuto una macro, pensata da Van Horn che funziona bene anche in C usando il fatto che un array di dimensione zero è illegale:


#define STATIC_CHECK(expr) { char unnamed[(expr) ? 1 : 0]; }

Se l'espressione expr è "vera" la macro genera un array legale, altrimenti uno illegale, e quindi un errore in fase di compilazione.

Riscriviamo la funzione template in questo modo:


template 
To checked_reinterpret_cast(From from)
{
STATIC_CHECK(sizeof(From) <= sizeof(To));  return reinterpret_cast(from);
}

Resta il problema della messaggistica generata. Usando STATIC_CHECK, in caso di errore abbiamo una segnalazione sulla dimensione zero dell'array, che non è in realtà molto pertinente con il nostro reale errore. L'Alexandrescu mostra una ingegnosa soluzione che ci permette di generare un messaggio significativo ma che, purtroppo, non è supportato da tutti i compilatori - ad esempio non da quello che sto usando correntemente.

Per cui mi accontento di STATIC_CHECK.

Usare boost::function e boost::bind

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

Parte sull'uso di function, nel capitolo undicesimo, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

Abbiamo visto che il punto debole di boost::function è proprio nella connessione a funzioni membro e in una certa rigidità nel gestire i parametri alla funzione sottostante. In questo ci viene in aiuto boost::bind.

Vediamo un esempio nell'ambito in cui boost::function entra alla perfezione, la gestione di callback.

Una prima implementazione non fa uso delle librerie boost, ma usa il pattern command per gestire le callback. La classe TapeRecorder mette a disposizione alcune funzionalità che definiscono una sorta di simulatore di registratore vocale. La classe CommandBase definisce l'interfaccia dei comandi che possono essere richiamati dalla GUI, da questa derivano le classi *Command che vengono usate dalla GUI per creare una connessione tra la presentazione e la logica business dell'applicazione:


#include <iostream>

using namespace std;

class TapeRecorder {
public:
void play() {
  cout << "Since my baby left me..." << endl;
}

void stop() {
  cout << "OK, taking a break" << endl;
}

void forward() {
  cout << "whizzz" << endl;
}

void rewind() {
  cout << "zzzihw" << endl;
}

void record(const string& sound) {
  cout << "Recorded: " << sound << endl;
}
};

class CommandBase {
public:
virtual bool enabled() const =0;
virtual void execute() =0;

virtual ~CommandBase() {}
};

class PlayCommand : public CommandBase {
TapeRecorder* p_;
public:
PlayCommand(TapeRecorder* p) : p_(p) {}

bool enabled() const {
  return true;
}

void execute() {
  p_->play();
}
};

class StopCommand : public CommandBase {
TapeRecorder* p_;
public:
StopCommand(TapeRecorder* p) : p_(p) {}

bool enabled() const {
  return true;
}

void execute() {
  p_->stop();
}
};

void function05() {
TapeRecorder tr;

cout << "Using the command pattern" << endl;
CommandBase* pPlay= new PlayCommand(&tr);
CommandBase* pStop= new StopCommand(&tr);

cout << "Pressing button play" << endl;
pPlay->execute();
cout << "Pressing button stop" << endl;
pStop->execute();

delete pPlay;
delete pStop;
}

Il difetto fondamentale di questa implementazione è la sua verbosità. Invece di una classe per ogni comando, potremmo lasciare che la classe command abbia al suo interno un puntatore a funzione generico che, inizializzato dal costruttore, si faccia carico di gestire la connessione verso la corretta funzionalità.

Rivediamo il codice:


// ...

class TapeRecorderCommand : public CommandBase {
void (TapeRecorder::*func_)();
TapeRecorder* p_;
public:

TapeRecorderCommand(
  TapeRecorder* p,
  void (TapeRecorder::*func)()) : p_(p), func_(func) {}

bool enabled() const {
  return true;
}

void execute() {
  (p_->*func_)();
}
};

void function05() {
TapeRecorder tr;

//...

cout << "Using the improved command" << endl;
pPlay = new TapeRecorderCommand(&tr, &TapeRecorder::play);
pStop = new TapeRecorderCommand(&tr, &TapeRecorder::stop);

cout << "Pressing button play" << endl;
pPlay->execute();
cout << "Pressing button stop" << endl;
pStop->execute();

delete pPlay;
delete pStop;
}

Invece di usare un puntatore a funzione, usiamo boost::function, che, in combinazione con boost::bind, ci permette una maggiore elasticità:


// ...
#include "boost/function.hpp"
#include "boost/bind.hpp"

// ...

class Command2 {
boost::function<void()> f_;
public:
Command2() {}
Command2(boost::function<void()> f) : f_(f) {}

void execute() {
  if (f_) {
    f_();
  }
}

template <typename Func> void setFunction(Func f) {
  f_ = f;
}

bool enabled() const {
  return f_;
}
};

void function05() {
TapeRecorder tr;

// ...

cout << endl << "Using boost::function and boost::bind" << endl;

Command2 play(boost::bind(&TapeRecorder::play,&tr));
Command2 stop(boost::bind(&TapeRecorder::stop,&tr));
Command2 forward(boost::bind(&TapeRecorder::stop,&tr));
Command2 rewind(boost::bind(&TapeRecorder::rewind,&tr));
Command2 record;

cout << "Pressing button play" << endl;
if (play.enabled()) {
  play.execute();
}

cout << "Pressing button stop" << endl;
stop.execute();

cout << "Pressing button record" << endl;
string s = "What a beautiful morning...";
record.setFunction(boost::bind(&TapeRecorder::record, &tr, s));
record.execute();
}

Ma ci rendiamo conto che la classe Command2 non è altro che una replica delle funzionalità già offerte da boost::function. Possiamo a questo punto farne a meno, riducendo la definizione della classe ad una typedef:


typedef boost::function<void()> Command3;

void function05() {
TapeRecorder tr;

// ...

cout << endl << "Fully using boost::function" << endl;
Command3 play3(boost::bind(&TapeRecorder::play, &tr));
Command3 stop3(boost::bind(&TapeRecorder::stop, &tr));
Command3 forward3(boost::bind(&TapeRecorder::stop, &tr));
Command3 rewind3(boost::bind(&TapeRecorder::rewind, &tr));

cout << "Pressing button play" << endl;
play3();

cout << "Pressing button stop" << endl;
stop3();

cout << "Pressing button record" << endl;
string s3 = "What a beautiful morning...";
Command3 record3(boost::bind(&TapeRecorder::record, &tr, s3));
record3();
}

Boost function per functor

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

Parte sull'uso di function, nel capitolo undicesimo, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

Quando passiamo un functor a boost::function, in realtà ne passiamo una copia. Questo vuol dire che usiamo diverse function queste lavoreranno su differenti copie del functor.

Se vogliamo che il functor sia passato per riferimento a function dobbiamo usare un apposito wrapper di boost, e si ottiene l'effetto chiamando la funzione ref (o cref, se vogliamo una const reference) sull'oggetto.

L'esempio che segue mostra l'uso di default, con i functor copiati, e l'uso con reference, in modo che vi sia in realtà un unico functor condiviso:


#include <iostream>
#include "boost/function.hpp"

using namespace std;

class KeepingState {
  int total_;
public:
  KeepingState() : total_(0) {}

  int operator()(int i) {
    total_ += i;
    return total_;
  }

  int total() const {
    return total_;
  }
};

void function04() {
  KeepingState ks;
  boost::function<int(int)> f1;
  f1 = ks;

  boost::function<int(int)> f2;
  f2 = ks;

  cout << "Default: functor copied" << endl;
  cout << "The current total is " << f1(10) << endl;
  cout << "The current total is " << f2(10) << endl;
  cout << "The total is " << ks.total() << endl;

  cout << "Forcing functor by reference" << endl;
  f1 = boost::ref(ks);
  f2 = boost::ref(ks);

  cout << "The current total is " << f1(10) << endl;
  cout << "The current total is " << f2(10) << endl;
  cout << "The total is " << ks.total() << endl;
}

Boost function per membri di classe

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

Parte sull'uso di function, nel capitolo undicesimo, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

É possibile usare boost:function anche per funzioni che sono membro di una classe, anche se l'uso non é così elegante come ci si potrebbe aspettare.

Nell'esempio a seguire vediamo come fare in modo che l'oggetto di riferimento sia passato a function per valore, riferimento o puntatore:


#include <iostream>
#include "boost/function.hpp"

using namespace std;

class AClass {
public:
  void doStuff(int i) const {
    cout << "Stuff done: " << i << endl;
  }
};

void function03() {
  cout << "Class function by value" << endl;
  boost::function<void(AClass, int)> f1;
  f1 = &AClass::doStuff;
  f1(AClass(), 1);

  cout << "Class function by reference" << endl;
  boost::function<void(AClass&, int)> f2;
  f2 = &AClass::doStuff;
  AClass ac2;
  f2(ac2, 2);

  cout << "Class function by pointer" << endl;
  boost::function<void(AClass*, int)> f3;
  f3 = &AClass::doStuff;
  AClass ac3;
  f3(&ac3, 3);
}

Boost function

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

Parte sull'uso di function, nel capitolo undicesimo, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

Con boost::function si semplifica la gestione dei puntatori a funzione, permettendo di usare per lo stesso scopo anche functor e qualunque oggetto che si comporti come una funzione.


#include <iostream>
#include "boost/function.hpp"

using namespace std;

bool check(int i, double d) {
  return i > d;
}

void function01() {
  boost::function<bool (int, double)> f = ✓

  if(f(10, 1.1))
    cout << "Function works as expected" << endl;
}

Callback

Una tipica situazione in cui boost::function ci viene in aiuto, e quando vogliamo gestire dei callback. Nell'esempio che segue confrontiamo l'uso normale, con puntatori a funzione nella classi Notifier, con quello di boost::function, in Notifier2.

A parte la definizione del tipo che parametrizza il vettore, il codice non cambia. Il comportamento é lo stesso, ma usando boost::function ci guadagnamo in genericità. Infatti, oltre a puntatori a funzione, possiamo anche utilizzare functor per fare la nostra callback.


#include <iostream>
#include <vector>

#include "boost/function.hpp"

using namespace std;

void printNewValue(int i) {
  cout << "The value has been updated and is now " << i << endl;
}

void changeObserver(int i) {
  cout << "Ah, the value has changed!" << endl;
}

class PrintPreviousValue {
  int lastValue_;
public:
  PrintPreviousValue() : lastValue_(-1) {}

  void operator()(int i) {
    cout << "Previous value was " << lastValue_ << endl;
    lastValue_ = i;
  }
};

class Notifier {
  typedef void (*FunType)(int);
  vector<FunType> vec_;
  int value_;
public:
  void addObserver(FunType t) {
    vec_.push_back(t);
  }

  void changeValue(int i) {
    value_ = i;
    for (size_t i=0; i < vec_.size(); ++i) {
      vec_[i](value_);
    }
  }
};

class Notifier2 {
  typedef boost::function<void(int)> FunType;
  vector<FunType> vec_;
  int value_;
public:
  void addObserver(FunType t) {
    vec_.push_back(t);
  }

  void changeValue(int i) {
    value_ = i;
    for (size_t i = 0; i < vec_.size(); ++i) {
      vec_[i](value_);
    }
  }
};

void function02() {
  Notifier n;
  n.addObserver(&printNewValue);
  n.addObserver(&changeObserver);

  n.changeValue(42);

  cout << "Using boost::function" << endl;
  Notifier2 n2;
  n2.addObserver(&printNewValue);
  n2.addObserver(&changeObserver);
  n2.addObserver(PrintPreviousValue());

  n2.changeValue(42);
  n2.changeValue(39);
}

Composizione funzionale con boost::bind

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

Parte sull'uso di bind, nel capitolo nove, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

Il problema sembra semplice: vogliamo selezionare elementi che siano all'interno di un certo intervallo, tipo (5, 10].
Normalmente risolviamo questa richiesta con codice tipo questo:


if(i>5 && i<=10) {
  // ...
}

Più complicato risulta l'applicazione di questa condizione nel processare un container. L'uso di boost::bind, in connessione con le operazioni della libreria standard C++, ci aiuta ad ottenere una soluzione relativamente semplice.

Dobbiamo in pratica fare un and logico su due confronti, ottenendo questo codice:


boost::bind(std::logical_and(),
  boost::bind(std::greater(), _1, 5),
  boost::bind(std::less_equal(), _1, 10));

Vediamo un esempio che verifica questo costrutto. Mettiamo in un vettore alcuni valori, poi usiamo count_if per contare quanti elementi del vettore rispettano la nostra condizione e find_if per trovare il primo elemento che le rispetta:


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

#include "boost/bind.hpp"

using namespace std;

void bind04() {
  vector<int> v;

  v.push_back(7);
  v.push_back(4);
  v.push_back(12);
  v.push_back(10);

  int count = count_if(v.begin(), v.end(),
    boost::bind(logical_and<bool>(),
      boost::bind(greater<int>(), _1, 5),
      boost::bind(less_equal<int>(), _1, 10)));
  cout << "Found " << count << " items" << endl;

  vector<int>::iterator it = find_if(v.begin(), v.end(),
    boost::bind(logical_and<bool>(),
      boost::bind(greater<int>(),_1,5),
      boost::bind(less_equal<int>(),_1,10)));

  if (it != v.end()) {
    cout << "First item: " << *it << endl;
  }
}

Un altro possibile uso é quello di applicare diverse operazioni su ogni singolo elemento di un container.

Nell'esempio che segue vogliamo aggiungere 10 a tutti gli elementi e quindi togliere il 5% dal valore risultante. Abbiamo quindi un binding composto che, notiamo, parte dall'operazione più interna.


#include <iostream>
#include <list>
#include <functional>
#include <algorithm>

#include "boost/bind.hpp"

using namespace std;

void bind05() {
  list<double> values;
  values.push_back(10.0);
  values.push_back(100.0);
  values.push_back(1000.0);

  transform(values.begin(), values.end(), values.begin(),
    boost::bind(multiplies<double>(), 0.95, 
      boost::bind(plus<double>(), _1, 10)));

  copy(values.begin(), values.end(), ostream_iterator<double>(cout," "));
  cout << endl;
}

Criteri di ordinamento dinamico via Boost bind

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

Parte sull'uso di bind, nel capitolo nove, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

Un utilizzo di boost::bind é in connessione con l'uso di sort su di un container. Infatti permette di creare sul posto una regola per l'ordinamento del container.

Nell'esempio che segue vediamo come ordinare un vettore di oggetti di una classe che non é fornita di operatori di ordinamento:


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

#include "boost/bind.hpp"

using namespace std;

class PersonalInfo {
  string name_;
  string surname_;
  unsigned int age_;

public:
  PersonalInfo(const string& n, const string& s, unsigned int age) : 
    name_(n), surname_(s), age_(age) {}

    string name() const {
      return name_;
    }

    string surname() const {
      return surname_;
    }

    unsigned int age() const {
      return age_;
    }
};

ostream& operator<< (ostream& os, const PersonalInfo& pi) {
  os << pi.name() << ' ' << pi.surname() << ' '
     << pi.age() << endl;
  return os;
}

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

void bind03() {
  vector<PersonalInfo> vec;
  vec.push_back(PersonalInfo("Little", "John", 30));
  vec.push_back(PersonalInfo("Friar", "Tuck", 50));
  vec.push_back(PersonalInfo("Robin", "Hood", 40));
  dump(vec);

  cout << "By age:" << endl;
  sort(vec.begin(), vec.end(), boost::bind(
    less<unsigned int>(),
    boost::bind(&PersonalInfo::age, _1),
    boost::bind(&PersonalInfo::age, _2)));
  dump(vec);

  cout << "By surname:" << endl;
  sort(vec.begin(), vec.end(), boost::bind(
    less<string>(),
    boost::bind(&PersonalInfo::surname, _1),
    boost::bind(&PersonalInfo::surname, _2)));
  dump(vec);
}

La prima sort viene eseguita usando la funzione age() e l'operatore less, il secondo con surname().

Ancora su boost::bind

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

Parte sull'uso di bind, nel capitolo nove, all'interno della terza parte, dedicata ai functor e alla programmazione di più alto ordine.

L'uso di boost::bind é estremamente flessibile. Nell'esempio che segue si vede come il confronto con std::mem_fun_ref la veda vincente.


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

#include "boost/bind.hpp"

using namespace std;

class status {
  string name_;
  bool ok_;
public:
  status(const string& name) : name_(name), ok_(true) {}

  void breakIt() {
    ok_=false;
  }

  bool isBroken() const {
    return ok_;
  }

  void report() const {
    cout << name_ << " is " << (ok_ ? "working" : "broken") << endl;
  }
};

void bind01() {
  vector<status> statuses;
  statuses.push_back(status("status 1"));
  statuses.push_back(status("status 2"));
  statuses.push_back(status("status 3"));
  statuses.push_back(status("status 4"));

  statuses[1].breakIt();
  statuses[2].breakIt();

  cout << "Using a classic for loop" << endl;
  for (vector<status>::iterator it = statuses.begin(); it != statuses.end(); ++it) {
    it->report();
  }

  cout << "Using for_each and mem_fun_ref" << endl;
  for_each(statuses.begin(), statuses.end(), mem_fun_ref(&status::report));

  cout << "Using for_each and boost::bind" << endl;
  for_each(statuses.begin(), statuses.end(), boost::bind(&status::report, _1));
}

Il bello di boost::bind é che funziona quando il parametro passato, identificato con il segnaposto _1, può essere un valore, un puntatore, o anche uno smart pointer. Usando le funzionalità offerte dalla libreria standard (in attesa della riscrittura 0x) occorre usare l'adattatore mem_fun_ref, mem_fun, o disperarsi per l'assenza di disponibilità per smart pointer.

Nell'esempio seguente vediamo come boost::bind lavori indifferentemente con funzioni libere o membri di classi. Bisogna solo fare attenzione ai parametri passati via segnaposto. Nel caso di funzioni membro non statiche, che richiedano quindi un "this" su cui operare, il primo segnaposto deve essere dedicato a un oggetto della classe a cui fare riferimento.


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

using namespace std;

class AClass {
public:
  void printString(const string& s) const {
    cout << "Member function: " << s << endl;
  }

  static void staticPrintString(const string& s) {
    cout << "Static member function: " << s << endl;
  }
};

void printString(const string& s) {
  cout << "Free function: " << s << endl;
}

void bind02() {
  boost::bind(&printString, _1)("Hello!"); // 1

  boost::bind(&AClass::staticPrintString, _1)("Hello!"); // 2

  AClass c;
  boost::bind(&AClass::printString, _1, _2)(c, "Hello!"); // 3

  boost::bind(&AClass::printString, AClass(), _1)("Hello!"); // 4

  boost::bind(&AClass::printString, AClass(), "Hello!")(); // 5
}

Nel primo esempio boost::bind invoca una funzione libera, passandole via il primo segnaposto, _1, una stringa. Nel secondo ad essere chiamata é una funzione statica, nel terzo una normale funzione membro, che ha bisogno di un "this" per operare, e che viene estratto dall'istanza di AClass che viene passata come _1.

Nel quarto esempio vediamo che é posibile passare esplicitamente a bind un'istanza della classe costruita al volo. In questo caso il primo segnaposto viene dedicato al parametro della funzione. Il quinto esempio permette di fare a meno dell'uso di ogni segnaposto, dato che bind prende in input il puntatore alla funzione, il puntatore a un oggetto della classe creato al volo e il parametro passato alla funzione.

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


#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


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