std.container.array

Этот модуль предоставляет тип Array с детерминированным использованием памяти, не зависящим от сборщика мусора, как альтернативу встроенным массивам.

Этот модуль является подмодулем std.container.

Источник

std/container/array.d

Лицензия:

Распространяется по лицензии Boost Software License, версия 1.0. (См. прилагаемый файл LICENSE_1_0.txt или копию по адресу boost.org/LICENSE_1_0.txt).

Авторы:

Андрей Александреску

Примеры:

auto arr = Array!int(0, 2, 3);
writeln(arr[0]); // 0
writeln(arr.front); // 0
writeln(arr.back); // 3

// reserve space
arr.reserve(1000);
writeln(arr.length); // 3
assert(arr.capacity >= 1000);

// insertion
arr.insertBefore(arr[1..$], 1);
writeln(arr.front); // 0
writeln(arr.length); // 4

arr.insertBack(4);
writeln(arr.back); // 4
writeln(arr.length); // 5

// set elements
arr[1] *= 42;
writeln(arr[1]); // 42

Примеры:

import std.algorithm.comparison : equal;
auto arr = Array!int(1, 2, 3);

// concat
auto b = Array!int(11, 12, 13);
arr ~= b;
writeln(arr.length); // 6

// slicing
assert(arr[1 .. 3].equal([2, 3]));

// remove
arr.linearRemove(arr[1 .. 3]);
assert(arr[0 .. 2].equal([1, 11]));

Примеры:

Array!bool эффективно объединяет значения, выделяя по одному биту на элемент

Array!bool arr;
arr.insert([true, true, false, true, false]);
writeln(arr.length); // 5

struct Array(T) if (!is(immutable(T) == immutable(bool)));

Тип массива с детерминированным управлением памятью. Память, выделенная для массива, освобождается как можно скорее; она не зависит от сборщика мусора. Array использует malloc, realloc и free для управления собственной памятью.

Это означает, что указатели на элементы Array станут висящими, как только элемент будет удален из Array. С другой стороны, память, выделенная Array, будет просматриваться сборщиком мусора, а объекты, управляемые сборщиком мусора, на которые ссылается Array, будут поддерживаться живыми.

Примечание

При использовании Array с функциями на основе диапазонов, такими как те, что в std.algorithm, Array необходимо разбить на диапазоны (например, использовать array[].map! вместо array.map!). Сам контейнер не является диапазоном.

Примеры:

typeof может дать неправильный результат в случае классов, определяющих оператор opCall https://issues.dlang.org/show_bug.cgi?id=20589 деструктор std.container.array.Array!(MyClass).Array.~this имеет @system, поэтому юнит-тест тоже должен быть @system

class MyClass
{
    T opCall(T)(T p)
    {
        return p;
    }
}

Array!MyClass arr;

this(U)(U[] values...)
Constraints: if (isImplicitlyConvertible!(U, T));

Конструктор, принимающий несколько элементов.

this(Range)(Range r)
Constraints: if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]));

Конструктор, принимающий диапазон входных данных.

const bool opEquals(const Array rhs);

const bool opEquals(ref const Array rhs);

Сравнение на равенство.

alias Range = RangeT!Array;

alias ConstRange = RangeT!(const(Array));

alias ImmutableRange = RangeT!(immutable(Array));

Определяет основной диапазон массива, который является диапазоном с произвольным доступом.

ConstRange — это вариант с const элементами. ImmutableRange — это вариант с immutable элементами.

@property Array dup();

Создаёт дубликат массива. Элементы сами не дублируются транзитивно.

Сложность

Ο(length).

const @property bool empty();

Возвращает:

true тогда и только тогда, когда массив не содержит элементов.

Сложность

Ο(1)

const @property size_t length();

const size_t opDollar();

Возвращает:

Количество элементов в массиве.

Сложность

Ο(1).

@property size_t capacity();

Возвращает:

Максимальное количество элементов, которое массив может хранить без перераспределения памяти и аннулирования итераторов при вставке.

Сложность

Ο(1)

void reserve(size_t elements);

Обеспечивает достаточную ёмкость для размещения e элементов. Если e < capacity, этот метод ничего не делает.

Постусловие

capacity >= e

Примечание

Если ёмкость увеличивается, следует предположить, что все итераторы на элементы аннулируются.

Сложность

не более Ο(length) если e > capacity, иначе Ο(1).

Range opSlice();

Возвращает:

Диапазон, который итерирует по элементам массива в прямом порядке.

Сложность

Ο(1)

Range opSlice(size_t i, size_t j);

Возвращает:

Диапазон, который итерирует по элементам массива с индекса i до (исключая) индекса j.

Предварительное условие

i <= j && j <= length

Сложность

Ο(1)

inout @property ref inout(T) front();

Возвращает:

Первый элемент массива.

Предварительное условие

empty == false

Сложность

Ο(1)

inout @property ref inout(T) back();

Возвращает:

Последний элемент массива.

Предварительное условие

empty == false

Сложность

Ο(1)

inout ref inout(T) opIndex(size_t i);

Возвращает:

Элемент или ссылку на элемент по указанному индексу.

Предварительное условие

i < length

Сложность

Ο(1)

void opSliceAssign(T value);

void opSliceAssign(T value, size_t i, size_t j);

void opSliceUnary(string op)()
Constraints: if (op == "++" || op == "--");

void opSliceUnary(string op)(size_t i, size_t j)
Constraints: if (op == "++" || op == "--");

void opSliceOpAssign(string op)(T value);

void opSliceOpAssign(string op)(T value, size_t i, size_t j);

Операторы срезов, выполняющие указанную операцию над всем слайсом.

Предварительное условие

i < j && j < length

Сложность

Ο(slice.length)

Array opBinary(string op, Stuff)(Stuff stuff)
Constraints: if (op == "~");

Возвращает:

Новый массив, являющийся конкатенацией this и его аргумента.

Сложность

Ο(length + m), где m — количество элементов в stuff.

void opOpAssign(string op, Stuff)(auto ref Stuff stuff)
Constraints: if (op == "~");

Перенаправляет к insertBack.

void clear();

Удаляет все элементы из массива и освобождает выделенную память.

Постусловие

empty == true && capacity == 0

Сложность

Ο(length)

@property void length(size_t newLength);

Устанавливает количество элементов в массиве на newLength. Если newLength больше, чем length, новые элементы добавляются в конец массива и инициализируются T.init.

Сложность

Гарантированно Ο(abs(length - newLength)) если capacity >= newLength. Если capacity < newLength наихудший случай — Ο(newLength).

Постусловие

length == newLength

T removeAny();

alias stableRemoveAny = removeAny;

Удаляет последний элемент из массива и возвращает его. Стабильная и нестабильная версии ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не аннулируются.

Предварительное условие

empty == false

Возвращает:

Удаленный элемент.

Сложность

Ο(1).

Выбрасывает:

Exception если массив пуст.

size_t insertBack(Stuff)(Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

alias insert = insertBack;

Вставляет указанные элементы в конец массива. stuff может быть значением, преобразуемым в T или диапазоном объектов, преобразуемых в T.

Возвращает:

Количество вставленных элементов.

Сложность

Ο(length + m) если происходит перераспределение, иначе Ο(m), где m — количество элементов в stuff.

void removeBack();

alias stableRemoveBack = removeBack;

Удаляет значение из конца массива. Стабильная и нестабильная версии ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не аннулируются.

Предварительное условие

empty == false

Сложность

Ο(1).

Выбрасывает:

Exception если массив пуст.

size_t removeBack(size_t howMany);

alias stableRemoveBack = removeBack;

Удаляет howMany значений из конца массива. В отличие от предыдущих версий, эти функции не выбрасывают исключение, если не удалось удалить howMany элементов. Вместо этого, если howMany > n, все элементы удаляются. Возвращаемое значение — эффективное количество удаленных элементов. Стабильная и нестабильная версии ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не аннулируются.

Возвращает:

Количество удаленных элементов.

Сложность

Ο(howMany).

size_t insertBefore(Stuff)(Range r, Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T));

size_t insertBefore(Stuff)(Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range r, Stuff stuff);

size_t replace(Stuff)(Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t replace(Stuff)(Range r, Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T));

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

Возвращает:

Количество вставленных значений.

Сложность

Ο(length + m), где m — длина stuff.

Выбрасывает:

Exception если r не является диапазоном, извлечённым из этого массива.

Диапазон linearRemove(Range r);

Удаляет все элементы, принадлежащие r, которое должно быть диапазоном, полученным изначально из этого массива.

Возвращает:

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

Сложность

Ο(length)

Выбрасывает:

Exception если r не является допустимым диапазоном, извлечённым из этого массива.

структура Array(T) если (is(immutable(T) == immutable(bool)));

Массив, специализированный для bool. Эффективно упаковывает значения, выделяя один бит на элемент.

struct Диапазон;

Определяет основной диапазон массива.

@property Диапазон save();

@property bool пустой();

@property T первый();

@property void первый(bool value);

T переместитьВперед();

void удалитьСпереди();

@property T последний();

@property void последний(bool value);

T переместитьНазад();

void удалитьСзади();

T индекс(size_t i);

void присвоитьИндекс(T value, size_t i);

T переместитьВ(size_t i);

const @property size_t длина();

Диапазон срез(size_t low, size_t high);

Примитивы диапазона

@property bool пустой();

Свойство, возвращающее true тогда и только тогда, когда массив не содержит элементов.

Сложность

Ο(1)

@property Array копия();

Возвращает:

Копию массива.

Сложность

Ο(length).

const @property size_t длина();

Возвращает количество элементов в массиве.

Сложность

Ο(1).

@property size_t емкость();

Возвращает:

Максимальное количество элементов, которое массив может хранить без перераспределения памяти и инвалидации итераторов при вставке.

Сложность

Ο(1).

void зарезервировать(size_t e);

Обеспечивает достаточную емкость для размещения e элементов. Если e < capacity, этот метод ничего не делает.

Постусловие

capacity >= e

Примечание

Если емкость увеличивается, все итераторы элементов считаются недействительными.

Сложность

не более Ο(length) если e > capacity, иначе Ο(1).

Диапазон срез();

Возвращает:

Диапазон, который перебирает все элементы массива в прямом порядке.

Сложность

Ο(1)

Диапазон срез(size_t a, size_t b);

Возвращает:

Диапазон, который итерирует по массиву между двумя заданными позициями.

Сложность

Ο(1)

@property bool первый();

@property void первый(bool value);

Возвращает:

Первый элемент массива.

Предварительное условие

empty == false

Сложность

Ο(1)

Выбрасывает:

Exception если массив пуст.

@property bool последний();

@property void последний(bool value);

Возвращает:

Последний элемент массива.

Предварительное условие

empty == false

Сложность

Ο(1)

Выбрасывает:

Exception если массив пуст.

bool индекс(size_t i);

void присвоитьИндекс(bool value, size_t i);

void индексОперацияПрисвоения(string op)(bool value, size_t i);

T переместитьВ(size_t i);

Операторы индексирования, возвращающие или изменяющие значение по указанному индексу.

Предварительное условие

i < length

Сложность

Ο(1)

Array!bool бинарнаяОперация(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~");

Возвращает:

Новый массив, который является конкатенацией this и его аргумента.

Сложность

Ο(length + m), где m - количество элементов в stuff.

Array!bool операцияПрисвоения(string op, Stuff)(Stuff stuff)
Constraints: if (op == "~");

Перенаправляет на insertBack.

void очистить();

Удаляет все элементы из массива и освобождает выделенную память.

Постусловие

empty == true && capacity == 0

Сложность

Ο(length)

@property void длина(size_t newLength);

Устанавливает количество элементов в массиве на newLength. Если newLength больше length, новые элементы добавляются в конец массива и инициализируются значением false.

Сложность

Гарантированно Ο(abs(length - newLength)) если capacity >= newLength. Если capacity < newLength, худший случай - Ο(newLength).

Постусловие

length == newLength

T удалитьЛюбой();

alias стабильноеУдалитьЛюбой = removeAny;

Удаляет последний элемент из массива и возвращает его. Стабильная и нестабильная версии ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не станут недействительными.

Предварительное условие

empty == false

Возвращает:

Удалённый элемент.

Сложность

Ο(1).

Выбрасывает:

Exception если массив пуст.

size_t вставитьСзади(Stuff)(Stuff stuff)
Constraints: if (is(Stuff : bool));

size_t вставитьСзади(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && is(ElementType!Stuff : bool));

alias стабильнаяВставкаСзади = insertBack;

alias вставить = insertBack;

alias стабильнаяВставка = insertBack;

alias линейнаяВставка = insertBack;

alias стабильнаяЛинейнаяВставка = insertBack;

Вставляет указанные элементы в конец массива. stuff может быть значением, преобразуемым в bool или диапазоном объектов, преобразуемых в bool.

Возвращает:

Количество вставленных элементов.

Сложность

Ο(length + m) если происходит перераспределение, иначе Ο(m), где m - количество элементов в stuff.

void удалитьСзади();

alias стабильноеУдалитьСзади = removeBack;

Удаляет значение из конца массива. Обе версии, стабильная и нестабильная, ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не станут недействительными.

Предварительное условие

empty == false

Сложность

Ο(1).

Выбрасывает:

Exception если массив пуст.

size_t удалитьСзади(size_t howMany);

alias стабильноеУдалитьСзади = removeBack;

Удаляет howMany значений с конца массива. В отличие от непараметризованных версий выше, эти функции не выбрасывают исключения, если не смогли удалить howMany элементов. Вместо этого, если howMany > n, удаляются все элементы. Возвращаемое значение - эффективное количество удалённых элементов. Стабильная и нестабильная версии ведут себя одинаково и гарантируют, что диапазоны, итерирующие по массиву, никогда не станут недействительными.

Возвращает:

Количество удалённых элементов.

Сложность

Ο(howMany).

size_t вставитьПеред(Stuff)(Range r, Stuff stuff);

alias стабильнаяВставкаПеред = insertBefore;

size_t вставитьПосле(Stuff)(Range r, Stuff stuff);

alias стабильнаяВставкаПосле = insertAfter;

size_t заменить(Stuff)(Range r, Stuff stuff)
Constraints: if (is(Stuff : bool));

alias стабильнаяЗамена = replace;

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

Возвращает:

Количество вставленных значений.

Сложность

Ο(length + m), где m — длина stuff.

Диапазон linearRemove(Диапазон r);

Удаляет все элементы, принадлежащие r, который должен быть диапазоном, изначально полученным из этого массива.

Возвращает:

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

Сложность

Ο(length)