Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
a local clone.
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
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:
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 doubly-linked list.
DList
uses reference semantics.- this(U)(U[]
values
...)
if (isImplicitlyConvertible!(U, T)); - Constructor taking a number of nodes
- this(Stuff)(Stuff
stuff
)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)); - Constructor taking an input range
- const bool
opEquals
()(ref const DListrhs
)
if (is(typeof(front == front))); - Comparison for equality.
Complexity Ο(min(n, n1)) where n1 is the number of elements in
rhs
. - 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)(Stuffrhs
)
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)(Stufflhs
)
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)(Stuffrhs
)
if (op == "~" && is(typeof(insertBack(rhs
)))); - Appends the contents of the argument
rhs
into this. - size_t
insertFront
(Stuff)(Stuffstuff
);
size_tinsertBack
(Stuff)(Stuffstuff
);
aliasinsert
= insertBack;
aliasstableInsert
= insert;
aliasstableInsertFront
= insertFront;
aliasstableInsertBack
= insertBack; - 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.Returns:The number of elements insertedComplexity Ο(log(n))
- size_t
insertBefore
(Stuff)(Ranger
, Stuffstuff
);
aliasstableInsertBefore
= insertBefore;
size_tinsertAfter
(Stuff)(Ranger
, Stuffstuff
);
aliasstableInsertAfter
= insertAfter; - Inserts
stuff
after ranger
, 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.Returns:The number of values inserted.Complexity Ο(k + m), where k is the number of elements in
r
and m is the length ofstuff
. - T
removeAny
();
aliasstableRemoveAny
= 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
();
aliasstableRemoveFront
= removeFront;
voidremoveBack
();
aliasstableRemoveBack
= 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_thowMany
);
aliasstableRemoveFront
= removeFront;
size_tremoveBack
(size_thowMany
);
aliasstableRemoveBack
= 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, 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.Returns:The number of elements removedComplexity Ο(howMany).
- Range
remove
(Ranger
);
RangelinearRemove
(Ranger
);
aliasstableRemove
= 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 afterr
.Complexity Ο(1)
- void
popFirstOf
(ref Ranger
); - 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 Ranger
); - 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!Ranger
);
aliasstableLinearRemove
= linearRemove; 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.Complexity Ο(r.walkLength)
- bool
linearRemoveElement
(Tvalue
); - 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)
Copyright © 1999-2022 by the D Language Foundation | Page generated by
Ddoc on (no date time)