Esercizio - Ordinare le parole di un file con sort e lambda (primo appello 2021-22, programmazione)

Prova di programmazione (90 minuti, su carta) del primo appello 2021-22 (25 gennaio 2022) 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) →, Esercizio - Predicati e algoritmi STL (primo appello 2022-23, teoria).

Testo. Creare un programma che legge tutto il contenuto di un file di testo inserendo le singole parole in un contenitore standard appropriato. Successivamente, ordinare tale contenitore sfruttando l'algoritmo std::sort(), usando come criterio il numero di lettere di ciascuna parola e, a parità di numero di lettere, l'ordine alfabetico. Implementare tale criterio usando un function object o una lambda expression.

Scelte

1. Contenitore: std::vector<std::string>. Serve accesso casuale (richiesto da sort: iteratori random access, che std::list non ha) e si aggiungono elementi in coda con push_back. Una std::map o set ordinerebbero da sole, ma per chiave e senza duplicati: qui le parole ripetute si tengono e il criterio è personalizzato.

2. Lettura: is >> w estrae una "parola" alla volta, saltando spazi e a capo, e restituisce un valore falso alla fine del flusso: for (string w; is >> w; ) parole.push_back(w);. La funzione prende un istream&, quindi funziona con un file (ifstream), con cin o con una stringa in memoria.

3. Criterio: funzione di confronto strettamente "minore": a viene prima di b se ha meno lettere, oppure se ne ha lo stesso numero e a < b (ordine lessicografico fra string).

   $$a \prec b \iff |a| < |b| \;\; \text{oppure} \;\; (|a| = |b| \;\text{e}\; a < b)$$

   È un ordine totale stretto, come richiede sort.

4. Lambda: scritta direttamente come terzo argomento di sort; non cattura nulla ([]) e prende le stringhe per const& per non copiarle.

Programma

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

// Legge tutte le parole (separate da spazi) da un flusso. Si lavora su istream&:
// vale per un file, per cin e per una stringa in memoria.
vector<string> leggi_parole(istream& is)
{
    vector<string> parole;
    for (string w; is >> w; )             // >> si ferma agli spazi e restituisce falso alla fine del file
        parole.push_back(w);
    return parole;
}

int main(int argc, char* argv[])
{
    vector<string> parole;
    if (argc > 1) {
        ifstream file(argv[1]);           // il nome del file si passa dalla riga di comando
        if (!file) {
            cerr << "impossibile aprire " << argv[1] << '\n';
            return 1;
        }
        parole = leggi_parole(file);
    }
    else
        parole = leggi_parole(cin);       // senza argomenti, legge da tastiera / da pipe

    // criterio: prima il numero di lettere, a parita' ordine alfabetico
    sort(parole.begin(), parole.end(),
         [](const string& a, const string& b) {
             if (a.size() != b.size()) return a.size() < b.size();
             return a < b;
         });

    for (const string& w : parole) cout << w << '\n';
    return 0;
}

Con il file (o l'ingresso standard)

il gatto nero mangia la mela rossa e il cane beve
acqua con la zampa

si ottiene (una parola per riga):

e
il
il
la
la
con
beve
cane
mela
nero
acqua
gatto
rossa
zampa
mangia

Nell'uscita: e (1 lettera); poi il, il, la, la (2 lettere, alfabetico); poi con (3); beve, cane, mela, nero (4); acqua, gatto, rossa, zampa (5); mangia (6). Le parole ripetute (il, la) restano entrambe.

Il file si passa come argomento della riga di comando (./prog testo.txt); senza argomenti il programma legge da cin. Nell'ambiente di prova in WebAssembly non c'è <fstream>: l'esecuzione è avvenuta leggendo dall'ingresso standard, mentre il ramo con ifstream è stato solo compilato (per Linux).

Versione con function object

Lo stesso criterio come classe con operator():

struct PiuCorta {
    bool operator()(const std::string& a, const std::string& b) const
    {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    }
};
// sort(parole.begin(), parole.end(), PiuCorta());

La lambda è preferibile quando il criterio serve in un solo punto: resta accanto alla chiamata; il function object è più adatto se va riusato.