Динамические массивы в C

Если вы используете относительно современный ЯП вроде JS, то массивы в С могут ввести вас в ступор.

Вступление

Массив в JavaScript:

let numbers = [];
numbers.push(1);
numbers.push(2);
numbers.push(3);
console.log(numbers); // [1, 2, 3]

Приведенный выше пример показывает, как бы мы создали массив в JS. Хорошо видно, что возможно добавить столько строк, сколько нам нужно.

Массив в C:

int numbers[3];
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
printf("%d\n", numbers[0]); // 1
printf("%d\n", numbers[1]); // 2
printf("%d\n", numbers[2]); // 3

Первое выражение numbers[3] говорит компилятору, что массив сохранит в памяти 3 числа. Далее сохраним 1,2 и 3 под соответствующими индексами и выведем на дисплей.
Пока все прекрасно, но но нельзя добавить ещё элементы:

int numbers[3];
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 4;
printf("%d\n", numbers[0]); // 1
printf("%d\n", numbers[1]); // 2
printf("%d\n", numbers[2]); // 3
printf("%d\n", numbers[3]); // should be 4

И что на это скажет gcc?:

array.c:8:5: warning: array index 3 is past the end of the array (which contains 3 elements) [-Warray-bounds]

Таким образом, мы получаем исключение за пределами границ памяти. Места в нашем массиве недостаточно, чтобы вместить ещё элементы.
Что же, если мы нуждаемся в динамическом массиве, в который можно добавить n элементов?

На С мы можем создать собственную имплементацию массива с динамически растущим размером.
Для этого используем блоки памяти.

malloc, realloc и указатели (pointers)

В С каждый тип данных имеет свой размер хранилища:

Тип Размер хранилища Диапазон значений
char 1 byte -128 до 127 или 0 до 255
unsigned char 1 byte 0 до 255
signed char 1 byte -128 до 127
int 2 или 4 bytes -32,768 до 32,767 или -2,147,483,648 до 2,147,483,647
unsigned int 2 или 4 bytes 0 до 65,535 или 0 до 4,294,967,295
short 2 bytes -32,768 to 32,767
unsigned short 2 bytes 0 до 65,535
long 8 bytes -9223372036854775808 до 9223372036854775807
unsigned long 8 bytes 0 до 18446744073709551615

В моей системе это 4 байта для целых чисел (integers). Просто имея эти данные можно создавать динамические массивы любого размера.
Размер типа данных можно получить при помощи функций sizeof(int), sizeof(double) или для тех типов данных, которые вам требуются.
Используя функции malloc и realloc мы можем создавать динамические блоки памяти.

Допустим, мы хотим начать с возможности хранить 3 целых числа (integers),это можно сделать, выделив блок памяти из 12 байт:

Единственным аргументом malloc является размер блока памяти в байтах.
Malloc возвращает указатель(pointer) на вновь созданный блок памяти.
#define INITIAL_CAPACITY 3
int main(){
     int* data = malloc(INITIAL_CAPACITY * sizeof(int));
}

Теперь у нас есть блок памяти, достаточно большой, чтобы вместить наши 3 целых числа - нам нужно сделать его динамическим. Сейчас мы все ещё не можем поместить больше 3-х элементов в наш блок памяти.

Если отслеживать размер и объемом используемой памяти, можно рассчитать, когда нужно изменить ее размер. Если блок памяти заполнен, удвоим размер этого блока памяти, при помощи вызвова realloc , который просто расширяет текущий блок памяти.

#define INITIAL_CAPACITY 3
void push(int *arr, int index, int value, int *size, int *capacity){
     int* ptr;
     if(*size > *capacity){
          ptr = realloc(arr, sizeof(arr) * 2);
          if(ptr == NULL)
               exit(0);
          else
               *capacity = sizeof(arr) * 2;
     }
 
     arr[index] = value;
     *size = *size + 1;
}
int main(){
     int size = 0;
     int capacity = INITIAL_CAPACITY;
     int* arr = malloc(INITIAL_CAPACITY * sizeof(int));
}

Теперь есть возможность добавлять элементы в блок памяти динамически.
Собрав все это вместе, получим следующую программу:

#include <stdio.h>
#include <stdlib.h>
 
#define INITIAL_CAPACITY 2
 
void push(int *arr, int index, int value, int *size, int *capacity){
     int* ptr;
     if(*size > *capacity){
          ptr = realloc(arr, sizeof(arr) * 2);
          if(ptr == NULL)
               exit(0);
          else
               *capacity = sizeof(arr) * 2;
     }
 
     arr[index] = value;
     *size = *size + 1;
}
 
int main(){
     int size = 0;
     int capacity = INITIAL_CAPACITY;
     int* arr = malloc(INITIAL_CAPACITY * sizeof(int));
     if(arr == NULL) {
          printf("Memory not allocated.\n");
          exit(0);
     }
     else {
          push(arr, 0, 1, &size, &capacity);
          push(arr, 1, 2, &size, &capacity);
          push(arr, 2, 3, &size, &capacity);
 
          printf("Current capacity: %d\n", capacity); // Current capacity: 2
 
          push(arr, 3, 4, &size, &capacity);
          push(arr, 4, 5, &size, &capacity);
          push(arr, 5, 6, &size, &capacity);
 
          printf("Current capacity: %d\n", capacity); // Current capacity: 16
     }
}
Только авторизованные участники могут оставлять комментарии.
  • blog/dynamic_arrays_in_c_lang.txt
  • Последние изменения: 2019/05/28