Esercizio - Aritmetica dei puntatori (quarto appello 2022-23, teoria)

Domanda aperta 3 del quarto appello 2022-23 del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. È la stessa domanda del primo appello 2021-22 (Esercizio - Aritmetica dei puntatori (primo appello 2021-22, teoria)), svolta con altri esempi; il concetto e la tabella degli operatori sono lì. Teoria: C++ - puntatori, array e castun puntatore è una variabile che contiene un indirizzo di memoria e sa il tipo dell'oggetto puntato (T*); si ottiene l'indirizzo con & e si accede al dato con * (dereference, un lvalue), nullptr indica nessun oggetto e due puntatori a tipi diversi sono tipi diversi; void* è un puntatore a memoria grezza (accetta qualsiasi puntatore ma non si dereferenzia) e i cast (static_cast, reinterpret_cast, const_cast) servono per interfacciarsi con hardware e codice non modificabile; il puntatore, a differenza della reference, si può spostare, può essere nullptr e va dereferenziato, e assegnarlo copia l'indirizzo (shallow copy) mentre assegnare una reference copia l'oggetto; un array C è una sequenza contigua di elementi dello stesso tipo, con dimensione costante, senza controllo dei limiti, che passato a una funzione decade in un puntatore al primo elemento; l'aritmetica dei puntatori somma o sottrae interi spostando di n elementi (non di n byte) e la differenza fra puntatori è in elementi; gli errori classici sono nullptr, puntatori non inizializzati, accessi fuori dai limiti e puntatori a oggetti usciti dallo scope.C++ - puntatori, array e cast →.

Testo. Introdurre l'aritmetica dei puntatori illustrando: a) il concetto alla base dell'aritmetica; b) con quali operatori e operandi funziona; c) due esempi di funzionamento, ciascuno corredato da codice che deve essere commentato mediante descrizione e/o grafici.

a) Il concetto

Un puntatore T* contiene un indirizzo e porta con sé il tipo T dell'oggetto puntato, quindi sizeof(T). L'aritmetica dei puntatori usa questa informazione: sommare un intero $n$ a un puntatore lo sposta di $n$ elementi ("slot"), cioè di $n \times \mathtt{sizeof}(T)$ byte. Funziona perché gli array hanno gli elementi contigui: dato l'indirizzo del primo, ogni altro elemento si raggiunge sommando l'indice, e p[i] equivale a *(p + i). Lo spostamento in byte dipende dal tipo: + 1 su un int* è 4 byte, su un double* è 8.

b) Operatori e operandi

• puntatore + intero, intero + puntatore, puntatore - intero: danno un puntatore spostato (+=, -=, ++, -- sono le forme composte);
• puntatore - puntatore (stesso tipo, stesso array): dà un intero con segno pari al numero di elementi compresi fra i due, non di byte;
• confronti ==, !=, <, > fra puntatori dello stesso array;
• non si sommano due puntatori, né si moltiplicano o dividono;
• è lecito restare dentro l'array, più la posizione "uno dopo l'ultimo" (non dereferenziabile): fuori è comportamento indefinito.

c) Due esempi (e un terzo)

#include <iostream>
using namespace std;

// Lunghezza di una stringa C con l'aritmetica dei puntatori: si avanza finche' non si trova '\0'
int lunghezza(const char* s)
{
    const char* p = s;
    while (*p != '\0') ++p;
    return static_cast<int>(p - s);                   // differenza fra puntatori = numero di ELEMENTI (char)
}

// Inverte un array scambiando gli estremi con DUE puntatori che si avvicinano
void inverti(int* inizio, int* fine)                  // [inizio, fine): fine e' "uno dopo l'ultimo"
{
    --fine;                                           // ora punta all'ultimo elemento
    while (inizio < fine) {                           // confronto fra puntatori dello stesso array
        int t = *inizio;
        *inizio = *fine;
        *fine = t;
        ++inizio;
        --fine;
    }
}

int main()
{
    // ESEMPIO 1: lunghezza di una stringa e differenza fra puntatori
    const char* s = "Beorn";
    cout << "lunghezza(\"Beorn\") = " << lunghezza(s) << '\n';

    // ESEMPIO 2: inversione di un array con due puntatori
    int v[6] = {1, 2, 3, 4, 5, 6};
    inverti(v, v + 6);                                // v + 6 = uno dopo l'ultimo
    for (int x : v) cout << x << ' ';
    cout << '\n';

    // ESEMPIO 3: matrice 2x3 memorizzata per righe: l'elemento (r, c) sta a m + r*3 + c
    int m[2][3] = {{10, 11, 12}, {20, 21, 22}};
    int* base = &m[0][0];
    cout << "elemento (1, 2) = " << *(base + 1 * 3 + 2) << ", distanza (1,0)-(0,0) = "
         << &m[1][0] - &m[0][0] << " elementi\n";
    return 0;
}

lunghezza("Beorn") = 5
6 5 4 3 2 1 
elemento (1, 2) = 22, distanza (1,0)-(0,0) = 3 elementi

Esempio 1: lunghezza di una stringa C. lunghezza(const char* s) parte da p = s e avanza con ++p finché *p non è il terminatore '\0'. A quel punto p - s è la differenza fra due puntatori: il numero di caratteri (char occupa 1 byte, ma la differenza è comunque in elementi). Per "Beorn": p si ferma sul sesto carattere (lo \0), $p - s = 5$.

s -> 'B'  'e'  'o'  'r'  'n'  '\0'
      ^                        ^
      s                        p (dopo 5 incrementi)      p - s = 5

Esempio 2: inversione di un array con due puntatori. inverti(v, v + 6): inizio punta a v[0] e fine a v + 6, uno dopo l'ultimo; si fa --fine per puntare all'ultimo elemento; finché inizio < fine (confronto fra puntatori) si scambiano i due valori e si avvicinano i puntatori (++inizio, --fine). Risultato: 6 5 4 3 2 1.

passo 0:  1  2  3  4  5  6          inizio -> 1, fine -> 6
passo 1:  6  2  3  4  5  1          scambia, poi inizio -> 2, fine -> 5
passo 2:  6  5  3  4  2  1          scambia, poi inizio -> 3, fine -> 4
passo 3:  6  5  4  3  2  1          scambia, poi inizio == fine + 1: si ferma (inizio > fine)

Esempio 3 (in più): matrice in memoria. Una matrice int m[2][3] è memorizzata per righe in un unico blocco contiguo: l'elemento $(r, c)$ sta a base + r*3 + c. Con base = &m[0][0], *(base + 1*3 + 2) è m[1][2] = 22; la differenza &m[1][0] - &m[0][0] vale 3 elementi (una riga). È la stessa formula che il compilatore usa per m[r][c].