C++
Tableaux

Introduction

Taille du tableau: tapez safe au moment de la compilation.

#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";
}

Le langage C pour la taille du tableau, sizeof(a)/sizeof(a[0]) acceptera un pointeur comme argument et donnera généralement un résultat incorrect.

Pour C ++ 11

en utilisant C ++ 11 vous pouvez faire:

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

Exemple:

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

Jusqu'à C ++ 17 (à paraître) Le C ++ n'avait pas de langage de base intégré ni d'utilitaire de bibliothèque standard pour obtenir la taille d'un tableau, mais cela peut être implémenté en passant le tableau par référence à un modèle de fonction, comme montré ci-dessus. Point précis mais important: le paramètre de taille de modèle est un size_t , quelque peu incompatible avec le type de résultat de la fonction Size signée, afin de prendre en charge le compilateur g ++ qui insiste parfois sur size_t pour la correspondance de modèle.

Avec C ++ 17 et versions ultérieures, on peut utiliser std::size , qui est spécialisé pour les tableaux.

Tableau brut de taille dynamique

// 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 programme qui déclare un tableau T a[n]; où n est déterminé à l'exécution, peut être compilé avec certains compilateurs qui prennent en charge les tableaux de longueurs variadiques C99 (VLA) en tant qu'extension de langage. Mais les VLA ne sont pas supportés par le standard C ++. Cet exemple montre comment allouer manuellement un tableau de taille dynamique via une new[] expression new[] ,

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

… Alors utilisez-le et enfin désallouez-le via une expression delete[] :

delete[] a;

Le tableau affecté ici a des valeurs indéterminées, mais il peut être initialisé à zéro en ajoutant simplement une parenthèse vide () , comme ceci: new int[n]() . Plus généralement, pour un type d'article arbitraire, une initialisation de valeur est effectuée .

Dans le cadre d'une fonction dans une hiérarchie d'appels, ce code ne serait pas exempt d'exception, car une exception avant l'expression delete[] (et après la new[] ) provoquerait une fuite de mémoire. Une façon de résoudre ce problème consiste à automatiser le nettoyage via, par exemple, un pointeur intelligent std::unique_ptr . Mais une meilleure façon de le résoudre consiste à utiliser simplement un std::vector : c'est ce que std::vector est là pour ça.

Extension du tableau de taille dynamique en utilisant 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 est un modèle de classe de bibliothèque standard qui fournit la notion d'un tableau de taille variable. Il prend en charge toute la gestion de la mémoire, et le tampon est contigu donc un pointeur vers le tampon (par exemple, &v[0] ou v.data() ) peut être transmis aux fonctions API nécessitant un tableau brut. Un vector peut même être développé au moment de l'exécution, par exemple via la fonction membre push_back qui ajoute un élément.

La complexité de la séquence de n opérations push_back , y compris la copie ou le déplacement impliqué dans les extensions vectorielles, est amortie O ( n ). «Amorti»: en moyenne.

En interne, ceci est généralement obtenu par le fait que le vecteur double sa taille de tampon, sa capacité, lorsqu'un plus grand tampon est nécessaire. Par exemple, pour un tampon commençant à la taille 1 et doublé à plusieurs reprises selon les besoins pour n = 17 appels push_back , cela implique 1 + 2 + 4 + 8 + 16 = 31 opérations de copie, ce qui est inférieur à 2 × n . plus généralement la somme de cette séquence ne peut dépasser 2 × n .

Par rapport à l'exemple de tableau brut de taille dynamique, ce code vector ne nécessite pas que l'utilisateur fournisse (et connaisse) le nombre d'éléments à la fois. Au lieu de cela, le vecteur est simplement développé selon les besoins, pour chaque nouvelle valeur d'élément spécifiée par l'utilisateur.

Une matrice de matrice brute de taille fixe (c'est-à-dire un tableau brut 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';
    }
}

Sortie:

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

C ++ ne supporte pas la syntaxe spéciale pour indexer un tableau multidimensionnel. Au lieu de cela, un tel tableau est considéré comme un tableau de tableaux (éventuellement de tableaux, etc.), et la notation d'index simple ordinaire [ i ] est utilisée pour chaque niveau. Dans l'exemple ci-dessus, m[y] fait référence à la ligne y de m , où y est un index basé sur zéro. Ensuite , cette ligne peut être indexé à son tour, par exemple , m[y][x] , qui se réfère à la x ^ième élément - ou colonne - de la ligne y .

C'est-à-dire que le dernier index varie le plus rapidement, et dans la déclaration, la plage de cet index, qui est ici le nombre de colonnes par ligne, est la dernière et la plus petite taille spécifiée.

Comme C ++ ne prend pas en charge les tableaux de taille dynamique, hormis l'allocation dynamique, une matrice de taille dynamique est souvent implémentée en tant que classe. Alors, la notation d'indexation matricielle brute m[y][x] a un certain coût, soit en exposant l'implémentation (de sorte qu'une vue d'une matrice transposée devient pratiquement impossible) ou en ajoutant une surcharge et un léger inconvénient un objet proxy de l' operator[] . Et donc, la notation d'indexation pour une telle abstraction peut et sera généralement différente, à la fois en apparence et dans l'ordre des index, par exemple m(x,y) ou m.at(x,y) ou m.item(x,y) .

Une matrice de taille dynamique utilisant std :: vector pour le stockage.

Malheureusement, à partir de C ++ 14, il n'y a pas de classe de matrice de taille dynamique dans la bibliothèque standard C ++. Classes de matrice qui prennent en charge la taille dynamique sont toutefois disponibles à partir d' un certain nombre de 3 ^e bibliothèques du parti, y compris la bibliothèque Matrix Boost (une sous-bibliothèque au sein de la bibliothèque Boost).

Si vous ne voulez pas de dépendance sur Boost ou une autre bibliothèque, la matrice de taille dynamique d'un homme pauvre en C ++ est comme

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

… Où le vector est std::vector . La matrice est ici créée en copiant un vecteur de ligne n fois où n est le nombre de lignes, ici 3. Il a l'avantage de fournir la même notation d'indexation m[y][x] que pour une matrice de matrice brute de taille fixe, mais c'est un peu inefficace car il implique une allocation dynamique pour chaque ligne, et c'est un peu dangereux car il est possible de redimensionner une ligne par inadvertance.

Une approche plus sûre et efficace consiste à utiliser un seul vecteur en tant que stockage pour la matrice et à mapper le code client ( x , y ) sur un index correspondant dans ce vecteur:

// 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';
    }
}

Sortie:

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

Le code ci-dessus n'est pas de qualité industrielle: il est conçu pour montrer les principes de base et répondre aux besoins des étudiants qui apprennent le C ++.

Par exemple, on peut définir des surcharges d' operator() pour simplifier la notation d'indexation.

Initialisation du tableau

Un tableau est juste un bloc d'emplacements de mémoire séquentiels pour un type de variable spécifique. Les tableaux sont alloués de la même manière que les variables normales, mais avec des crochets ajoutés à son nom [] qui contiennent le nombre d'éléments qui rentrent dans la mémoire du tableau.

L'exemple suivant d'un tableau utilise le type int , le nom de la variable arrayOfInts et le nombre d'éléments [5] que le tableau peut arrayOfInts :

int arrayOfInts[5];

Un tableau peut être déclaré et initialisé en même temps comme ceci

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

Lors de l'initialisation d'un tableau en listant tous ses membres, il n'est pas nécessaire d'inclure le nombre d'éléments à l'intérieur des crochets. Il sera automatiquement calculé par le compilateur. Dans l'exemple suivant, c'est 5:

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

Il est également possible d'initialiser uniquement les premiers éléments tout en allouant plus d'espace. Dans ce cas, la définition de la longueur entre parenthèses est obligatoire. Ce qui suit va allouer un tableau de longueur 5 avec une initialisation partielle, le compilateur initialise tous les éléments restants avec la valeur standard du type d'élément, dans ce cas zéro.

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

Les tableaux d'autres types de données de base peuvent être initialisés de la même manière.

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!"};

Il est également important de noter que lors de l'accès aux éléments du tableau, l'index (ou la position) de l'élément du tableau commence à 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