Vai al contenuto
Topos Uranos
Italiano

Array

Riepilogo

Finora ogni dato del corso ha vissuto nella propria variabile, con il proprio nome; ma molti dati dello stesso tipo, come le temperature di una settimana, non si possono scorrere con un ciclo se ciascuno ha un nome diverso. Questa lezione presenta la prima struttura dati del corso, la sequenza indicizzata: elementi dello stesso tipo, in posizioni contigue della memoria, numerate a partire da zero. Nel C++ moderno si scrive con std::array, la cui dimensione resta fissata in compilazione. Si studiano la sua dichiarazione, il tipo std::size_t degli indici e le due scansioni, con indice e con il for basato su intervallo. Si stabilisce la regola che governa tutta l’unità: un indice è valido se è compreso tra 0 e la dimensione meno uno, e in ogni accesso di un ciclo questa validità si giustifica con l’invariante. Si mostra che cosa accade quando non è rispettata, cioè comportamento indefinito, e si confronta [] con l’accesso controllato .at(). Infine si presentano gli array C, per leggere il codice altrui.

Obiettivi di apprendimento

  1. Dichiarare, inizializzare e scorrere uno std::array con indici e con il for basato su intervallo.
  2. Giustificare, mediante l’invariante del ciclo, che un indice è entro i limiti in ogni accesso.
  3. Distinguere l’accesso con [], che lo standard non controlla, dall’accesso con .at(), che è sempre controllato, e spiegare quando conviene ciascuno.
  4. Leggere codice con array C e spiegarne gli svantaggi rispetto a std::array.

La sequenza indicizzata

Molti dati, un solo nome

Per calcolare la media delle temperature di una settimana con quanto insegnato finora servirebbero sette variabili, monday, tuesday e così via fino a sunday, e una somma di sette termini. Con quelle di un anno sarebbero 365, e nessun ciclo potrebbe scorrerle, perché nel corpo di un ciclo il nome di una variabile è sempre lo stesso. Ciò che manca è un nome per l’insieme e un numero per ciascun elemento, in modo che il numero possa essere una variabile che il ciclo fa avanzare.

Una sequenza indicizzata è esattamente questo: un insieme di nn elementi dello stesso tipo, memorizzati uno dopo l’altro in celle contigue della memoria, e designati dalla loro posizione, detta indice. La matematica conosce l’oggetto: una successione finita (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), in cui aia_i designa l’elemento di posto ii, oppure un vettore, come quelli del corso Algebra e Geometria I. In C++ si scrive a[i], e l’indice può essere qualsiasi espressione intera: 2, i, i + 1.

Perché da zero

In C++, come nella maggior parte dei linguaggi attuali, il primo elemento ha indice 0, e l’ultimo indice n−1n - 1. La ragione non è una convenzione capricciosa, ma il modo in cui si trova un elemento: se la sequenza comincia a un certo indirizzo di memoria e ogni elemento occupa ss byte, l’elemento di indice ii si trova all’indirizzo iniziale più i⋅si \cdot s. L’indice è, dunque, un offset (scostamento): il numero di elementi che bisogna saltare a partire dal primo. Il primo è a zero salti da sé stesso.

Ne segue la definizione che governa tutta questa unità: in una sequenza di nn elementi, un indice ii è valido se e solo se 0≤i<n0 \leq i < n. La disuguaglianza di destra è stretta, ed è la fonte dell’errore più frequente con le sequenze, l’errore di uno: scrivere i≤ni \leq n dove si doveva scrivere i<ni < n, o cominciare da 1 dove si doveva cominciare da 0. Un indice uguale a nn non designa l’ultimo elemento, ma la cella che segue la sequenza, che non le appartiene.