std.container.dlist

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

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

Исходный код

std/container/dlist.d

Лицензия:

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

Авторы:

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

Примеры:

import std.algorithm.comparison : equal;
import std.container : DList;

auto s = DList!int(1, 2, 3);
assert(equal(s[], [1, 2, 3]));

s.removeFront();
assert(equal(s[], [2, 3]));
s.removeBack();
assert(equal(s[], [2]));

s.insertFront([4, 5]);
assert(equal(s[], [4, 5, 2]));
s.insertBack([6, 7]);
assert(equal(s[], [4, 5, 2, 6, 7]));

// If you want to apply range operations, simply slice it.
import std.algorithm.searching : countUntil;
import std.range : popFrontN, popBackN, walkLength;

auto sl = DList!int([1, 2, 3, 4, 5]);
writeln(countUntil(sl[], 2)); // 1

auto r = sl[];
popFrontN(r, 2);
popBackN(r, 2);
assert(r.equal([3]));
writeln(walkLength(r)); // 1

// DList.Range can be used to remove elements from the list it spans
auto nl = DList!int([1, 2, 3, 4, 5]);
for (auto rn = nl[]; !rn.empty;)
    if (rn.front % 2 == 0)
        nl.popFirstOf(rn);
    else
        rn.popFront();
assert(equal(nl[], [1, 3, 5]));
auto rs = nl[];
rs.popFront();
nl.remove(rs);
assert(equal(nl[], [1]));

struct DList(T);

Реализует двусвязный список.

DList использует семантику ссылок.

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

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

this(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

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

const bool opEquals()(ref const DList rhs)
Constraints: if (is(typeof(front == front)));

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

Сложность

Ο(min(n, n1)) где n1 — количество элементов в rhs.

struct Range;

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

const nothrow @property bool empty();

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

Сложность

Ο(1)

void clear();

Удаляет все содержимое из DList.

Постусловие

empty

Сложность

Ο(1)

@property DList dup();

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

Сложность

Ο(n).

Range opSlice();

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

Сложность

Ο(1)

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

Обращается к opSlice().front.

Сложность

Ο(1)

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

Обращается к opSlice().back.

Сложность

Ο(1)

DList opBinary(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~" && is(typeof(insertBack(rhs))));

Возвращает новый DList, который является конкатенацией this и его аргумента rhs.

DList opBinaryRight(string op, Stuff)(Stuff lhs)
Constraints: if (op == "~" && is(typeof(insertFront(lhs))));

Возвращает новый DList, который является конкатенацией аргумента lhs и this.

DList opOpAssign(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~" && is(typeof(insertBack(rhs))));

Добавляет содержимое аргумента rhs в this.

size_t insertFront(Stuff)(Stuff stuff);

size_t insertBack(Stuff)(Stuff stuff);

alias insert = insertBack;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

alias stableInsertBack = insertBack;

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

Возвращает:

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

Сложность

Ο(log(n))

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

alias stableInsertBefore = insertBefore;

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

alias stableInsertAfter = insertAfter;

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

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

Возвращает:

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

Сложность

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

T removeAny();

alias stableRemoveAny = removeAny;

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

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

!empty

Возвращает:

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

Сложность

Ο(1).

void removeFront();

alias stableRemoveFront = removeFront;

void removeBack();

alias stableRemoveBack = removeBack;

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

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

!empty

Сложность

Ο(1).

size_t removeFront(size_t howMany);

alias stableRemoveFront = removeFront;

size_t removeBack(size_t howMany);

alias stableRemoveBack = removeBack;

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

Возвращает:

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

Сложность

Ο(howMany).

Range remove(Range r);

Range linearRemove(Range r);

alias stableRemove = remove;

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

Возвращает:

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

Сложность

Ο(1)

void popFirstOf(ref Range r);

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

Сложность

Ο(1)

void popLastOf(ref Range r);

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

Сложность

Ο(1)

Range linearRemove(Take!Range r);

alias stableLinearRemove = linearRemove;

Функция linearRemove работает как remove, но также принимает диапазоны, которые являются результатом операции take. Это удобный способ удалить определённое количество элементов из диапазона.

Сложность

Ο(r.walkLength)

bool linearRemoveElement(T value);

Удаляет первое вхождение элемента из списка за линейное время.

Возвращает:

True, если элемент существовал и был успешно удалён, false в противном случае.

Параметры:

T value

значение узла, который нужно удалить

Сложность

Ο(n)