std.container.slist

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

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

Источник

std/container/slist.d

Лицензия:

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

Авторы:

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

Примеры:

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

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

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

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

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

struct SList(T) if (!is(T == shared));

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

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

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

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

this(Stuff)(Stuff stuff)
Constraints: 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.

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)
Constraints: if (op == "~" && is(typeof(SList(rhs))));

SList opBinaryRight(string op, Stuff)(Stuff lhs)
Constraints: 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)
Constraints: if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

alias insert = insertFront;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

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

Возвращает:

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

Сложность

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

T removeAny();

alias stableRemoveAny = removeAny;

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

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

!empty

Возвращает:

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

Сложность

Ο(1).

void removeFront();

alias stableRemoveFront = removeFront;

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

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

!empty

Сложность

Ο(1).

size_t removeFront(size_t howMany);

alias stableRemoveFront = removeFront;

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

Возвращает:

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

Сложность

Ο(howMany * log(n)).

size_t insertAfter(Stuff)(Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

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

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

Возвращает:

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

Сложность

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

Пример

auto sl = SList!string(["a", "b", "d"]);
sl.insertAfter(sl[], "e"); // insert at the end (slowest)
assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b"
assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));

size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

alias stableInsertAfter = insertAfter;

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

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

r.original.empty || r.maxLength > 0

Возвращает:

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

Сложность

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

Range linearRemove(Range r);

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

Возвращает:

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

Сложность

Ο(n)

Range linearRemove(Take!Range r);

alias stableLinearRemove = linearRemove;

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

Возвращает:

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

Сложность

Ο(n)

bool linearRemoveElement(T value);

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

Возвращает:

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

Параметры:

T value

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

Сложность

Ο(n)