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

Массивы

Массив — подряд идущие в памяти элементы одного типа.

int a[5];                       /* 5 int, значения не определены (если локальный) */
int b[5] = {1, 2, 3, 4, 5};
int c[5] = {1, 2};              /* {1, 2, 0, 0, 0} */
int d[] = {7, 8, 9};            /* размер 3 вычислен по инициализатору */
double z[70] = {0};             /* все нули */

size_t n = sizeof(b) / sizeof(b[0]);   /* число элементов: 5 */

Индексы начинаются с нуля: у массива из N элементов допустимы индексы 0…N−1.

Массивы и функции

Массив в функцию передаётся как указатель на первый элемент. Поэтому размер передают отдельно:

double dot(const double *a, const double *b, int n)
{
    double s = 0.0;
    for (int i = 0; i < n; i++)
        s += a[i] * b[i];
    return s;
}

Запись double a[] в параметре — то же самое, что double *a.

Массивы и страницы памяти

Раз элементы лежат подряд, массив может пересекать границу страницы. Посчитаем на примере задачи 7: 70 элементов double = 560 байт, страница 512 байт.

Минимум страниц для N байт — ⌈N / P⌉, максимум — ⌈N / P⌉ + 1 (если массив «неудачно» начинается в конце страницы). Это ключ к поиску минимального и максимального ответа.

Двумерные массивы

int m[3][4];          /* 3 строки по 4 элемента, хранятся построчно */
m[1][2] = 5;          /* адрес: m + (1*4 + 2) * sizeof(int) */

Обход по строкам (for i { for j { m[i][j] } }) идёт по памяти подряд — быстро. Обход по столбцам прыгает через строку — для больших массивов это много промахов кеша и TLB.

Строки

Строка в C — массив char, заканчивающийся нулевым байтом '\0'.

char s[] = "fork";          /* {'f','o','r','k','\0'} — 5 байт */
const char *p = "exec";     /* указатель на строковую константу (только чтение!) */

printf("%s %zu %zu\n", s, sizeof(s), strlen(s));   /* fork 5 4 */

Функции из <string.h>:

Итог

• Массив — элементы подряд; индексы с 0; границы не проверяются.
• В функцию массив передаётся как указатель, размер — отдельно.
• Массив размера N байт занимает ⌈N/P⌉ или ⌈N/P⌉+1 страниц размера P.
• Строка — массив char с завершающим '\0'; сравнение — strcmp.