Динамические массивы и списки
Когда мы обсуждали массивы, мы говорили, что это структуры данных, размер которых известен на этапе компиляции и размер является частью их типа. Однако, как вы могли догадаться, довольно часто возникает необходимость в структуре данных, похожей на массив, но с возможностью хранения произвольного количества элементов.
Именно для таких случаев во многих языках программирования существуют массивы переменной длины. Например, в Rust это Vec, в C++ — std::vector, в Go — slice. В языке Zig тоже есть подобная структура, и называется она ArrayList.
Динамические массивы одна из самых полезных структур данных, так как её использование требуется во многих практических задачах, где нам надо хранить произвольный список объектов заданного типа. Давайте рассмотрим, как динамические массивы работают в общем виде.
Динамические массивы
Как мы знаем, для управления обычным массивом данных произвольного типа языку программирования достаточно трех параметров: адреса начала массива, типа сохраняемого объекта и количество элементов, хранимых в массиве. Однако, если массив имеет переменную длину, то во многих языках к этим параметрам добавляется ещё один — ёмкость (capacity), которая указывает на максимальное количество элементов, которое может храниться в массиве без перераспределения памяти.
Зачем же нужен этот третий параметр и как всё это работает “под капотом”? И что за перераспределение памяти? Давайте разберёмся.
Поскольку наш массив является динамическим, как мы уже знаем, он размещается в куче, а не на стеке. Это связано с тем, что размер динамического массива может изменяться во время выполнения программы, тогда как стек имеет фиксированный объём, заданный на этапе компиляции, и не может быть расширен во время работы программы.
Для хранения элементов массива в куче выделяется непрерывный блок памяти, в который по порядку записываются элементы. Если вдруг выделенного блока памяти становится недостаточно, чтобы вместить все элементы, выделяется новый, более крупный блок. Существующие данные копируются в этот новый сегмент памяти, после чего старый сегмент освобождается и можно продолжать добавление новых элементов — до следующего момента, когда снова понадобится расширение сегмента памяти:
Как видно из примера, изначально наш массив содержит всего три элемента, а его ёмкость составляет четыре. Мы начинаем добавлять новые элементы, и как только количество элементов достигнет текущей ёмкости, при попытке добавить следующий элемент произойдёт автоматическое расширение массива — как правило, его размер удваивается. При этом все существующие данные копируются в новое место в памяти, а старая область памяти освобождается. В целом, по такому принципу работают динамические массивы во многих языках программирования.
Давайте теперь посмотрим как работать с динамическим массивом в языке программирования Zig.
Создание и инициализация ArrayList
Чтобы создать динамический массив в Zig, сначала необходимо создать аллокатор, который будет использоваться для выделения памяти. Как мы уже знаем, в Zig нет скрытых аллокаций — вся работа с памятью происходит явно через передаваемый вами аллокатор.
Далее, для создания динамического массива нужно передать созданный аллокатор и тип элемента, который будет храниться в массиве:
const std = @import("std");
const User = struct {
id: usize,
name: []const u8,
};
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = std.ArrayList(User).init(allocator);
defer list.deinit();
std.debug.print("Size {d}\n", .{list.items.len});
std.debug.print("Capacity {d}\n", .{list.capacity});
}
Если мы запустим наш код, то получим вывод:
Size 0
Capacity 0
Как мы видим по умолчанию емкость нашего массива равно 0, т.е. Zig не стал выделять память для нашего массива, пока мы не добавим в него элементы. Как только мы попытаемся добавить элемент в массив, Zig автоматически увеличит емкость массива, причем размер емкости будет выбран на основании типа сохраняемых данных и может быть разным для различных типов. Если мы знаем сколько элементов максимально будет хранится в нашем массиве, то мы можем задать вручную начальную емкость нашего массива используя метод initCapacity:
const std = @import("std");
const User = struct {
id: usize,
name: []const u8,
};
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list1 = std.ArrayList(User).init(allocator);
defer list1.deinit();
try list1.append(User{ .id = 1, .name = "Alice" });
std.debug.print("Size {d}\n", .{list1.items.len});
std.debug.print("Capacity {d}\n", .{list1.capacity});
var list2 = std.ArrayList(u8).init(allocator);
defer list2.deinit();
try list2.append(1);
std.debug.print("Size {d}\n", .{list2.items.len});
std.debug.print("Capacity {d}\n", .{list2.capacity});
var list3 = try std.ArrayList(u8).initCapacity(allocator, 30);
defer list3.deinit();
std.debug.print("Size {d}\n", .{list3.items.len});
std.debug.print("Capacity {d}\n", .{list3.capacity});
}
Если запустить данный код, то мы получим вывод:
Size 1
Capacity 5
Size 1
Capacity 128
Size 0
Capacity 30
Как можно заметить, при использовании нашей структуры User в качестве элемента массива компилятор установил начальную ёмкость массива равной 5. В случае же с типом данных u8 компилятор определил начальную ёмкость как 128. Из этого можно сделать вывод, что у вас нет гарантий того, что компилятор будет каждый раз выделять одинаковое количество слотов в массиве для разных типов данных. Поскольку операция изменения ёмкости массива довольно затратна, считается хорошей практикой задавать начальное значение ёмкости вручную, чтобы избежать лишних перераспределений памяти и перемещений данных.
Работа с динамическим массивом
Для добавления значений в массив в Zig предусмотрено несколько методов, таких как append и insert. Метод append добавляет элемент в конец массива и является самым эффективным способом добавления, поскольку работает за константное время — O(1).
Метод insert, напротив, позволяет вставить элемент в произвольную позицию внутри массива. Однако такая операция более затратна: при вставке все элементы, находящиеся после указанной позиции, сдвигаются, чтобы освободить место. В худшем случае это может привести к временной сложности O(n), поэтому используйте этот метод только если вам важно сохранять порядок элементов.
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = try std.ArrayList(u8).initCapacity(allocator, 10);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.append(5);
// Вставка через insert приведет к сдвигу элементов 3, 4, 5
try list.insert(2, 10);
for (list.items) |item| {
std.debug.print("Element: {}\n", .{item});
}
}
Если нам нужно вставить сразу несколько элементов, например добавить массив из элементов, то вставлять по одному не очень эффективно и можно использовать метод appendSlice или insertSlice. Первый метод вставит добавляемые элементы в конец массива, а второй вставит элементы в указанное место, а оставшиеся элементы сдвинет на длину вставляемого среза:
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = try std.ArrayList(u8).initCapacity(allocator, 10);
defer list.deinit();
try list.appendSlice(&[5]u8{ 1, 2, 3, 4, 5 });
// Вставка через insert приведет к сдвигу элементов 3, 4, 5
try list.insert(2, 10);
for (list.items) |item| {
std.debug.print("Element: {}\n", .{item});
}
}
В данном примере мы заменили множественные вызовы метода append, на еденичный вызов метода appendSlice, куда передали срез из наших 5 элементов.
Удаление элементов из массива
Для того, чтобы извлечь элемент из массива у нас есть также два метода - pop и orderedRemove. Первый метод, симметричен методу append - он удаляет последний элемент из нашего массива и возвращает удаленный элемент. Если наш массив пуст, то метод pop просто вернет null. Второй метод orderedRemove позволяет удалить элемент с конкретной позиции и также симметричен нашему методу insert. При использование метода orderedRemove он удаляет элемент с указанной позиции, сдвигает все оставшиеся элементы влево и возвращает нам удаленный элемент. Если вам нужно удалять элементы с определенных индексов, но порядок элементов для вас не важен, то используйте метод swapRemove. Он работает также эффективно как и pop и не требует перемещения элементов в массиве как метод orderedRemove. Однако у него есть один важный момент - внутри этот метод при удалении элемента перемещает на его позицию последний элемент массива, что явным образом нарушает порядок.
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = try std.ArrayList(u8).initCapacity(allocator, 10);
defer list.deinit();
try list.appendSlice(&[5]u8{ 1, 2, 3, 4, 5 });
const elem1 = list.pop();
if (elem1) |el| {
std.debug.print("Removed element: {d}\n", .{el});
}
for (list.items) |item| {
std.debug.print("{d} ", .{item});
}
std.debug.print("\n", .{});
const elem2 = list.orderedRemove(2);
std.debug.print("Removed element: {d}\n", .{elem2});
for (list.items) |item| {
std.debug.print("{d} ", .{item});
}
std.debug.print("\n", .{});
try list.append(10);
try list.append(20);
std.debug.print("До swapRemove: ", .{});
for (list.items) |item| {
std.debug.print("{d} ", .{item});
}
std.debug.print("\n", .{});
const elem3 = list.swapRemove(1);
std.debug.print("Removed element: {d}\n", .{elem3});
std.debug.print("После swapRemove: ", .{});
for (list.items) |item| {
std.debug.print("{d} ", .{item});
}
std.debug.print("\n", .{});
}
Данный код выведет нам:
Removed element: 5
1 2 3 4
Removed element: 3
1 2 4
До swapRemove: 1 2 4 10 20
Removed element: 2
После swapRemove: 1 20 4 10
Как мы видим использование orderedRemove сохранило нам порядок наших элементов, но при этом это и довольно завтратный метод, который может в худшем случае приводить к O(n). А вот swapRemove нарушает порядок, перемещая последний элемент на место удаляемого, но работает за O(1).
Очистка массива
Если вам нужно удалить все элементы из массива, есть два основных метода:
// Очищает содержимое, не освобождая память
list.clearRetainingCapacity();
// Очищает содержимое и освобождает память
list.clearAndFree();
Метод clearRetainingCapacity просто сбрасывает размер до нуля, но сохраняет выделенную память. Это полезно, если вы планируете повторно использовать массив для хранения новых данных.
Метод clearAndFree полностью освобождает выделенную память. Используйте его, когда вам нужно минимизировать использование памяти.
Использование ArrayList через Writer
Иногда возникает задача получать данные по сети из какого-либо источника и сохранять их, используя универсальный интерфейс Writer, не задумываясь о том, какая именно структура данных стоит за этим интерфейсом. Для этого у типа ArrayList есть два метода: writer и fixedWriter. Оба возвращают интерфейс Writer, но между ними есть важное различие.
Метод writer возвращает интерфейс Writer, который при необходимости автоматически увеличивает размер массива. Метод fixedWriter, напротив, возвращает интерфейс Writer, который не расширяет массив при нехватке памяти — вместо этого он вернёт ошибку error.OutOfMemory.
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = std.ArrayList(u8).init(allocator);
defer list.deinit();
var wrt = list.writer();
try wrt.print("Hello world", .{});
for (list.items) |item| {
std.debug.print("{c}", .{item});
}
std.debug.print("\n", .{});
// Пример использования fixedWriter
var fixed_list = try std.ArrayList(u8).initCapacity(allocator, 5);
defer fixed_list.deinit();
var fixed_wrt = fixed_list.fixedWriter();
// Это успешно запишет 5 байт
try fixed_wrt.writeAll("Hello");
// Это вернет ошибку OutOfMemory, так как ёмкость массива ограничена 5 байтами
fixed_wrt.writeAll(" world") catch |err| {
std.debug.print("Ошибка при записи: {s}\n", .{@errorName(err)});
};
std.debug.print("Fixed list content: ", .{});
for (fixed_list.items) |item| {
std.debug.print("{c}", .{item});
}
std.debug.print("\n", .{});
}
В данном примере мы получаем из нашего списка интерфейс Writer и дальше используем методы интерфейса чтобы писать наши данные в наш динамический массив.
Внутреннее устройство ArrayList
Как вы, возможно, уже заметили, структура ArrayList по сути является обёрткой над обычным массивом, дополненной логикой для управления выделением и освобождением памяти.
Когда нам нужно получить доступ к элементам, хранящимся в ArrayList, мы можем напрямую обращаться к его полю items — это и есть внутренний массив. Через него можно итерироваться по данным или изменять их. Однако важно помнить: получать ссылки (указатели) на элементы этого массива может быть небезопасно. Если произойдёт перераспределение памяти (например, при увеличении ёмкости), массив будет перемещён, и все ранее полученные указатели станут невалидными.
Иногда бывает удобно не просто получить доступ к внутреннему массиву, но и полностью “отцепить” его от ArrayList. Это может понадобиться, например, если вы накопили нужное количество данных и хотите передать их дальше, сбросив состояние ArrayList.
Для таких случаев у структуры есть метод toOwnedSlice. Он возвращает срез с текущими данными, а внутри ArrayList создаёт новый пустой массив. Таким образом, происходит передача владения данными вызывающему коду, и теперь именно он отвечает за освобождение памяти, занятой этим срезом.
const std = @import("std");
fn to_upper(allocator: std.mem.Allocator, reader: anytype) ![]u8 {
var list = std.ArrayList(u8).init(allocator);
defer list.deinit();
while (true) {
const byte = reader.readByte() catch |err| {
if (err == error.EndOfStream) break;
return err;
};
const uppercased = if (byte >= 'a' and byte <= 'z')
byte - ('a' - 'A')
else
byte;
try list.append(uppercased);
}
// Передаем владение данными вызывающему коду
// После этого вызова list становится пустым (и deinit не освободит память)
return list.toOwnedSlice();
}
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const data = "Hello Zig!";
var stream = std.io.fixedBufferStream(data);
const upper = try to_upper(allocator, stream.reader());
defer allocator.free(upper);
std.debug.print("Result: {s}\n", .{upper});
}
В этом примере мы реализовали функцию, которая принимает на вход поток, читает из него символы, переводит их в верхний регистр и сохраняет в ArrayList. После того как все данные считаны, мы возвращаем срез, передавая владение этими данными вызывающему коду.
Такой подход особенно полезен, когда нужно сформировать данные в одной функции, а затем передать их в другую или вернуть без лишнего копирования. Метод toOwnedSlice() позволяет эффективно передавать владение, избавляя от необходимости копировать данные и упрощая управление памятью.
MultiArrayList
Иногда возникает необходимость хранить в динамическом массиве большое количество структур, и в таких случаях важно, чтобы это было максимально эффективно — как по использованию памяти, так и по скорости обработки данных.
Существует приём, позволяющий эффективно хранить большое количество структур. Он не является уникальным для Zig и используется во многих языках программирования — это техника хранения полей структур в виде отдельных массивов (так называемый Structure of Arrays, или SoA). Довольно часто такой стиль хранения данных используется в игровых движках.
Суть этого подхода в том, что вместо хранения массива структур, мы храним по отдельному массиву для каждого поля структуры. Например, если у нас есть структура User с полями id и name, то все идентификаторы пользователей будут храниться в одном массиве, а все имена — в другом.
Такое раздельное хранение данных даёт следующие преимущества:
-
Локализация данных (Data Locality)
Если поля структуры хранятся в отдельных массивах (SoA — Structure of Arrays), то при обработке большого количества объектов процессор эффективнее использует кэш. Например, если у вас есть массив структур {x, y, z}, то при обходе только поля x остальные поля y и z загружаются в кэш без необходимости. В SoA-подходе (xs: []f32, ys: []f32, zs: []f32) кэш используется оптимальнее.
-
Векторизация (SIMD)
Современные процессоры поддерживают SIMD-инструкции (AVX, NEON и др.), которые могут обрабатывать несколько значений одновременно. SoA-расположение данных облегчает векторизацию, так как поля выровнены в памяти последовательно.
-
Экономия памяти (Packing)
При хранение структур целиком как элементов массива, компилятору может потребоватся выравнивание полей структуры по максимальному полю, что может привести к наличию пустых промежутков в области памяти занимаемой структурой. При хранении каждого поля структуры отдельно, нет необходимости выравнивать данные так как они однородны.
-
Гибкость и контроль над памятью
Zig даёт низкоуровневый контроль над памятью, и SoA-подход позволяет явно управлять распределением, выравниванием и даже ручной освобождением памяти. Полезно в высокопроизводительных сценариях (игры, симуляции, embedded-системы). Если не все поля структуры нужны в конкретном алгоритме, можно загружать только необходимые массивы, уменьшая объём используемой памяти. Также можно применять оптимизации, например, хранение bool как битовых флагов в одном u8 вместо отдельных bool.
Для того чтобы создать такую структуру хранения данных в виде массивов в Zig необходимо воспользоваться типом данных MultiArrayList. Для этого надо передать в универсальную функцию MultiArrayList тип нашей структуры, который мы хотим хранить в массиве, и она вернет нам обратно тип данных, где поля нашей структуры будут хранится в виде набора массивов:
const std = @import("std");
const User = struct {
id: usize,
name: []const u8,
};
const UserArray = std.MultiArrayList(User);
pub fn main() !void {
var gpa = std.heap.DebugAllocator(.{}).init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var users = UserArray{};
defer users.deinit(allocator);
try users.append(allocator, .{ .id = 1, .name = "Alice" });
try users.append(allocator, .{ .id = 2, .name = "Bob" });
try users.append(allocator, .{ .id = 3, .name = "Karoll" });
var users_slice = users.slice();
for (users_slice.items(.id), users_slice.items(.name)) |*id, *name| {
std.debug.print("User {d} with name {s}\n", .{ id.*, name.* });
}
}
Данный код выведет:
User 1 with name Alice
User 2 with name Bob
User 3 with name Karoll
Первое заметное отличие MultiArrayList от привычного ArrayList заключается в том, что теперь при работе с этим типом данных мы явно передаём аллокатор. Это происходит как при добавлении элементов в массив users, так и при освобождении памяти с помощью вызова метода deinit.
Второй важный момент касается доступа к элементам внутри структуры. Чтобы получить значения конкретного поля, необходимо воспользоваться методом items(), передав в него имя интересующего поля. В результате вызова мы получаем срез (slice), содержащий ссылки на значения этого поля для всех элементов. Это удобно, поскольку позволяет не только итерироваться по значениям, например для вывода, но и напрямую изменять их.
Если же требуется часто работать сразу с несколькими полями, рекомендуется сначала вызвать метод slice() на экземпляре MultiArrayList, а уже затем применять к полученному объекту метод items(). Такой подход более эффективен, поскольку вызов slice() подготовит срезы на значения полей, которые будут использоваться в дальнейшем.
Однако при этом важно помнить об одной особенности: полученные срезы на значения полей становятся невалидными при любом изменении структуры MultiArrayList, которое может привести к перемещению данных в памяти (например, при добавлении новых элементов) или к изменению количества элементов в массиве. Поэтому каждый раз после изменения MultiArrayList необходимо повторно запрашивать срезы с помощью items() — это обеспечит корректный доступ к актуальным данным.
Иногда вам необходимо получить все поля структуры для конкретного элемента в массиве. Для этого вы можете использовать метод get() на экземпляре MultiArrayList, передав в него индекс элемента. Этот метод вернет вам структуру, которую вы передавали при инициализации MultiArrayList. Для того чтобы изменить конкретное значение в массиве MultiArrayList, вы можете использовать метод set(), передав в него индекс элемента и новое значение.
Списки (SinglyLinkedList и DoublyLinkedList)
Связные списки — одна из фундаментальных структур данных в программировании. Они позволяют хранить элементы в произвольном порядке и обеспечивают быструю вставку и удаление элементов в любом месте списка — зачастую за константное время. Однако, как и у любой структуры данных, у связных списков есть свои ограничения: операции поиска элемента требуют линейного времени (O(n)), что может быть неэффективно при работе с большими объёмами данных.
Прежде чем перейти к использованию связанных списков в Zig, давайте сначала рассмотрим, что собой представляет эта структура данных в общем.
Основная идея построения связных списков заключается в использовании указателей для хранения ссылок на следующий элемент в списке. Каждый элемент содержит данные и указатель на следующий элемент. В результате элементы списка, как правило, располагаются не в непрерывном блоке памяти, а разбросаны по разным её участкам.
С одной стороны, такой способ хранения позволяет не беспокоиться о том, что выделенного сегмента памяти может не хватить и придётся перемещать данные в новое место. С другой стороны, разрозненное расположение элементов снижает эффективность использования кэш-памяти процессора и затрудняет применение векторных инструкций.
Схематично связный список можно представить следующим образом:
Как мы видим, у нас есть указатель на начало списка (head) и указатель на конец списка (tail). Первый нужен для того, чтобы можно было пройтись по списку и найти нужный элемент, а второй — чтобы быстро добавлять новые элементы в конец списка.
Связанные списки бывают односвязными и двусвязными. На рисунке изображён односвязный список, в котором каждый элемент содержит указатель только на следующий элемент. В отличие от него, двусвязный список содержит также указатель на предыдущий элемент, что позволяет быстро перемещаться по списку в обе стороны.
В языке Zig списки представлены двумя типами данных: SinglyLinkedList и DoublyLinkedList. Как и многие другие структуры в Zig, это обобщённые (generic) функции, которые при вызове возвращают новый тип данных. Этот тип представляет собой связанный список, хранящий элементы указанного при вызове типа.
Давайте рассмотрим пример использования двусвязного списка, а заодно посмотрим, какие методы предоставляет эта структура:
const std = @import("std");
const allocator = std.heap.page_allocator;
const History = std.DoublyLinkedList([]const u8);
pub fn main() !void {
var history = History{};
// Добавляем страницы в историю
const google = try allocator.create(History.Node);
google.data = "https://google.com";
history.append(google);
const yahoo = try allocator.create(History.Node);
yahoo.data = "https://yahoo.com";
history.append(yahoo);
const zig = try allocator.create(History.Node);
zig.data = "https://ziglang.org";
history.append(zig);
// Вывод истории
var curr = history.first;
while (curr != null) {
std.debug.print("Page: {s}\n", .{curr.?.data});
curr = curr.?.next;
}
std.debug.print("\n", .{});
// Удаление из истории
_ = history.remove(yahoo);
allocator.destroy(yahoo);
// Вывод истории
curr = history.first;
while (curr != null) {
std.debug.print("Page: {s}\n", .{curr.?.data});
curr = curr.?.next;
}
std.debug.print("\n", .{});
}
Наш код выведет:
Page: https://google.com
Page: https://yahoo.com
Page: https://ziglang.org
Page: https://google.com
Page: https://ziglang.org
В нашем примере мы храним историю посещённых страниц в виде связанного списка. Каждый узел списка содержит URL страницы и ссылку на следующий узел. Чтобы добавить новый элемент, мы сначала создаём узел с указанным URL, а затем добавляем его в конец списка с помощью метода append.
Также в списке доступен метод prepend, который позволяет добавлять элемент в начало списка, а не в конец. Если необходимо вставить элемент в середину списка — после какого-либо узла — сначала нужно найти этот узел, а затем вызвать метод insertAfter, передав в него как сам узел, после которого нужно вставить, так и новый элемент.
В примере видно, что для итерации по элементам списка мы используем цикл while, который проходит по всем узлам, пока не встретит нулевой указатель на следующий элемент. Это довольно распространённый способ перебора элементов связанного списка.
Если нужно удалить элемент, сначала следует найти нужный узел, а затем вызвать метод remove, передав в него тот самый узел, который требуется удалить.
В данном примере используется двусвязный список, однако мы вполне могли бы использовать и односвязный. Выбор между односвязным и двусвязным списком зависит от конкретной задачи: односвязный проще и экономичнее по памяти, тогда как двусвязный предоставляет больше гибкости при перемещении по списку.
Заключение
В этой главе мы познакомились с динамическими массивами и списками в Zig — гибкими структурами данных, которые позволяют хранить произвольное количество элементов одного типа. Мы рассмотрели две основные реализации динамических массивов - ArrayList и MultiArrayList, а также реализацию связанного списка - SinglyLinkedList и DoublyLinkedList.
ArrayList представляет собой классический динамический массив, аналогичный std::vector в C++ или Vec в Rust. Он автоматически увеличивает свою ёмкость при добавлении новых элементов, что делает его удобным инструментом для решения множества задач — особенно в тех случаях, когда важен порядок элементов и требуется, чтобы они располагались как можно ближе друг к другу в памяти. Это способствует более эффективной работе кэширования и векторных инструкций.
MultiArrayList предлагает альтернативный подход к хранению структур данных, известный как “Structure of Arrays” (SoA). Вместо хранения массива структур, он хранит структуру из массивов для каждого поля. Такой подход обеспечивает лучшую локализацию данных в памяти, что может значительно повысить производительность при обработке больших объёмов данных, особенно в сценариях, где важна эффективность использования кэша процессора и возможности SIMD-инструкций.
Если для вас важен порядок элементов, но не принципиально их хранение в непрерывном участке памяти, вы можете использовать связанный список, у которого есть свои преимущества и недостатки. Например, объединение двух связанных списков — это очень “дешёвая” операция с точки зрения производительности, тогда как для динамических массивов аналогичная операция может потребовать копирования элементов из двух массивов в третий.