std.container.dlist

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

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]));

// Если вы хотите применять операции с диапазонами, просто выделите срез.
import std.algorithm.searching : countUntil;
import std.range : popFrontN, popBackN, walkLength;

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

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

Переместиться к: back · clear · dup · empty · front · insert · insertAfter · insertBack · insertBefore · insertFront · linearRemove · opBinary · opBinaryRight · opEquals · opOpAssign · opSlice · Range · remove · removeAny · removeBack · removeFront · stableInsert · stableInsertAfter · stableInsertBack · stableInsertBefore · stableInsertFront · stableLinearRemove · stableRemove · stableRemoveAny · stableRemoveBack · stableRemoveFront · this

struct DList(T);

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

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

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

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

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

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

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

const bool opEquals()(ref const DList rhs)
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)
if (op == "~" && is(typeof(insertBack(rhs))));

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

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

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

DList opOpAssign(string op, Stuff)(Stuff rhs)
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).

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

void removeFront();

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

alias stableRemoveFront = removeFront;

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

void removeBack();

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

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);

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

Range linearRemove(Range r);

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

Возвращает:

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

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

Range linearRemove(Take!Range r);

alias stableRemove = remove;

alias stableLinearRemove = linearRemove;

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

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