std.container.array

Переместиться к: Array

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

Исходный код: std/container/array.d

Лицензия:
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).
Авторы:
Andrei Alexandrescu
Примеры: 
auto arr = Array!int(0, 2, 3);
assert(arr[0] == 0);
assert(arr.front == 0);
assert(arr.back == 3);

// резервирование пространства
arr.reserve(1000);
assert(arr.length == 3);
assert(arr.capacity >= 1000);

// вставка
arr.insertBefore(arr[1..$], 1);
assert(arr.front == 0);
assert(arr.length == 4);

arr.insertBack(4);
assert(arr.back == 4);
assert(arr.length == 5);

// установка элементов
arr[1] *= 42;
assert(arr[1] == 42);
Примеры: 
import std.algorithm.comparison : equal;
auto arr = Array!int(1, 2, 3);

// конкатенация
auto b = Array!int(11, 12, 13);
arr ~= b;
assert(arr.length == 6);

// выделение среза
assert(arr[1..3].equal([2, 3]));

// удаление
arr.linearRemove(arr[1..3]);
assert(arr[0..2].equal([1, 11]));
Примеры:
Array!bool упаковывает значения вместе, эффективно распределяя по одному биту на элемент 
Array!bool arr;
arr.insert([true, true, false, true, false]);
assert(arr.length == 5);
struct Array(T) if (!is(Unqual!T == bool));
Тип массива с детерминированным управлением памятью. Память, распределяемая для массива, освобождается как можно скорее, не полагаясь на сборщик мусора. Array использует malloc и free для управления собственной памятью.
Это означает, что указатели на элементы Array станут висячими, как только элемент будет удалён из Array. С другой стороны, память, распределённая Array , будет сканироваться сборщиком мусора, и объекты, управляемые им, на которые есть ссылки из Array, сохранятся живыми.

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

Переместиться к: 2

this(U)(U[] values...)
if (isImplicitlyConvertible!(U, T));
Конструктор, принимающий несколько элементов
this(Stuff)(Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[]));
Конструктор, принимающий входной диапазон
const bool opEquals(const Array rhs);

const bool opEquals(ref const Array rhs);
Сравнение на равенство.

Переместиться к: 2 · back · empty · front · length · moveAt · moveBack · moveFront · opIndex · opIndexAssign · opSlice · popBack · popFront · save

alias Range = RangeT!Array;

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

alias ImmutableRange = RangeT!(immutable(Array));
Определяет первичный диапазон контейнера, который станет диапазоном с произвольным доступом.
ConstRange – это вариант с константными элементами. ImmutableRange – это вариант с неизменяемыми элементами.

Переместиться к: 2

@property Array dup();
Дублирует контейнер. Сами элементы дублируются не транзитивно.

Сложность: Ο(n).

Переместиться к: 2

const @property bool empty();
Свойство, возвращающее true тогда и только тогда, когда контейнер не имеет элементов.

Сложность: Ο(1)

Переместиться к: 2 · 3 · 4

const @property size_t length();

const size_t opDollar();
Возвращает количество элементов в контейнере.

Сложность: Ο(1).

Переместиться к: 2

@property size_t capacity();
Возвращает максимальное количество элементов, которые контейнер может сохранить без (a) распределения памяти, (b) аннулирования итераторов при вставке.

Сложность: Ο(1)

Переместиться к: 2

void reserve(size_t elements);
Гарантирует, что размер capacity (возможности) станет достаточной для размещения elements элементов.

Постусловие: capacity >= elements

Сложность: Ο(1)

Глянул я в код этого метода, в нём после распределения новой памяти туда копируется весь массив (с помощью memcpy), а затем оставшееся место заполняется нулями (с помощью memset). Эти операции никак не могут быть Ο(1)... – прим. пер.

Переместиться к: 2 · 3 · 4

Range opSlice();
Возвращает диапазон, который итерирует по элементам контейнера, в прямом порядке.

Сложность: Ο(1)

Range opSlice(size_t i, size_t j);
Возвращает диапазон, который итерирует по элементам контейнера от индекса a до (исключительно) индекса b.

Предусловие: a <= b && b <= length

Сложность: Ο(1)

Переместиться к: 2

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

Переместиться к: 2

inout @property ref inout(T) back();
Перенаправляет к opSlice().front и opSlice().back, соответсвенно.

Предусловие: !empty

Сложность: Ο(1)

Переместиться к: 2

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)()
if (op == "++" || op == "--");

void opSliceUnary(string op)(size_t i, size_t j)
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)

Переместиться к: 2

Array opBinary(string op, Stuff)(Stuff stuff)
if (op == "~");
Возвращает новый контейнер, являющийся конкатенацией этого контейнера (this) и аргумента. opBinaryRight определена только, если Stuff не определяет opBinary.

Сложность: Ο(n + m), где m – это количество элементов в stuff

Переместиться к: 2

void opOpAssign(string op, Stuff)(Stuff stuff)
if (op == "~");
Перенаправляет к insertBack(stuff).

Переместиться к: 2

void clear();
Удаляет все содержимое из контейнера. Контейнер решает, как это будет воздействовать на capacity.

Postcondition: empty

Сложность: Ο(n)

@property void length(size_t newLength);
Устанавливает количество элементов в контейнере на newLength. Если newLength больше, чем length, на неопределенные позиции в контейнере добавляются дополнительные элементы и инициализируются T.init.

Сложность: Ο(abs(n - newLength))

Постусловие: length == newLength

Переместиться к: 2

T removeAny();

Переместиться к: 2

alias stableRemoveAny = removeAny;
Берет одно значение в неопределенной позиции в контейнере, удаляет его из контейнера, и возвращает его. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие контейнер, никогда не станут недействительными.
Я так и не понял, в чём тут состоит стабильность, тем более, что здесь и в последующих подобных функциях это всего лишь псевдоним. Во всяком случае, попробовав этот пример, ожидаемо нарвался на ошибку:
auto arr = make!Array([0, 1, 2, 3]);
auto a1=arr[2..4];
writeln(arr.stableRemoveAny());
writeln("a1=",a1[]); // Ошибка! Range violation

Предусловие: !empty

Возвращает:
Удалённый элемент.

Сложность: Ο(log(n)).

Переместиться к: 2

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

Переместиться к: 2

alias insert = insertBack;
Вставляет значение спереди или сзади контейнера. stuff может быть значением, преобразуемым в T, или диапазоном объектов, преобразуемых в T. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными.
Возвращает:
Количество вставленных элементов

Сложность: Ο(m * log(n)), где m – это количество элементов в stuff

Переместиться к: 2 · 3 · 4

void removeBack();

Переместиться к: 2 · 3

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

Предусловие: !empty

Сложность: Ο(log(n)).

size_t removeBack(size_t howMany);

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

Сложность: Ο(howMany).

Переместиться к: 2

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

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

Переместиться к: 2

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

Переместиться к: 2

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

size_t replace(Stuff)(Range r, Stuff stuff)
if (isImplicitlyConvertible!(Stuff, T));
Вставляет stuff перед, после, или вместо диапазона r, который должен быть действительным диапазоном, ранее извлечённым из этого контейнера. stuff может быть значением, преобразуемым в T или диапазоном объектов, преобразуемых в T. Стабильная версия ведется себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными.
Возвращает:
Количество вставленных элементов.

Сложность: Ο(n + m), где m – это длина stuff

Переместиться к: 2

Range linearRemove(Range r);
Удаляет все элементы, принадлежащие r, который должен быть диапазоном, полученным первоначально из этого контейнера. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными.
Возвращает:
Диапазон, распределяющий оставшиеся элементы в контейнере, которые изначально были справа после r.

Сложность: Ο(n - m), где m – это количество элементов в r

struct Array(T) if (is(Unqual!T == bool));
Массив, специализированый на bool. Упаковывает значения вместе, эффективно распределяя по одному биту на элемент.
struct Range;
Определяет первичный диапазон контейнера.
@property Range save();

@property bool empty();

@property T front();

@property void front(bool value);

T moveFront();

void popFront();

@property T back();

@property void back(bool value);

T moveBack();

void popBack();

T opIndex(size_t i);

void opIndexAssign(T value, size_t i);

T moveAt(size_t i);

const @property size_t length();

Range opSlice(size_t low, size_t high);
Примитивы диапазона
@property bool empty();
Свойство, возвращающее true тогда и только тогда, когда контейнер не имеет элементов.

Сложность: Ο(1)

@property Array dup();
Возвращает дубликат контейнера. Сами элементы дублируются не транзитивно.

Сложность: Ο(n).

const @property size_t length();
Возвращает количество элементов в контейнере.

Сложность: Ο(log(n)).

@property size_t capacity();
Возвращает максимальное количество элементов, которые контейнер может сохранить без (a) распределения памяти, (b) аннулирования итераторов при вставке.

Сложность: Ο(log(n)).

void reserve(size_t e);
Гарантирует, что размер capacity (возможности) станет достаточной для размещения elements элементов.

Postcondition: capacity >= n

Сложность: Ο(log(e - capacity)) if e > capacity, otherwise Ο(1).

Range opSlice();
Возвращает диапазон, который итерирует по элементам контейнера, в прямом порядке. Контейнер должен выбирать наиболее удобный и быстрый метод итерации для opSlice().

Сложность: Ο(log(n))

Range opSlice(size_t a, size_t b);
Возвращает диапазон, который итерирует по элементам контейнера между заданными позициями.

Сложность: Ο(log(n))

@property bool front();

@property void front(bool value);

@property bool back();

@property void back(bool value);
Эквивалентно opSlice().front и opSlice().back, соответсвенно.

Сложность: Ο(log(n))

bool opIndex(size_t i);

void opIndexAssign(bool value, size_t i);

void opIndexOpAssign(string op)(bool value, size_t i);

T moveAt(size_t i);
Оператор индексации, возвращающие или позволяющие модифицировать значение value по определенному индексу.
Array!bool opBinary(string op, Stuff)(Stuff rhs)
if (op == "~");
Возвращает новый контейнер, являющийся конкатенацией этого контейнера (this) и аргумента.

Сложность: Ο(n + m), где m – это количество элементов в stuff

Array!bool opOpAssign(string op, Stuff)(Stuff stuff)
if (op == "~");
Forwards to insertAfter(this[], stuff).
void clear();
Удаляет все содержимое из контейнера. Контейнер решает, как это будет воздействовать на capacity.

Постусловие: empty

Сложность: Ο(n)

@property void length(size_t newLength);
Устанавливает количество элементов в контейнере на newLength. Если newLength больше, чем length, в контейнер добавляются элементы и инициализируются в ElementType.init.

Сложность: Ο(abs(n - newLength))

Постусловие: length == newLength

alias insert = insertBack;

alias stableInsert = insertBack;
Вставляет stuff в контейнер. stuff может быть значением, преобразуемым в ElementType, или диапазоном объектов, преобразуемых в ElementType.
Стабильная версия гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными. Код клиента, который рассчитывает на не-недействительную вставку, должен использовать stableInsert.
Возвращает:
Количество добавленных элементов.

Сложность: Ο(m * log(n)), где m – это количество элементов в stuff

alias linearInsert = insertBack;

alias stableLinearInsert = insertBack;
То же, что insert(stuff) и stableInsert(stuff) соответвественно, но смягчает сложность до линейной.
T removeAny();

alias stableRemoveAny = removeAny;
Берет одно значение в контейнере, удаляет его из контейнера, и возвращает его. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие контейнер, никогда не станут недействительными.

Предусловие: !empty

Возвращает:
Удалённый элемент.

Сложность: Ο(log(n))

size_t insertBack(Stuff)(Stuff stuff)
if (is(Stuff : bool));

size_t insertBack(Stuff)(Stuff stuff)
if (isInputRange!Stuff && is(ElementType!Stuff : bool));

alias stableInsertBack = insertBack;
Вставляет значение сзади контейнера. stuff может быть значением, преобразуемым в ElementType, или диапазоном объектов, преобразуемых в ElementType. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными.
Возвращает:
Количество вставленных элементов

Сложность: Ο(log(n))

void removeBack();

alias stableRemoveBack = removeBack;
Удаляет значение с задней стороны контейнера. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными. Необязательный параметр howMany предписывает удалить столько элементов. Если howMany > n, удаляются все элементы, и исключение не выбрасывается.

Предусловие: !empty

Сложность: Ο(log(n)).

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

Сложность: Ο(howMany * log(n)).

ditto

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

alias stableInsertBefore = insertBefore;

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

alias stableInsertAfter = insertAfter;

size_t replace(Stuff)(Range r, Stuff stuff)
if (is(Stuff : bool));

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

Сложность: Ο(n + m), где m – это длина stuff

Range linearRemove(Range r);
Удаляет все элементы, принадлежащие r, который должен быть диапазоном, полученным первоначально из этого контейнера. Стабильная версия ведет себя так же, но гарантирует, что диапазоны, итерирующие по контейнеру, никогда не станут недействительными.
Возвращает:
Диапазон, распределяющий оставшиеся элементы в контейнере, которые изначально были справа после r.

Сложность: Ο(n)