#
Глава VII. Обобщённые структуры данных
В предыдущей главе мы сконструировали минималистичный динамический
массив, который назывался IntList. Применение этой структуры состояло в
том, чтобы хранить переменное количество целых чисел. И, хотя сами
алгоритмы, которые мы использовали, сработали бы для любого типа данных,
наша реализация была жёстко привязана к типу i64. Добро пожаловать в
обобщённые структуры данных (generics), которые нужны для того, чтобы
абстрагировать алгоритмы от конкретных типов данных.
В многих языках такого рода структуры реализованы при помощи специального
синтаксиса и особых правил. В Zig, напротив, обобщённые структуры данных
не столько специфическая особенность, сколько демонстрация того, что
умеет делать компилятор. Конкретно, работа с обобщёными структурами
данных предполагает умелое использование метапрограммирования при помощи
comptime.
Начнём с (немного дурацкого) примера, только ради того, чтобы хоть
немного освоиться с этим пока загадочным comptime:
const std = @import("std");
pub fn main() !void {
var arr: IntArray(3) = undefined;
arr[0] = 1;
arr[1] = 10;
arr[2] = 100;
std.debug.print("{any}\n", .{arr});
}
fn IntArray(comptime length: usize) type {
return [length]i64;
}Эта программа напечатает { 1, 10, 100 }, что не особо интересно. А
интересно тут то, что функция IntArray возвращает type, то есть
тип. И поэтому, кстати, имя функции написано в PascalCase, а не в
camelCase. Далее, эта функция возвращает не какой-то тип "вообще", этот
тип основан на параметре, переданном в функцию, который помечен словом
comptime. Этот код вообще только благодаря этому и работает. Такая
запись (comptime length: usize) обязывает каждого, кто вызывает эту
функцию передать значение, известное во время компиляции. Это
необходимо, потому что наша функция возвращает тип, а типы должны быть
известны во время компиляции (напомним, что Zig это язык со статической
типизацией).
Это может показаться странным, но тип переменной arr тут
это реально IntArray(3). Это такой же тип, как и любой другой.
Функция может возвратить любой тип, не только скалярные типы и массивы. Например, она может возвратить структуру:
const std = @import("std");
pub fn main() !void {
var arr: IntArray(3) = undefined;
arr.items[0] = 1;
arr.items[1] = 10;
arr.items[2] = 100;
std.debug.print("{any}\n", .{arr.items});
}
fn IntArray(comptime length: usize) type {
return struct {
items: [length]i64,
};
}Можно сделать ещё изящнее:
const std = @import("std");
pub fn main() !void {
var arr = IntArray(3).init();
arr.items[0] = 1;
arr.items[1] = 10;
arr.items[2] = 100;
std.debug.print("{any}\n", .{arr.items});
}
fn IntArray(comptime length: usize) type {
return struct {
items: [length]i64,
fn init() IntArray(length) {
return .{
.items = undefined,
};
}
};
}На первый взгляд, тут ничего "более изящного" нет. Однако, помимо того, что тут структура вложена в функцию и не имеет имени, она выглядит как любая другая структура, которые мы уже видели ранее, то есть у неё есть поля, есть методы. Ну, вы знаете, как говорят - если что-то выглядит как утка... тут то же самое, это что-то выглядит, плавает и крякает как обычная структура, потому что она и есть структура.
Мы идём таким извилистым путём ради того, чтобы получше освоиться с функциями, которые возвращают тип и соответствующим синтаксисом. Чтобы подобраться к какой-то более типичной обобщённой структуре данных, нам нужно сделать ещё одно небольшое изменение: помимо того, что наша функция возвращает тип, она должна также и принимать его в качестве параметра:
fn List(comptime T: type) type {
return struct {
pos: usize,
items: []T,
allocator: Allocator,
fn init(allocator: Allocator) !List(T) {
return .{
.pos = 0,
.allocator = allocator,
.items = try allocator.alloc(T, 4),
};
}
}
};Наша новая структура почти идентична структуре IntList за исключением
того, что i64 заменено на T. Именно такое название (T) может
показаться чем-то особенным, но это просто имя аргумента функции и ничего
более. Мы могли бы назвать её item_type, ничего бы по сути не
изменилось. Но, если следовать соглашениям об именовании, то лучше было
бы ItemType. Однако, традиционно для переменных с типом type
используются однобуквенные названия, например K и V для типа ключа и
типа значения применительно к, скажем, хэш-таблице.
Если вам ещё не до конца всё понятно, поглядите ещё раз на те места, где
фигурирует это наше T: items: []T и allocator.alloc(T, 4). Когда мы
хотим использовать наш обобщённый тип (для создания конкретизированного),
мы пишем
var list = try List(u32).init(allocator);
Когда такой код компилируется, компилятор создаёт новый тип, находя
каждое вхождение T и попросту заменяя его на u32. Если мы используем
List(u32) ещё раз, компилятор использует тот тип, что он уже ранее
создал, а если мы напишем какое-то другое значение для T, скажем,
List(bool) или List(User), тогда будут созданы новые типы.
Чтобы завершить реализацию нашего обобщённого списка, мы можем дословно
продублировать код из IntList, заменяя i64 на T. Вот полный рабочий
пример:
const std = @import("std");
const Allocator = std.mem.Allocator;
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var list = try List(u32).init(allocator);
defer list.deinit();
for (0..10) |i| {
try list.add(@intCast(i));
}
std.debug.print("{any}\n", .{list.items[0..list.pos]});
}
fn List(comptime T: type) type {
return struct {
pos: usize,
items: []T,
allocator: Allocator,
fn init(allocator: Allocator) !List(T) {
return .{
.pos = 0,
.allocator = allocator,
.items = try allocator.alloc(T, 4),
};
}
fn deinit(self: List(T)) void {
self.allocator.free(self.items);
}
fn add(self: *List(T), value: T) !void {
const pos = self.pos;
const len = self.items.len;
if (pos == len) {
// у нас кончилось место
// создаём новый срез, который в два раза длинне имеющегося
var larger = try self.allocator.alloc(T, len * 2);
// копируем элементы (если они есть) в новое место
@memcpy(larger[0..len], self.items);
self.allocator.free(self.items);
self.items = larger;
}
self.items[pos] = value;
self.pos = pos + 1;
}
};
}
Функция init возвращает List(T), функция add принимает аргумент
*List(T), функция deinit принимает аргумент List(T). Для нашего
простого "класса" писать полные имена типов всякий раз ещё более-менее
терпимо, но для более сложных структур это становится слегка
утомительным, особенно если у нас есть несколько параметров типа type
(например, хэш-таблица, имеющая различные типы для ключа и значения).
Здесь нам поможет встроенная функция @This(), которая возращает тип той
сущности, в которой она вызывается. Поэтому, реальная реализация List,
скорее всего, была бы сделана примерно так:
fn List(comptime T: type) type {
return struct {
pos: usize,
items: []T,
allocator: Allocator,
// добавлено
const Self = @This();
fn init(allocator: Allocator) !Self {
// ... как и было
}
fn deinit(self: Self) void {
// ... как и было
}
fn add(self: *Self, value: T) !void {
// ... как и было
}
};
}Как и T, Self не является каким-то особым словом, это просто имя
(немутабельной) переменной. И так же, как и для T, для неё используется
PascalCase, потому что это значение типа. Таким образом, вместо
List(T) мы можем везде использовать Self(ну или какое-то другое
наименование, которое нам больше нравится, например, This).
Мы могли бы сконструировать более сложные примеры, с несколькими параметрами-типами и с более сложными алгоритмами. Но, по большому счёту, базовая логика описания обобщённых структур данных никак не отличается от той, что мы видели в рассмотренном простом примере.