C++
Array

introduzione

Dimensione array: digita sicuro al momento della compilazione.

#include <stddef.h>     // size_t, ptrdiff_t

//----------------------------------- Machinery:

using Size = ptrdiff_t;

template< class Item, size_t n >
constexpr auto n_items( Item (&)[n] ) noexcept
    -> Size
{ return n; }


//----------------------------------- Usage:

#include <iostream>
using namespace std;
auto main()
    -> int
{
    int const   a[]     = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    Size const  n       = n_items( a );
    int         b[n]    = {};       // An array of the same size as a.
    
    (void) b;
    cout << "Size = " << n << "\n";
}

L'idioma C per la dimensione dell'array, sizeof(a)/sizeof(a[0]) , accetta un puntatore come argomento e genererà quindi un risultato errato.

Per C ++ 11

usando C ++ 11 puoi fare:

std::extent<decltype(MyArray)>::value;

Esempio:

char MyArray[] = { 'X','o','c','e' };
const auto n = std::extent<decltype(MyArray)>::value;
std::cout << n << "\n"; // Prints 4

Fino a C ++ 17 (in uscita al momento della stesura di questo manuale) C ++ non aveva un linguaggio di base incorporato o un'utilità di libreria standard per ottenere la dimensione di un array, ma questo può essere implementato passando l'array per riferimento a un modello di funzione, come sopra riportati. Punto fine ma importante: il parametro size template è un size_t , in qualche modo incoerente con il tipo di risultato della funzione Size firmato, al fine di adattare il compilatore g ++ che a volte insiste su size_t per la corrispondenza dei template.

Con C ++ 17 e successivi si può invece usare std::size , che è specializzato per gli array.

Array raw di dimensioni dinamiche

// Example of raw dynamic size array. It's generally better to use std::vector.
#include <algorithm>            // std::sort
#include <iostream>
using namespace std;

auto int_from( istream& in ) -> int { int x; in >> x; return x; }

auto main()
    -> int
{
    cout << "Sorting n integers provided by you.\n";
    cout << "n? ";
    int const   n   = int_from( cin );
    int*        a   = new int[n];       // ← Allocation of array of n items.
    
    for( int i = 1; i <= n; ++i )
    {
        cout << "The #" << i << " number, please: ";
        a[i-1] = int_from( cin );
    }

    sort( a, a + n );
    for( int i = 0; i < n; ++i ) { cout << a[i] << ' '; }
    cout << '\n';
    
    delete[] a;
}

Un programma che dichiara un array T a[n]; dove n è determinato a run-time, può compilare con alcuni compilatori che supportano array di lunghezze variadici C99 (VLA) come estensione del linguaggio. Ma i VLA non sono supportati dal C ++ standard. Questo esempio mostra come allocare manualmente un array di dimensioni dinamiche tramite una new[] -expression,

int*        a   = new int[n];       // ← Allocation of array of n items.

... quindi usalo e infine deallocalo tramite una delete[] -expression:

delete[] a;

L'array allocato qui ha valori indeterminati, ma può essere inizializzato a zero semplicemente aggiungendo una parentesi vuota () , come questo: new int[n]() . Più in generale, per tipo di oggetto arbitrario, esegue un'inizializzazione del valore .

Come parte di una funzione giù in una gerarchia di chiamate, questo codice non sarebbe eccezionalmente sicuro, poiché un'eccezione prima dell'espressione delete[] (e dopo la new[] ) causerebbe una perdita di memoria. Un modo per risolvere questo problema è automatizzare la pulizia tramite, ad esempio, un puntatore intelligente std::unique_ptr . Ma un modo generalmente migliore per affrontarlo è usare semplicemente un std::vector : ecco a cosa serve std::vector .

Espansione dell'array di dimensioni dinamiche utilizzando std :: vector.

// Example of std::vector as an expanding dynamic size array.
#include <algorithm>            // std::sort
#include <iostream>
#include <vector>               // std::vector
using namespace std;

int int_from( std::istream& in ) { int x = 0; in >> x; return x; }

int main()
{
    cout << "Sorting integers provided by you.\n";
    cout << "You can indicate EOF via F6 in Windows or Ctrl+D in Unix-land.\n";
    vector<int> a;      // ← Zero size by default.

    while( cin )
    {
        cout << "One number, please, or indicate EOF: ";
        int const x = int_from( cin );
        if( !cin.fail() ) { a.push_back( x ); }  // Expands as necessary.
    }

    sort( a.begin(), a.end() );
    int const n = a.size();
    for( int i = 0; i < n; ++i ) { cout << a[i] << ' '; }
    cout << '\n';
}

std::vector è un modello di libreria standard che fornisce la nozione di una matrice di dimensioni variabili. Si occupa di tutta la gestione della memoria e il buffer è contiguo, quindi un puntatore al buffer (ad esempio &v[0] o v.data() ) può essere passato alle funzioni API che richiedono un array raw. Un vector può persino essere espanso in fase di esecuzione, ad esempio tramite la funzione membro push_back che aggiunge un elemento.

La complessità della sequenza di n operazioni push_back , inclusa la copia o lo spostamento coinvolti nelle espansioni di vettori, viene ammortizzata O ( n ). "Ammortizzato": in media.

Internamente questo è solitamente ottenuto dal raddoppio del vettore della sua dimensione del buffer, la sua capacità, quando è necessario un buffer più grande. Ad esempio, per un buffer che inizia come dimensione 1, e che viene ripetutamente raddoppiato come necessario per n = 17 chiamate push_back , ciò comporta operazioni di copia 1 + 2 + 4 + 8 + 16 = 31, che è inferiore a 2 × n = 34. E più in generale la somma di questa sequenza non può superare 2 × n .

Rispetto all'esempio di matrice raw di dimensioni dinamiche, questo codice basato su vector non richiede all'utente di fornire (e conoscere) il numero di elementi in anticipo. Invece il vettore viene semplicemente espanso secondo necessità, per ogni nuovo valore di articolo specificato dall'utente.

Una matrice di matrice raw di dimensioni fisse (ovvero una matrice raw 2D).

// A fixed size raw array matrix (that is, a 2D raw array).
#include <iostream>
#include <iomanip>
using namespace std;

auto main() -> int
{
    int const   n_rows  = 3;
    int const   n_cols  = 7;
    int const   m[n_rows][n_cols] =             // A raw array matrix.
    {
        {  1,  2,  3,  4,  5,  6,  7 },
        {  8,  9, 10, 11, 12, 13, 14 },
        { 15, 16, 17, 18, 19, 20, 21 }
    };
    
    for( int y = 0; y < n_rows; ++y )
    {
        for( int x = 0; x < n_cols; ++x )
        {
            cout << setw( 4 ) << m[y][x];       // Note: do NOT use m[y,x]!
        }
        cout << '\n';
    }
}

Produzione:

   1   2   3   4   5   6   7
   8   9  10  11  12  13  14
  15  16  17  18  19  20  21

C ++ non supporta la sintassi speciale per l'indicizzazione di un array multidimensionale. Invece una tale matrice è vista come una matrice di matrici (possibilmente di matrici, e così via), e la normale notazione di indice singolo [ i ] è usata per ogni livello. Nell'esempio sopra m[y] riferisce alla riga y di m , dove y è un indice a base zero. Allora questa riga può essere indicizzato a sua volta, ad esempio m[y][x] , che si riferisce alla x ^th elemento - o colonna - di fila y .

Cioè l'ultimo indice varia più velocemente, e nella dichiarazione l'intervallo di questo indice, che qui è il numero di colonne per riga, è l'ultima e "più interna" dimensione specificata.

Poiché il C ++ non fornisce il supporto integrato per gli array di dimensioni dinamiche, oltre all'allocazione dinamica, una matrice di dimensioni dinamiche viene spesso implementata come classe. Quindi la notazione dell'indice matrice matrice raw m[y][x] ha un certo costo, sia esponendo l'implementazione (in modo che ad esempio una vista di una matrice trasposta diventa praticamente impossibile) o aggiungendo qualche sovraccarico e leggero inconveniente quando viene fatto ritornando un oggetto proxy operator[] . E così la notazione di indicizzazione per una tale astrazione può e sarà di solito diversa, sia nell'aspetto che nell'ordine degli indici, ad esempio m(x,y) o m.at(x,y) o m.item(x,y) .

Una matrice di dimensioni dinamiche che utilizza std :: vector per l'archiviazione.

Sfortunatamente a partire dal C ++ 14 non esiste una classe di matrice di dimensioni dinamiche nella libreria standard C ++. Classi Matrix che supportano la dimensione dinamica sono comunque disponibili da un certo numero di librerie di 3 ^rd di partito, tra cui la libreria Boost Matrix (un sub-libreria all'interno della libreria Boost).

Se non vuoi una dipendenza da Boost o da qualche altra libreria, la matrice delle dimensioni dinamiche di un povero in C ++ è proprio come

vector<vector<int>> m( 3, vector<int>( 7 ) );

... dove vector è std::vector . La matrice viene qui creata copiando un vettore di riga n volte in cui n è il numero di righe, qui 3. Ha il vantaggio di fornire la stessa notazione di indicizzazione m[y][x] come per una matrice di matrice raw di dimensioni fisse, ma è un po 'inefficiente perché implica un'allocazione dinamica per ogni riga, ed è un po' pericoloso perché è possibile ridimensionare inavvertitamente una riga.

Un approccio più sicuro ed efficiente consiste nell'utilizzare un singolo vettore come memoria per la matrice e mappare il codice del client ( x , y ) in un indice corrispondente in quel vettore:

// A dynamic size matrix using std::vector for storage.

//--------------------------------------------- Machinery:
#include <algorithm>        // std::copy
#include <assert.h>         // assert
#include <initializer_list> // std::initializer_list
#include <vector>           // std::vector
#include <stddef.h>         // ptrdiff_t

namespace my {
    using Size = ptrdiff_t;
    using std::initializer_list;
    using std::vector;

    template< class Item >
    class Matrix
    {
    private:
        vector<Item>    items_;
        Size            n_cols_;
        
        auto index_for( Size const x, Size const y ) const
            -> Size
        { return y*n_cols_ + x; }

    public:
        auto n_rows() const -> Size { return items_.size()/n_cols_; }
        auto n_cols() const -> Size { return n_cols_; }

        auto item( Size const x, Size const y )
            -> Item&
        { return items_[index_for(x, y)]; }
        
        auto item( Size const x, Size const y ) const
            -> Item const&
        { return items_[index_for(x, y)]; }

        Matrix(): n_cols_( 0 ) {}

        Matrix( Size const n_cols, Size const n_rows )
            : items_( n_cols*n_rows )
            , n_cols_( n_cols )
        {}
        
        Matrix( initializer_list< initializer_list<Item> > const& values )
            : items_()
            , n_cols_( values.size() == 0? 0 : values.begin()->size() )
        {
            for( auto const& row : values )
            {
                assert( Size( row.size() ) == n_cols_ );
                items_.insert( items_.end(), row.begin(), row.end() );
            }
        }
    };
}  // namespace my

//--------------------------------------------- Usage:
using my::Matrix;

auto some_matrix()
    -> Matrix<int>
{
    return
    {
        {  1,  2,  3,  4,  5,  6,  7 },
        {  8,  9, 10, 11, 12, 13, 14 },
        { 15, 16, 17, 18, 19, 20, 21 }
    };
}

#include <iostream>
#include <iomanip>
using namespace std;
auto main() -> int
{
    Matrix<int> const m = some_matrix();
    assert( m.n_cols() == 7 );
    assert( m.n_rows() == 3 );
    for( int y = 0, y_end = m.n_rows(); y < y_end; ++y )
    {
        for( int x = 0, x_end = m.n_cols(); x < x_end; ++x )
        {
            cout << setw( 4 ) << m.item( x, y );        // ← Note: not `m[y][x]`!
        }
        cout << '\n';
    }
}

Produzione:

   1   2   3   4   5   6   7
   8   9  10  11  12  13  14
  15  16  17  18  19  20  21

Il codice sopra riportato non è di livello industriale: è progettato per mostrare i principi di base e soddisfare le esigenze degli studenti che imparano C ++.

Ad esempio, è possibile definire overload operator() per semplificare la notazione dell'indicizzazione.

Inizializzazione di array

Un array è solo un blocco di posizioni di memoria sequenziali per un tipo specifico di variabile. Gli array sono allocati allo stesso modo delle variabili normali, ma con parentesi quadre aggiunte al suo nome [] che contengono il numero di elementi che si adattano alla memoria dell'array.

Il seguente esempio di un array utilizza la tip int , il nome della variabile arrayOfInts , e il numero di elementi [5] che l'array ha spazio per:

int arrayOfInts[5];

Un array può essere dichiarato e inizializzato allo stesso tempo in questo modo

int arrayOfInts[5] = {10, 20, 30, 40, 50};

Quando si inizializza una matrice elencando tutti i suoi membri, non è necessario includere il numero di elementi all'interno delle parentesi quadre. Sarà calcolato automaticamente dal compilatore. Nell'esempio seguente, è 5:

int arrayOfInts[] = {10, 20, 30, 40, 50};

È anche possibile inizializzare solo i primi elementi mentre si assegna più spazio. In questo caso, la definizione della lunghezza tra parentesi è obbligatoria. Quanto segue assegnerà un array di lunghezza 5 con inizializzazione parziale, il compilatore inizializza tutti gli elementi rimanenti con il valore standard del tipo di elemento, in questo caso zero.

int arrayOfInts[5] = {10,20}; // means 10, 20, 0, 0, 0

Le matrici di altri tipi di dati di base possono essere inizializzate allo stesso modo.

char arrayOfChars[5]; // declare the array and allocate the memory, don't initialize

char arrayOfChars[5] = { 'a', 'b', 'c', 'd', 'e' } ; //declare and initialize

double arrayOfDoubles[5] = {1.14159, 2.14159, 3.14159, 4.14159, 5.14159};

string arrayOfStrings[5] = { "C++", "is", "super", "duper", "great!"};

È anche importante notare che quando si accede agli elementi dell'array, l'indice (o la posizione) dell'elemento dell'array inizia da 0.

int array[5] = { 10/*Element no.0*/, 20/*Element no.1*/, 30, 40, 50/*Element no.4*/};
std::cout << array[4]; //outputs 50
std::cout << array[0]; //outputs 10