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
.
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]));
Implements a doubly-linked list.
DList
uses reference semantics.
Constructor taking a number of nodes
Constructor taking an input range
Comparison for equality.
min(n, n1)
) where n1
is the number of elements in rhs
.Defines the container's primary range, which embodies a bidirectional range.
Property returning true
if and only if the container has no elements.
1
)
Removes all contents from the DList
.
empty
1
)
Duplicates the container. The elements themselves are not transitively duplicated.
n
).Returns a range that iterates over all elements of the container, in forward order.
1
)
Forward to opSlice().front
.
1
)
Forward to opSlice().back
.
1
)
Returns a new DList
that's the concatenation of this
and its argument rhs
.
Returns a new DList
that's the concatenation of the argument lhs
and this
.
Appends the contents of the argument rhs
into this
.
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 iterating over the container are never invalidated.
log(n)
)
Inserts stuff
after range r
, which must be a non-empty range previously extracted from this 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 iterating over the container are never invalidated.
k + m
), where k
is the number of elements in r
and m
is the length of stuff
.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.
!empty
1
).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.
!empty
1
).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 howMany > 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.
howMany
).Removes all elements belonging to r
, which must be a range obtained originally from this container.
r
. 1
)
Removes first element of r
, wich must be a range obtained originally from this container, from both DList instance and range r
.
1
)
Removes last element of r
, wich must be a range obtained originally from this container, from both DList instance and range r
.
1
)
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.
r.walkLength
)
Removes the first occurence of an element from the list in linear time.
T value
| value of the node to be removed |
n
)
© 1999–2019 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_container_dlist.html