STL - search

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

Sezione dedicata agli algoritmi che non modificano le sequenze su cui operano.

5.3.9: search

L'algoritmo search cerca una sequenza di dimensione N per vedere se contiene una seconda sequenza di dimensione G.

Ritorna un iteratore al punto in cui inizia la seconda sequenza all'interno della prima, o end().

Nell'esempio che segue creiamo due vettori di interi tali che il secondo sia una sottosequenza del primo.

La search, evidentemente, avrà successo e ritornerà l'iteratore che punta al primo elemento della sottosequenza all'interno del primo vettore.

Cambiamo ora segno alla sottosequenza e ripetiamo la ricerca utilizzando come predicato usando il functor AbsIntCompare che ritorna true in caso di uguaglianza dei valori passati in termini assoluti. Otterremo lo stesso risultato del passaggio precedente.

Naturalmente quando chiamiamo search senza passare il predicato per la sottosequenza negativizzata la search fallisce, ovvero ritorna l'iteratore end() del primo vettore.

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

using namespace std;

class AbsIntCompare { // ignore signs
public:

    bool operator()(int x, int y) {
        return abs(x) == abs(y);
    }
};

int main() {
    vector<int> v1(12);
    for (size_t i = 0; i < v1.size(); ++i)
        v1[i] = i; // 0 1 2 3 4 5 6 7 8 9 10 11 12
    vector<int> v2(4);
    for (size_t i = 0; i < v2.size(); ++i)
        v2[i] = i + 5; // 5 6 7 8

    vector<int>::const_iterator where;

    cout << "Search for substructure v2 in v1: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (where != v1.end()) {
        cout << "v2 starts at position " << (where - v1.begin()) << endl;
    }

    // change signs
    for (size_t i = 0; i < v2.size(); ++i)
        v2[i] *= -1; // –5 –6 –7 –8

    cout << "Search for substructure v2 in v1, ignoring signs: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end(), AbsIntCompare());
    if (where != v1.end()) {
        cout << "v2 starts at position " << (where - v1.begin()) << endl;
    }

    // can't find the negative sequence with the standard search
    cout << "Search for substructure v2 in v1: ";
    where = search(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (where == v1.end()) {
        cout << "can't find v2." << endl;
    }
}