Esercizio - Spostare i valori di una list in un array dinamico senza delete (quarto appello 2021-22, programmazione)

Esame

Prova di programmazione (60 minuti) del quarto appello 2021-22 (12 settembre 2022) del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: C++ - smart pointer, STL - sequenze, iteratori e container (vector, list, string), C++ - eccezioni e gestione delle risorse (RAII). Una variante con std::array e copia è nel terzo appello 2022-23: Esercizio - Copiare da array a array dinamico senza delete (terzo appello 2022-23, programmazione).

Testo. Progettare un programma che: 1. crei una standard list di valori interi e la popoli usando 20 valori a piacere; 2. allochi dinamicamente un array stile C di dimensione 20; 3. scorra tale lista e sposti nell'array i valori inferiori a una soglia costante definita opportunamente; 4. esca senza usare esplicitamente delete/delete[] nel codice dell'esercizio e senza causare memory leak.

Ragionamento

Lista: std::list<int> inizializzata con la lista di 20 valori ({83, 12, ...}).
Array dinamico senza delete: il vincolo 4 dice di usare RAII. L'array è new int[20], quindi la responsabilità di liberarlo va a un oggetto con distruttore: std::unique_ptr<int[]> (la specializzazione per array chiama delete[] da sola; senza [] nel tipo, unique_ptr<int> farebbe una delete sbagliata sull'array). L'alternativa make_unique<int[]>(20) è equivalente e più sicura. Un std::vector<int> sarebbe ancora più semplice, ma il testo vuole un array stile C allocato dinamicamente.
"Sposti": i valori vanno tolti dalla lista e messi nell'array: si copia *it in arr[usati++] e si cancella l'elemento dalla lista con erase.
Attenzione all'iteratore: erase(it) invalida it e restituisce l'iteratore all'elemento successivo. Quindi il ciclo non incrementa nel for ma dentro: it = lista.erase(it) se si è spostato, ++it altrimenti. (Con list, erase invalida solo l'iteratore dell'elemento cancellato; con vector invaliderebbe tutti quelli successivi.)
Quanti elementi: non si sa in anticipo quanti valori siano sotto soglia (da 0 a 20): un contatore usati tiene il numero di elementi validi dell'array; l'array ha sempre 20 posti, e al massimo se ne usano 20, quindi non c'è overflow.
Uscita: lista e arr sono oggetti locali: i loro distruttori liberano tutto; nessuna delete nel codice.

list_to_array.cppcpp

#include <iostream>
#include <list>
#include <memory>
using namespace std;

int main()
{
    constexpr int kN = 20;                          // numero di valori
    constexpr int kSoglia = 50;                     // soglia costante

    // 1. lista di 20 interi "a piacere"
    list<int> lista {83, 12, 47, 95, 3, 60, 28, 71, 50, 19, 66, 5, 90, 34, 77, 41, 8, 58, 25, 99};

    // 2. array C di dimensione 20 allocato dinamicamente, gestito da uno unique_ptr<int[]>:
    //    il suo distruttore fa delete[] da solo, quindi nel codice non compare nessuna delete
    unique_ptr<int[]> arr(new int[kN]);
    int usati = 0;                                  // quanti elementi dell'array sono stati scritti

    // 3. si scorre la lista e si SPOSTANO nell'array i valori inferiori alla soglia
    for (auto it = lista.begin(); it != lista.end(); ) {
        if (*it < kSoglia) {
            arr[usati++] = *it;                     // copiato nell'array...
            it = lista.erase(it);                   // ...e tolto dalla lista (erase restituisce l'iteratore successivo)
        }
        else
            ++it;
    }

    cout << "nell'array (" << usati << " valori < " << kSoglia << "):";
    for (int i = 0; i < usati; ++i) cout << ' ' << arr[i];
    cout << "\nnella lista (" << lista.size() << " valori >= " << kSoglia << "):";
    for (int x : lista) cout << ' ' << x;
    cout << '\n';
    // 4. si esce: lista e arr sono oggetti con distruttore, quindi liberano la memoria da soli
    return 0;
}

nell'array (10 valori < 50): 12 47 3 28 19 5 34 41 8 25
nella lista (10 valori >= 50): 83 95 60 71 50 66 90 77 58 99

Controllo dell'uscita: i valori sotto 50 (12, 47, 3, 28, 19, 5, 34, 41, 8, 25) sono finiti nell'array nell'ordine di scorrimento (dieci); i dieci rimasti nella lista (83, 95, 60, 71, 50, 66, 90, 77, 58, 99) sono quelli $\ge 50$ (il $50$ resta: la condizione è strettamente minore).

Versione ripasso

Passi: list<int> con 20 valori; array C dinamico di 20 int gestito da unique_ptr<int[]> (RAII: libera con delete[] da solo, nessuna delete nel codice); scorrere la lista e spostare i valori $<$ soglia (copia in arr[usati++] + erase dalla lista); uscire.
Iteratore: erase(it) invalida it e restituisce il successivo: it = lista.erase(it) se si sposta, ++it altrimenti (l'incremento sta nel corpo, non nel for).

cpp

constexpr int kN = 20, kSoglia = 50;
list<int> lista {83, 12, 47, 95, 3, 60, 28, 71, 50, 19, 66, 5, 90, 34, 77, 41, 8, 58, 25, 99};
unique_ptr<int[]> arr(new int[kN]);
int usati = 0;
for (auto it = lista.begin(); it != lista.end(); ) {
    if (*it < kSoglia) { arr[usati++] = *it; it = lista.erase(it); }
    else ++it;
}

Uscita: array con 10 valori $<50$ (12 47 3 28 19 5 34 41 8 25); lista con 10 valori $\ge 50$ (83 95 60 71 50 66 90 77 58 99).
Errori tipici: unique_ptr<int> al posto di unique_ptr<int[]> (delete sull'array); erase dentro un for con ++it (iteratore invalidato); non contare gli elementi usati; new int[20] con delete[] esplicito (vietato dal testo); soglia nel ciclo come numero magico.

Esercizio - Spostare i valori di una list in un array dinamico senza delete (quarto appello 2021-22, programmazione)

Ragionamento

Esercizi su questo argomento

Teoria collegata