On this page
std.container.dlist
This module implements a generic doublylinked 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
 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
 Examples:

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

Implements a doublylinked list.
DList
uses reference semantics.
this(U)(U[] values...)
Constraints: if (isImplicitlyConvertible!(U, T)); 
Constructor taking a number of nodes

this(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)); 
Constructor taking an input range

const bool opEquals()(ref const DList rhs)
Constraints: if (is(typeof(front == front))); 
Comparison for equality.
 Complexity
 Ο(
min(n, n1)
) wheren1
is the number of elements inrhs
.
 struct Range;

Defines the container's primary range, which embodies a bidirectional range.
 const nothrow @property bool empty();

Property returning
true
if and only if the container has no elements. Complexity
 Ο(
1
)
 void clear();

Removes all contents from the
DList
. Postcondition
empty
 Complexity
 Ο(
1
)
 @property DList dup();

Duplicates the container. The elements themselves are not transitively duplicated.
 Complexity
 Ο(
n
).
 Range opSlice();

Returns a range that iterates over all elements of the container, in forward order.
 Complexity
 Ο(
1
)
 inout @property ref inout(T) front();

Forward to
opSlice().front
. Complexity
 Ο(
1
)
 inout @property ref inout(T) back();

Forward to
opSlice().back
. Complexity
 Ο(
1
)

DList opBinary(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~" && is(typeof(insertBack(rhs)))); 
Returns a new
DList
that's the concatenation ofthis
and its argumentrhs
. 
DList opBinaryRight(string op, Stuff)(Stuff lhs)
Constraints: if (op == "~" && is(typeof(insertFront(lhs)))); 
Returns a new
DList
that's the concatenation of the argumentlhs
andthis
. 
DList opOpAssign(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~" && is(typeof(insertBack(rhs)))); 
Appends the contents of the argument
rhs
intothis
. 
size_t insertFront(Stuff)(Stuff stuff);
size_t insertBack(Stuff)(Stuff stuff);
alias insert = insertBack;
alias stableInsert = insert;
alias stableInsertFront = insertFront;
alias stableInsertBack = insertBack; 
Inserts
stuff
to the front/back of the container.stuff
can be a value convertible toT
or a range of objects convertible toT
. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated. Returns:
 The number of elements inserted
 Complexity
 Ο(
log(n)
)

size_t insertBefore(Stuff)(Range r, Stuff stuff);
alias stableInsertBefore = insertBefore;
size_t insertAfter(Stuff)(Range r, Stuff stuff);
alias stableInsertAfter = insertAfter; 
Inserts
stuff
after ranger
, which must be a nonempty range previously extracted from this container.stuff
can be a value convertible toT
or a range of objects convertible toT
. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated. Returns:
 The number of values inserted.
 Complexity
 Ο(
k + m
), wherek
is the number of elements inr
andm
is the length ofstuff
.

T removeAny();
alias stableRemoveAny = 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 container are never invalidated.
 Precondition
!empty
 Returns:
 The element removed.
 Complexity
 Ο(
1
).

void removeFront();
alias stableRemoveFront = removeFront;
void removeBack();
alias stableRemoveBack = removeBack; 
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.
 Precondition
!empty
 Complexity
 Ο(
1
).

size_t removeFront(size_t howMany);
alias stableRemoveFront = removeFront;
size_t removeBack(size_t howMany);
alias stableRemoveBack = removeBack; 
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 removehowMany
elements. Instead, ifhowMany > n
, all elements are removed. The returned value is the effective number of elements removed. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated. Returns:
 The number of elements removed
 Complexity
 Ο(
howMany
).

Range remove(Range r);
Range linearRemove(Range r);
alias stableRemove = remove; 
Removes all elements belonging to
r
, which must be a range obtained originally from this container. Returns:

A range spanning the remaining elements in the container that initially were right after
r
.
 Complexity
 Ο(
1
)
 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 ranger
. Compexity
 Ο(
1
)
 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 ranger
. Compexity
 Ο(
1
)

Range linearRemove(Take!Range r);
alias stableLinearRemove = linearRemove; 
linearRemove
functions asremove
, but also accepts ranges that are result the of atake
operation. This is a convenient way to remove a fixed amount of elements from the range. Complexity
 Ο(
r.walkLength
)
 bool linearRemoveElement(T value);

Removes the first occurence of an element from the list in linear time.
 Returns:
 True if the element existed and was successfully removed, false otherwise.
 Parameters:

T value
value of the node to be removed
 Complexity
 Ο(
n
)

this(U)(U[] values...)
© 1999–2021 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_container_dlist.html