C++
Tablice

Wprowadzenie

Rozmiar tablicy: wpisz bezpieczny w czasie kompilacji.

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

Idiom C dla rozmiaru tablicy, sizeof(a)/sizeof(a[0]) , zaakceptuje wskaźnik jako argument, a następnie na ogół da niepoprawny wynik.

Dla C ++ 11

używając C ++ 11 możesz:

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

Przykład:

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

Aż do C ++ 17 (nadchodzące od tego pisania) C ++ nie miał wbudowanego języka podstawowego ani standardowego narzędzia bibliotecznego do uzyskania rozmiaru tablicy, ale można to zaimplementować poprzez przekazanie tablicy przez odwołanie do szablonu funkcji, ponieważ pokazane powyżej. Dobra, ale ważna uwaga: parametr size szablonu to size_t , nieco niespójny z typem wyniku podpisanej funkcji Size , w celu dostosowania do kompilatora g ++, który czasami nalega na size_t celu dopasowania szablonu.

W C ++ 17 i późniejszych można zamiast tego użyć std::size , który specjalizuje się w tablicach.

Dynamiczny rozmiar tablicy surowej

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

Program deklarujący tablicę T a[n]; gdzie n jest określane w czasie wykonywania, może kompilować się z pewnymi kompilatorami, które obsługują tablice długości V99 (C99) jako rozszerzenie języka. Ale VLA nie są obsługiwane przez standardowy C ++. Ten przykład pokazuje, jak ręcznie przydzielić dynamiczną tablicę rozmiarów za pomocą new[] wyrażenia new[] ,

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

… Następnie użyj go, a na koniec cofnij przydział poprzez wyrażenie delete[] :

delete[] a;

Przydzielona tutaj tablica ma nieokreślone wartości, ale można ją zainicjować zero, po prostu dodając pusty nawias () , taki jak: new int[n]() . Mówiąc bardziej ogólnie, dla dowolnego typu elementu wykonuje to inicjalizację wartości .

Jako część funkcji w hierarchii wywołań ten kod nie byłby bezpieczny pod względem wyjątków, ponieważ wyjątek przed wyrażeniem delete[] (i po new[] ) spowodowałby przeciek pamięci. Jednym ze sposobów rozwiązania tego problemu jest zautomatyzowanie czyszczenia za pomocą np. Inteligentnego wskaźnika std::unique_ptr . Ale ogólnie lepszym sposobem rozwiązania tego problemu jest użycie std::vector : po to jest std::vector .

Rozszerzanie tablicy rozmiarów dynamicznych za pomocą 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 to standardowy szablon klasy biblioteki, który zapewnia pojęcie tablicy o zmiennej wielkości. Zajmuje się całym zarządzaniem pamięcią, a bufor jest ciągły, więc wskaźnik do bufora (np. &v[0] lub v.data() ) można przekazać do funkcji API wymagających surowej tablicy. vector można nawet rozwinąć w czasie wykonywania, np. Poprzez funkcję członka push_back która dołącza element.

Złożoność sekwencji n operacji push_back , w tym kopiowania lub przenoszenia zaangażowanych w rozwinięcia wektora, jest amortyzowana przez O ( n ). „Amortyzowane”: średnio.

Wewnętrznie jest to zwykle osiągane przez wektor podwajający jego rozmiar bufora, jego pojemność, gdy potrzebny jest większy bufor. Np. Dla bufora rozpoczynającego się od rozmiaru 1 i wielokrotnie podwajanego w razie potrzeby dla n = 17 wywołań push_back , obejmuje to operacje kopiowania 1 + 2 + 4 + 8 + 16 = 31, czyli mniej niż 2 × n = 34. I bardziej ogólnie suma tej sekwencji nie może przekraczać 2 × n .

W porównaniu z przykładem surowej tablicy z dynamicznym rozmiarem, ten oparty na vector kod nie wymaga od użytkownika podania (i znajomości) liczby elementów z góry. Zamiast tego wektor jest po prostu rozwijany w razie potrzeby dla każdej nowej wartości elementu określonej przez użytkownika.

Matryca surowa o ustalonym rozmiarze (tj. Surowa macierz 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';
    }
}

Wynik:

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

C ++ nie obsługuje specjalnej składni do indeksowania tablicy wielowymiarowej. Zamiast tego taka tablica jest postrzegana jako tablica tablic (prawdopodobnie tablic itp.), A dla każdego poziomu stosuje się zwykłą notację pojedynczego indeksu [ i ] . W powyższym przykładzie m[y] odnosi się do wiersza y m , gdzie y jest indeksem zerowym. Następnie ten rząd może być indeksowana z kolei, na przykład m[y][x] , który odnosi się do x ^th - element lub kolumny - w rzędzie y .

Oznacza to, że ostatni indeks zmienia się najszybciej, a w deklaracji zakres tego indeksu, który tutaj jest liczbą kolumn w wierszu, jest ostatnim i określonym „najbardziej wewnętrznym” rozmiarem.

Ponieważ C ++ nie zapewnia wbudowanej obsługi dynamicznych tablic rozmiarów, innych niż dynamiczny przydział, matryca rozmiarów dynamicznych jest często implementowana jako klasa. Następnie notacja indeksowania macierzy surowej macierzy m[y][x] ma pewien koszt, albo przez ujawnienie implementacji (tak, że np. Widok transponowanej macierzy staje się praktycznie niemożliwy), albo przez dodanie pewnych kosztów ogólnych i drobnych niedogodności, gdy jest to wykonywane przez powrót obiekt proxy od operator[] . Tak więc notacja indeksująca dla takiej abstrakcji może i zwykle będzie różna, zarówno pod względem wyglądu, jak i kolejności indeksów, np. m(x,y) lub m.at(x,y) lub m.item(x,y) .

Dynamiczna matryca rozmiarów wykorzystująca do przechowywania std :: vector.

Niestety od C ++ 14 w standardowej bibliotece C ++ nie ma klasy matrycy rozmiarów dynamicznych. Klasy Matrix że wielkość wsparcia dynamiczne są jednak dostępne w wielu bibliotekach 3 ^rd podmiotami, w tym biblioteki Boost, Matrix (sub-biblioteki w bibliotece Boost).

Jeśli nie chcesz zależeć od Boost lub innej biblioteki, to dynamiczna matryca jednego biedaka w C ++ jest jak

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

… Gdzie vector to std::vector . Macierz jest tutaj tworzona przez skopiowanie wektora wiersza n razy, gdzie n jest liczbą wierszy, tutaj 3. Ma tę zaletę, że zapewnia taką samą notację indeksowania m[y][x] jak dla macierzy surowej o stałym rozmiarze, ale jest to trochę nieefektywne, ponieważ wymaga dynamicznej alokacji dla każdego wiersza i jest trochę niebezpieczne, ponieważ można przypadkowo zmienić rozmiar wiersza.

Bardziej bezpiecznym i wydajnym podejściem jest użycie pojedynczego wektora jako pamięci dla macierzy i odwzorowanie kodu klienta ( x , y ) na odpowiedni indeks w tym wektorze:

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

Wynik:

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

Powyższy kod nie jest klasy przemysłowej: ma na celu pokazanie podstawowych zasad i zaspokojenie potrzeb uczniów uczących się języka C ++.

Na przykład można zdefiniować przeciążenia operator() celu uproszczenia notacji indeksującej.

Inicjalizacja tablicy

Tablica jest tylko blokiem sekwencyjnych lokalizacji pamięci dla określonego typu zmiennej. Tablice są przydzielane w taki sam sposób, jak zmienne normalne, ale do nazwy [] dołączone są nawiasy kwadratowe, które zawierają liczbę elementów pasujących do pamięci tablicy.

Poniższy przykład tablicy wykorzystuje typ int , nazwę zmiennej arrayOfInts i liczbę elementów [5] , dla których tablica ma miejsce:

int arrayOfInts[5];

Tablicę można zadeklarować i zainicjować w ten sam sposób

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

Podczas inicjowania tablicy przez wylistowanie wszystkich jej elementów nie jest konieczne dołączanie liczby elementów w nawiasach kwadratowych. Zostanie automatycznie obliczony przez kompilator. W poniższym przykładzie jest to 5:

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

Możliwe jest również zainicjowanie tylko pierwszych elementów przy przydzielaniu większej ilości miejsca. W takim przypadku określenie długości w nawiasach jest obowiązkowe. Poniżej przydzieli tablicę o długości 5 z częściową inicjalizacją, kompilator inicjuje wszystkie pozostałe elementy ze standardową wartością typu elementu, w tym przypadku zero.

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

Tablice innych podstawowych typów danych mogą być inicjowane w ten sam sposób.

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

Należy również pamiętać, że podczas uzyskiwania dostępu do elementów tablicy indeks (lub pozycja) elementu tablicy zaczyna się od 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