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.