Esercizio - Predicati e algoritmi STL (primo appello 2022-23, teoria)

Domanda aperta 3 del primo appello 2022-23 del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: STL - algoritmi, predicati e lambdaLa STL ha circa 80 algoritmi generici (header e ) che lavorano su sequenze [first, last) di qualunque contenitore tramite iteratori: find/find_if, count/count_if, sort, copy/copy_if/unique_copy, merge, equal_range, equal, accumulate, inner_product. find cerca un valore e restituisce l'iteratore alla prima occorrenza o end(); find_if verifica un predicato (funzione che restituisce bool) passato come puntatore a funzione, function object (classe con operator()) o lambda expression. Una variabile globale per passare la soglia al predicato è da evitare; il function object la memorizza in un dato membro. Una lambda cattura -> tipo { corpo } definisce la funzione sul posto e può catturare le variabili locali per valore ([=], [x]) o per riferimento ([&], [&x]). sort(b, e) ordina con < e sort(b, e, cmp) con un criterio, solo su iteratori random access; copy richiede spazio a destinazione.STL - algoritmi, predicati e lambda →, STL - sequenze, iteratori e container (vector, list, string)La STL (Standard Template Library) fornisce contenitori (vector, list, map, ...) e algoritmi generici (sort, find, accumulate, ...) tenuti insieme da una interfaccia unificata: la sequenza, un intervallo [begin, end) di elementi gestito tramite iteratori (oggetti che identificano un elemento: * dereferenzia, ++ avanza, == e != confrontano; end è il primo elemento dopo l'ultimo, quindi una sequenza vuota ha begin == end). Gli algoritmi conoscono solo gli iteratori e i contenitori espongono solo iteratori, così i due mondi sono disaccoppiati e cambiare contenitore non cambia l'algoritmo. Un iteratore di lista è una classe annidata con un puntatore al nodo; auto deduce il tipo dell'iteratore. vector (contiguo, [] e at(), insert/erase costosi e che invalidano gli iteratori), string (un vector di char con + e +=), list (nodi concatenati, insert/erase senza spostare gli altri elementi, niente []) e char[] (array C: dimensione fissa, niente iteratori, == confronta i puntatori) a confronto.STL - sequenze, iteratori e container (vector, list, string) →. Il problema di programmazione del primo appello 2021-22 usa un predicato di ordinamento: Esercizio - Ordinare le parole di un file con sort e lambda (primo appello 2021-22, programmazione).

Testo. Illustrare il concetto di predicato e fornire un esempio in C++. Spiegare in che modo un predicato può essere usato in un algoritmo STL, corredando la spiegazione con un esempio di codice.

Il predicato

Predicato. Una funzione (o un oggetto chiamabile) che restituisce true o false e che esprime un criterio su un elemento (o su due, nel caso dei criteri di ordinamento). Esempio: bool odd(int x) { return x % 2; } (dispari). Gli algoritmi STL generici lo ricevono come argomento: il cosa (la ricerca) è nell'algoritmo, il criterio nel predicato.

Un predicato può essere espresso in tre modi:

Perché non una variabile globale per la soglia? Funziona, ma è modificabile ovunque, non c'è incapsulamento, il codice è fragile: il function object e la lambda risolvono il problema.

Uso in un algoritmo STL

Gli algoritmi con predicato sono, tra gli altri: find_if(b, e, p) (primo elemento per cui p(x) è vero, oppure e), count_if(b, e, p) (quanti), copy_if(b, e, b2, p) (copia quelli per cui è vero), sort(b, e, cmp) (ordina secondo cmp(a, b): "a viene prima di b"). find_if internamente fa

while (first != last && !pred(*first)) ++first;     // pred(*first) e' una chiamata a funzione o a operator()
return first;

Il predicato è passato per copia (un function object piccolo è copiato: va bene; se grande, per riferimento) e find_if lo chiama con ogni elemento. Funziona con qualsiasi container (vector, list) e tipo di elemento, perché l'interfaccia è fatta di iteratori.

#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;

// PREDICATO: una funzione che restituisce true o false
bool odd(int x) { return x % 2; }

// Predicato con un parametro (la soglia): function object, cioe' una classe con operator()
class Larger_than {
public:
    explicit Larger_than(int vv) : v{vv} {}                // salva la soglia nel dato membro
    bool operator()(int x) const { return x > v; }         // il predicato vero e proprio
private:
    int v;
};

int main()
{
    vector<int> v {4, 8, 15, 16, 23, 42};
    list<double> l {1.5, 31.0, 40.5, 12.25};

    // 1) puntatore a funzione: si passa il NOME della funzione, senza ()
    auto p = find_if(v.begin(), v.end(), odd);
    cout << "primo dispari: " << (p != v.end() ? to_string(*p) : "nessuno") << '\n';

    // 2) function object: la soglia viaggia nell'oggetto
    auto q = find_if(l.begin(), l.end(), Larger_than(31));
    cout << "primo > 31: " << (q != l.end() ? to_string(*q) : "nessuno") << '\n';

    // 3) lambda: il predicato e' scritto nel punto d'uso e cattura la soglia
    int soglia = 15;
    auto r = find_if(v.begin(), v.end(), [soglia](int x) { return x > soglia; });
    cout << "primo > " << soglia << ": " << *r << '\n';

    // lo stesso predicato in altri algoritmi
    cout << "quanti dispari: " << count_if(v.begin(), v.end(), odd) << '\n';
    vector<int> grandi(v.size());
    auto fine = copy_if(v.begin(), v.end(), grandi.begin(), Larger_than(15));   // copia solo quelli per cui e' vero
    grandi.erase(fine, grandi.end());
    cout << "copiati > 15:";
    for (int x : grandi) cout << ' ' << x;
    cout << '\n';
    return 0;
}

primo dispari: 15
primo > 31: 40.500000
primo > 15: 16
quanti dispari: 2
copiati > 15: 16 23 42

• find_if(v.begin(), v.end(), odd) $\to$ primo dispari di {4, 8, 15, 16, 23, 42}: 15.
• find_if(l.begin(), l.end(), Larger_than(31)) su una list<double> $\to$ 40.5 (31.0 non è maggiore di 31): lo stesso algoritmo su un altro container, con un function object.
• find_if con la lambda [soglia](int x) { return x > soglia; } $\to$ 16.
• count_if(..., odd) $\to$ 2 (15 e 23); copy_if con Larger_than(15) $\to$ 16 23 42; grandi.erase(fine, grandi.end()) toglie le posizioni non scritte.
• Efficienza: un function object piccolo con operator() inline può essere più efficiente di una chiamata a funzione.