std.container.slist

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

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

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

s.insertFront([5, 6]);
assert(equal(s[], [5, 6, 2, 3]));

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

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

auto r = sl[];
popFrontN(r, 2);
assert(walkLength(r) == 3);

Переместиться к: clear · dup · empty · front · insert · insertAfter · insertFront · linearRemove · opBinary · opBinaryRight · opEquals · opSlice · Range · removeAny · removeFront · reverse · stableInsert · stableInsertAfter · stableInsertFront · stableLinearRemove · stableRemoveAny · stableRemoveFront · this

struct SList(T);

Реализует простой и быстрый односвязный список. Может быть использован как стек.

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

Переместиться к: 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 SList rhs);

const bool opEquals(ref const SList rhs);

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

Сложность: Ο(min(n, n1)), где n1 – это количество элементов в rhs.

Переместиться к: empty · front · popFront · save

struct Range;

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

const @property bool empty();

@property ref T front();

void popFront();

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

@property Range save();

Примитив лидирующего диапазона.

const @property bool empty();

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

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

@property SList dup();

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

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

Range opSlice();

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

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

@property ref T front();

Перенаправляет к opSlice().front.

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

SList opBinary(string op, Stuff)(Stuff rhs)
if (op == "~" && is(typeof(SList(rhs))));

SList opBinaryRight(string op, Stuff)(Stuff lhs)
if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))));

Возвращает новый SList, который является результатом конкатенации this и его аргумента. opBinaryRight определен только, если Stuff не определяет opBinary.

void clear();

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

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

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

void reverse();

Обращает SList на-месте. Не выполняет никакого распределения памяти.

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

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

size_t insertFront(Stuff)(Stuff stuff)
if (isImplicitlyConvertible!(Stuff, T));

alias insert = insertFront;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

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

Returns:

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

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

T removeAny();

alias stableRemoveAny = removeAny;

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

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

Returns:

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

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

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

void removeFront();

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

alias stableRemoveFront = removeFront;

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

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

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

size_t removeFront(size_t howMany);

alias stableRemoveFront = removeFront;

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

Returns:

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

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

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

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

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

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

Returns:

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

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

Пример:

auto sl = SList!string(["a", "b", "d"]);
sl.insertAfter(sl[], "e"); // вставить в конце (медленно)
assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
sl.insertAfter(std.range.take(sl[], 2), "c"); // вставить после "b"
assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));

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

alias stableInsertAfter = insertAfter;

Подобно insertAfter, описанному выше, но принимает диапазон, ограниченный по количеству. Важно для обеспечения быстрых вставок в середине списка. Для быстрых вставок после определенной позиции r, используйте insertAfter(take(r, 1), stuff). Сложность этого действия зависит только от количества элементов в stuff.

Предусловие: r.original.empty || r.maxLength > 0

Returns:

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

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

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

Range linearRemove(Range r);

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

Returns:

Пустой диапазон.

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

Range linearRemove(Take!Range r);

alias stableLinearRemove = linearRemove;

Удаляет Take!Range из списка за линейное время.

Returns:

Диапазон, охватывающий элементы после удалённого диапазона.

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