Массивы и кортежи - Алгоритмика
Массивы и кортежи

Массивы и кортежи

В C++ есть несколько способов объединить группу переменных фиксированного размера в одну переменную.

Массивы в C

В языке C есть три основных способа определить массив:

int a[100];

int main() {
    int b[100];
    int *c = new int[100];
    del[] c;
    return 0;
}

Получившиеся переменные функционально идентичные, но немного отличаются:

  • Определенный глобально массив a будет лежать в заранее выделенной области памяти на протяжении всего времени исполнения программы. Все элементы изначально заполнены своим значением по умолчанию (для int, нулём).
  • Определенный внутри функции массив b будет лежать на стеке — специальной области памяти для временных переменных — и будет удален сразу когда функция (или любой другой блок вроде тела цикла или if-а) завершится. Так как размер стека исполнения ограничен, большие массивы ($>10^6$) выделять так нельзя. Изначально он заполнен чем-то случайным, что лежало на тот момент в памяти — чтобы заполнить нулями, можно написать int x[100] = {}. Чтобы заполнить все элементы заданными значениями, можно написать int y[5] = {4, 8, 15, 23, 42}.
  • Определенный через оператор new массив c выделен динамически. Он существует, пока его специально не удалили через оператор del[]. Он также заполнен тем, что на тот момент лежало в памяти. В отличие от предыдущих двух вариантов, он может быть любого размера, даже неизвестного заранее.

Важно. В первых двух вариантах размер массива должен быть известной на момент компиляции константой. Компилятор GCC может скомпилировать выражение вида int a[n], и действительно выделится массив не-константного размера; IDE поэтому может и не подчеркнуть его, хотя это не является частью стандарта.

Все элементы массива хранятся последовательно в памяти, а сами переменные a, b и c на самом деле являются указателями на первый элемент массива. Скобочки — это просто «синтаксический сахар»:

a[k]  <=>  *(a + k)

Для инициализации и копирования в C есть две полезные функции, memset и memcpy соответственно.

Первая берет указатель «куда», указатель «откуда» и количество байт, которые нужно перекопировать:

memcpy(dest, src, sizeof src);

Вторая берет указатель «куда» и один байт — значение, которое нужно раскопировать по всему массиву.

memset(arr, 0, sizeof arr);

Важно. memset работает именно с сырыми байтами, а не типами вроде int или float. Поэтому через memset массивы целочисленных типов можно заполнять только «периодичными» значениями, вроде $0$ и $-1$ (отрицательная единица в двоичной записи выглядит как 111..111).

Также важно помнить, что последний аргумент в обоих функциях — это число байтов, а не количество элементов. В случае с массивами не-константного размера можно домножить размер типа на размер массива:

memcpy(dest, src, sizeof(int) * n)

Здесь sizeof(int) = 4. Вместо просто четверки так пишут для самокомментируемости.

std::array

В C++11 добавили свой класс для массивов константного размера:

// int a[3] = {1, 2, 3};
array<int, 3> a = {1, 2, 3};

Все операции с ним работают по аналогии с сишными. Основное отличие — он является контейнером STL, то есть у него есть итераторы и с ним работают все алгоритмы из стандартной библиотеки.

sort(a.begin(), a.end());

С обычными массивами, впрочем, тоже — указатели автоматически приводятся к итераторам:

sort(a, a + 3);

Массивы из STL, как и обычные массивы константного размера, поддерживают итерирование:

for (int x : a)
    cout << x << endl;

Также можно изменять элементы в массиве во время итерирования следующим синтаксисом:

for (int &x : a)
    x *= 2;

В STL также есть более ошибкоустойчивая альтернатива memsetstd::fill:

fill(a.begin(), a.end(), 42);

Она уже работает с полными типами, хотя и немного медленнее.

std::pair и std::tuple

Тип pair<T1, T2> хранит пару из переменных не обязательно одинаковых типов:

pair<int, int> interval = {0, 42};
pair<int, double> index_and_value = {7, 3.1415};

Первый элемент доступен через поле .first, а второй через .second.

Его обобщение, tuple, хранит кортеж из произвольного количества переменных:

tuple<int, int, int> coords_xyz = {1, 2, 3};

Вместо .first, .second, .third и так далее с tuple нужно использовать индексы.

Пары и тюплы удобно возвращать из функций:

typedef tuple<double, double, double> point;

point rotate(point p) {
    return {p[1], p[2], p[0]};
}

Также по массивам из них удобно итерироваться:

point points[100];

for (auto [x, y, z] : points)
    cout << x << y << z << endl;

struct

Очень рекомендуется по возможности вместо пар и тюплов объявлять структуры.

struct point {
    double x, y, z;
};

Вместо возни с .first и .second или индексами вы получаете именованные поля, а также возможность определять свои методы и перегружать операторы:

point::length() {
    return sqrt(x * x + y * y + z * z);
}

point operator+(point a, point b) {
    return {a.x + b.x, a.y + b.y, a.z + b.z};
}

Единственный минус структур в том, что по для пар и тюплов будут определены функции сравнения и хеширования, и поэтому их можно сразу в таком виде класть в качестве ключа в структуры из STL вроде set или unordered_set, а для структур их нужно писать отдельно.