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.