STL - inplace_merge

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

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

5.5.4: inplace_merge

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

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

Ad esempio:

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

using namespace std;

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

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