std.container.dlist

This module implements a generic doubly-linked list container. It can be used as a queue, dequeue or stack.

This module is a submodule of std.container.

Source: std/container/dlist.d

Copyright

License

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

Authors

Andrei Alexandrescu

struct BaseNode DList DRange

Types 3

private structBaseNode

Fields

private BaseNode * _prev

private BaseNode * _next

Methods

inout(T) getPayload(T)() ref inout @trusted

void connect(BaseNode * p, BaseNode * n) @safe nothrow pure

private structDRange

Fields

private BaseNode * _first

private BaseNode * _last

Methods

bool empty() @property const scope

BaseNode * front() @property return scope

void popFront() scope

BaseNode * back() @property return scope

void popBack() scope

DRange save() @property return scopeForward range primitive.

Constructors

this(BaseNode * first, BaseNode * last)

this(BaseNode * n)

structDList(T)

Implements a doubly-linked list.

DList uses reference semantics.

Fields

private BaseNode * _root

Methods

BaseNode * createNode(Stuff)(auto ref Stuff arg, BaseNode * prev = null, BaseNode * next = null)

void initialize() nothrow @safe pure

inout(BaseNode *) _first() ref @property @safe nothrow pure inout

inout(BaseNode *) _last() ref @property @safe nothrow pure inout

bool opEquals()(ref const DList rhs) if (is(typeof(front == front))) constComparison for equality.

bool empty() @property const nothrowProperty returning `true` if and only if the container has no elements.

void clear()Removes all contents from the `DList`.

DList dup() @propertyDuplicates the container. The elements themselves are not transitively duplicated.

Range opSlice()Returns a range that iterates over all elements of the container, in forward order.

inout(T) front() @property ref inoutForward to `opSlice().front`.

inout(T) back() @property ref inoutForward to `opSlice().back`.

DList opBinary(string op, Stuff)(Stuff rhs) if (op == "~" && is(typeof(insertBack(rhs))))Returns a new `DList` that's the concatenation of `this` and its argument `rhs`.

DList opBinaryRight(string op, Stuff)(Stuff lhs) if (op == "~" && is(typeof(insertFront(lhs))))Returns a new `DList` that's the concatenation of the argument `lhs` and `this`.

DList opOpAssign(string op, Stuff)(Stuff rhs) if (op == "~" && is(typeof(insertBack(rhs))))Appends the contents of the argument `rhs` into `this`.

size_t insertFront(Stuff)(Stuff stuff)Inserts `stuff` to the front/back of the container. `stuff` can be a value convertible to `T` or a range of objects convertible to T. The stable version behaves the same, but guarantees that ranges...

size_t insertBack(Stuff)(Stuff stuff)ditto

size_t insertBefore(Stuff)(Range r, Stuff stuff)Inserts `stuff` after range `r`, which must be a non-empty range previously extracted from this container.

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

T removeAny()Picks one value in an unspecified position in the container, removes it from the container, and returns it. The stable version behaves the same, but guarantees that ranges iterating over the contai...

void removeFront()Removes the value at the front/back of the container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

void removeBack()ditto

size_t removeFront(size_t howMany)Removes `howMany` values at the front or back of the container. Unlike the unparameterized versions above, these functions do not throw if they could not remove `howMany` elements. Instead, if howM...

size_t removeBack(size_t howMany)ditto

Range remove(Range r)Removes all elements belonging to `r`, which must be a range obtained originally from this container.

Range linearRemove(Range r)ditto

void popFirstOf(ref Range r)Removes first element of `r`, wich must be a range obtained originally from this container, from both DList instance and range `r`.

void popLastOf(ref Range r)Removes last element of `r`, wich must be a range obtained originally from this container, from both DList instance and range `r`.

Range linearRemove(Take!Range r)`linearRemove` functions as `remove`, but also accepts ranges that are result the of a `take` operation. This is a convenient way to remove a fixed amount of elements from the range.

bool linearRemoveElement(T value)Removes the first occurence of an element from the list in linear time.

BaseNode * findNodeByValue(BaseNode * n, T value)

size_t insertBeforeNode(Stuff)(BaseNode * n, ref Stuff stuff) if (isImplicitlyConvertible!(Stuff, T))

size_t insertBeforeNode(Stuff)(BaseNode *  n,  ref  Stuff stuff) if (isInputRange!Stuff &&  isImplicitlyConvertible!(ElementType!Stuff,  T))

size_t insertAfterNode(Stuff)(BaseNode * n, ref Stuff stuff) if (isImplicitlyConvertible!(Stuff, T))

size_t insertAfterNode(Stuff)(BaseNode *  n,  ref  Stuff stuff) if (isInputRange!Stuff &&  isImplicitlyConvertible!(ElementType!Stuff,  T))

Range createRange(Stuff)(ref Stuff stuff, ref size_t result)

Constructors

this(U[] values...)Constructor taking a number of nodes

this(Stuff stuff)Constructor taking an input range

Nested Templates

PayNode

RangeDefines the container's primary range, which embodies a bidirectional range.