Массив — это набор однотипных переменных, доступ к которым осуществляется по индексу.
Динамический или расширяющийся массив — это массив, который может изменять свой размер в зависимости от количества элементов в нём.
Динамические массивы обычно используют, когда заранее предсказать размер массива сложно или невозможно. В таком контексте у динамических массивов помимо операций доступа и изменения произвольных элементов есть ещё три:
- Добавить в конец массива элемент $x$.
- Удалить последний элемент массива.
- Узнать размер массива.
При этом все операции должны выполняться за $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)