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.