Динамический массив - Алгоритмика
Динамический массив

Динамический массив

автор Сергей Слотин

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

Динамический или расширяющийся массив — это массив, который может изменять свой размер в зависимости от количества элементов в нём.

Динамические массивы обычно используют, когда заранее предсказать размер массива сложно или невозможно. В таком контексте у динамических массивов помимо операций доступа и изменения произвольных элементов есть ещё три:

  1. Добавить в конец массива элемент $x$.
  2. Удалить последний элемент массива.
  3. Узнать размер массива.

При этом все операции должны выполняться за $O(1)$ — необязательно в худшем случае, но амортизировано.

Реализация

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

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

  • указатель на массив $t$,
  • размер этого массива,
  • текущее число элементов (меньшее размера массива $t$).

При этом внутренний массив $t$ расширяют (деаллоцируют и заново аллоцируют с большим размером), когда он становится полностью заполненным, и требуется добавить ещё один элемент. Также опционально можно сжимать массив, когда доля заполненных элементов станет малой — это позволит вернуть не использующуюся память.

template <typename T>
struct dynamic_array {
    T *t;
    int size = 0, capacity;
    
    dynamic_array(int capacity) : capacity(capacity) {
        t = new T[capacity];
    }

    void resize(int new_capacity) {
        T *new_t = new T[new_capacity];
        memcpy(new_t, t, sizeof(T) * size);
        delete[] t;
        t = new_t;
    }

    T get(int k) {
        return t[k];
    }

    T set(int k, T x) {
        t[k] = x;
    }

    void add(T x) {
        if (size == capacity)
            resize(2 * capacity);
        t[size++] = x;
    }

    void del() {
        // если хотим сэкономить память:
        if (4 * size < capacity)
            resize(capacity / 2);
        size--;
    }
};

Время работы

В худшем случае операции добавления и удаления работают за линейное время, потому что нам нужно пересоздавать весь массив размера $O(n)$. Однако амортизировано все операции будут работать за $O(1)$. Применим метод предоплаты чтобы это показать.

add

Пусть единицей стоимости операции является одна монетка. Тогда при каждой операции add, при которой нам не требуется копирование, мы будем платить три монетки: одна из них пойдёт на стоимость самой этой операции, а две будут в резерве — если мы добавили $k$-ый элемент, мы будем класть по одной монетке к элементам с номерами $k$ и $(k−\frac{n}{2})$.

К тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которой мы и сможем оплатить его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add — 3, и среднее время её работы — $O(1)$.

del

При каждой обычной операции del будем платить две монетки. Одну из них потратим на непосредственно удаление последнего ($k$-того) элемента, другую положим рядом с элементом, стоящим на позиции $(k \bmod \frac{n}{4})$. Тогда даже в худшем случае — если мы только что расширились, а потом удалили $\frac{n}{4}$ элементов с конца — у каждого элемента из первых $\frac{n}{4}$ будет по монете, которые мы и потратим на их перемещение.

В языках программирования

std::vector

В С++ динамический массив реализован в структуре vector из стандартной библиотеки.

// создать пустой вектор
vector<int> a;

// вставляет x в конец a
a.push_back(x);

// возвращает размер вектора а
a.size();

// сделать размер вектора = x
// либо удаляются последние элементы, либо добавляются нули
a.resize(x);

// сделать размер вектора = x, добавляются y
a.resize(x, y);

// при инициализации можно изначально задать размер и элементы массива
vector<int> a(8);         // {0, 0, 0, 0, 0, 0, 0, 0}
vector<int> b(5, 42);     // {42, 42, 42, 42, 42}
vector<int> c = {1, 2, 3} // {1, 2, 3}

При попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера — в 2 раза при компиляции через GCC и в 1.5 при компиляции через MSVC. При удалении элементов уменьшение размера массива не происходит.

Получить capacity у vector можно с помощью одноимённой функции:

vector<int> a;
for (int i = 0; i < 10; i++) {
    a.push_back(i);
    cout << "size: " << a.size() << ", capacity " << a.capacity() << endl;
}

Будет выведено:

size: 1, capacity 1
size: 2, capacity 2
size: 3, capacity 4
size: 4, capacity 4
size: 5, capacity 8
size: 6, capacity 8
size: 7, capacity 8
size: 8, capacity 8
size: 9, capacity 16
size: 10, capacity 16

При инициализации vector по-умолчанию начальный размер (который capacity) равен 0, однако многие использующие его внутри структуры часто резервируют какой-то начальный размер — например, 16 или 32 элементов — чтобы сэкономить время из предположения, что там будет храниться не один элемент.

Python

В Питоне обычные списки выполняют роль расширяемых массивов.

a = [1, 2, 3]
a.append(4)