C++
Массивы

Вступление

Размер массива: тип safe во время компиляции.

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

Идиома C для размера массива sizeof(a)/sizeof(a[0]) примет указатель как аргумент и в итоге даст неверный результат.

Для C ++ 11

используя C ++ 11, вы можете:

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

Пример:

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

До C ++ 17 (начиная с этой записи) У C ++ не было встроенного основного языка или стандартной библиотечной утилиты для получения размера массива, но это можно реализовать, передав массив по ссылке на шаблон функции, так как показано выше. Точная, но важная точка: параметр размера шаблона является size_t , несколько несовместимым с типом результата функции подписанного Size , чтобы разместить компилятор g ++, который иногда настаивает на size_t для сопоставления шаблонов.

С C ++ 17 и более поздними версиями можно использовать std::size , который специализирован для массивов.

Динамический размерный массив

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

Программа, объявляющая массив T a[n]; где n определяется временем выполнения, может компилироваться с определенными компиляторами, которые поддерживают массивы вариативной длины C99 (VLAs) в качестве расширения языка. Но VLA не поддерживаются стандартным C ++. В этом примере показано, как вручную распределить массив динамического размера с помощью new[] -выражения,

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

... затем используйте его и, наконец, освободите его с помощью delete[] -expression:

delete[] a;

Выделенный здесь массив имеет неопределенные значения, но его можно инициализировать нулем, просто добавив пустую скобку () , например: new int[n]() . В более общем плане, для произвольного типа элемента это выполняет инициализацию значения .

Как часть функции вниз в иерархии вызовов этот код не будет безопасным для исключений, поскольку исключение перед выражением delete[] (и после new[] ) вызовет утечку памяти. Один из способов решения этой проблемы - автоматизировать очистку, например, с помощью умного указателя std::unique_ptr . Но, как правило, лучший способ обратиться к нему - просто использовать std::vector : для этого используется std::vector .

Расширение массива динамических размеров с помощью 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 - стандартный шаблон класса библиотеки, который предоставляет понятие массива с переменным размером. Он заботится обо всем управлении памятью, а буфер смежен, поэтому указатель на буфер (например, &v[0] или v.data() ) может быть передан функциям API, требующим сырой массив. vector можно даже развернуть во время выполнения, например, через функцию push_back , добавляющую элемент.

Сложность последовательности операций n push_back , включая копирование или перемещение, участвующие в векторных разложениях, амортизируется O ( n ). «Амортизировано»: в среднем.

Обычно это достигается путем удвоения вектора размера буфера, его емкости, когда требуется больший буфер. Например, для буфера, начинающегося как размер 1, и при повторном удвоении при n = 17 вызовах push_back это включает в себя операции копирования 1 + 2 + 4 + 8 + 16 = 31, которая меньше 2 × n = 34. И более общая сумма этой последовательности не может превышать 2 × n .

По сравнению с примером необработанного массива динамического размера этот vector код не требует, чтобы пользователь предоставлял (и знал) количество предметов спереди. Вместо этого вектор просто расширяется по мере необходимости, для каждого нового значения элемента, указанного пользователем.

Матрица необработанного массива фиксированного размера (т. Е. 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';
    }
}

Выход:

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

C ++ не поддерживает специальный синтаксис для индексирования многомерного массива. Вместо этого такой массив рассматривается как массив массивов (возможно, массивов и т. Д.), А для каждого уровня используется стандартная однозначная нотация [ i ] . В приведенном выше примере m[y] ссылается на строку y of m , где y - индекс на основе нуля. Затем эта строка может быть проиндексирована по очереди, например m[y][x] , которая ссылается на x ^й элемент - или столбец строки y .

Т.е. последний индекс изменяется быстрее, а в объявлении диапазон этого индекса, который представляет собой число столбцов на строку, является последним и «самым внутренним» размером.

Поскольку C ++ не обеспечивает встроенную поддержку массивов динамических размеров, за исключением динамического распределения, динамическая матрица размеров часто реализуется как класс. Тогда номенклатура индексирования матрицы исходного массива m[y][x] имеет некоторую стоимость либо путем представления реализации (так что, например, представление транспонированной матрицы становится практически невозможным) или путем добавления некоторых накладных расходов и незначительных неудобств, когда это делается путем возврата прокси-объект от operator[] . И поэтому индексирующее обозначение для такой абстракции может и обычно будет отличаться как по внешнему виду, так и по порядку индексов, например m(x,y) или m.at(x,y) или m.item(x,y) .

Матрица динамического размера, использующая std :: vector для хранения.

К сожалению, с C ++ 14 в стандартной библиотеке C ++ нет динамического размера. Матричные классы , которые поддерживают динамический размер, однако , доступны из ряда 3 - ^й партии библиотеки, включая библиотеку подталкивание Matrix (суб-библиотеку в библиотеке форсирования).

Если вам не нужна зависимость от Boost или какой-либо другой библиотеки, то одна динамическая матрица бедного человека на C ++ похожа на

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

... где vector - std::vector . Матрица здесь создается путем копирования вектора строки n раз, где n - количество строк, здесь 3. Преимущество состоит в том, чтобы предоставить такую ​​же нотацию индексирования m[y][x] как для матрицы исходного массива фиксированного размера, но это немного неэффективно, потому что оно включает динамическое распределение для каждой строки, и это немного небезопасно, потому что возможно непреднамеренно изменить размер строки.

Более безопасным и эффективным подходом является использование одного вектора в качестве хранилища для матрицы и сопоставление кода клиента ( x , y ) с соответствующим индексом в этом векторе:

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

Выход:

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

Вышеприведенный код не является промышленным классом: он призван показать основные принципы и удовлетворять потребности студентов, изучающих C ++.

Например, можно определить перегрузки operator() для упрощения нотации индексирования.

Инициализация массива

Массив - это всего лишь блок последовательных мест памяти для определенного типа переменной. Массивы распределяются так же, как и обычные переменные, но с квадратными скобками, добавленными к его имени [] которые содержат количество элементов, которые вписываются в память массива.

В следующем примере массива используется тип int , имя переменной arrayOfInts и количество элементов [5] , в которых массив имеет место для:

int arrayOfInts[5];

Массив может быть объявлен и инициализирован одновременно с этим

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

При инициализации массива путем перечисления всех его членов нет необходимости включать число элементов в квадратные скобки. Он будет автоматически вычисляться компилятором. В следующем примере это 5:

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

Также возможно инициализировать только первые элементы, выделяя больше места. В этом случае определение длины в скобках является обязательным. Далее будет выделен массив длиной 5 с частичной инициализацией, компилятор инициализирует все остальные элементы со стандартным значением типа элемента, в этом случае нуль.

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

Массивы других базовых типов данных могут быть инициализированы таким же образом.

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

Важно также отметить, что при доступе к элементам массива индекс элемента (или позиция) массива начинается с 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