Коллекции: ArrayList и HashMap

На столе есть лента записей по порядку и картотека по фамилии. Лента удобна, когда нужно просмотреть всё от первого до последнего. Картотека удобна, когда требуется быстро найти конкретную фамилию. Массив с фиксированной длиной не подходит, если записей становится больше во время работы.

Сегодня добавим числа в растущий список и посчитаем повторения слов в карте. У обеих коллекций явно останется источник памяти.

Одна мысль урока

Коллекция выбирается по способу доступа, а её рост требует явной памяти и уборки.

Опора из прошлого урока: Строки и работа с UTF-8.

От картинки к записи

ArrayList

похож на массив, но количество элементов может расти. В Zig 0.16 начинаем с var list: std.ArrayList(u16) = .empty. Аллокатор не хранится внутри списка: передаём его в append, deinit и другие операции, которым он нужен.

append(allocator, value) добавляет элемент в конец и может вернуть ошибку. Количество существующих элементов находится в list.items.len. Вместимость служебного хранилища может быть больше этой длины. Нельзя читать незанятые места только потому, что коллекция заранее получила под них память.

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

HashMap

отвечает на другой вопрос: какое значение связано с этим ключом? Хэш это вычисленный из ключа признак для выбора места поиска; совпадения хэша возможны, поэтому реализация также проверяет сам ключ. Для строк стандартная библиотека предоставляет StringHashMap.

В примере берём std.StringHashMap(u32).init(allocator). Эта управляемая форма карты хранит выбранный аллокатор внутри, поэтому её put и deinit выглядят иначе, чем операции ArrayList. Сходство названий коллекций не означает полностью одинаковый API. Для собственной программы выбирай одну форму осознанно и сверяй её с версией библиотеки.

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

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

Обе коллекции нужно уничтожить после работы. defer list.deinit(allocator) и defer counts.deinit() стоят рядом с созданием. Если append или put вернут ошибку, уже полученное хранилище не потеряется. Это тот же договор ресурсов, который мы разобрали отдельно, теперь применённый к готовым контейнерам.