This module implements a singly-linked list container. It can be used as a stack.
This module is a submodule of std.container
.
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
Implements a simple and fast singly-linked list. It can be used as a stack.
SList
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 forward range.
Input range primitives.
Forward range primitive.
Property returning true
if and only if the container has no elements.
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
)
Returns a new SList
that's the concatenation of this
and its argument. opBinaryRight
is only defined if Stuff
does not define opBinary
.
Removes all contents from the SList
.
empty
1
)
Reverses SList in-place. Performs no memory allocation.
n
)
Inserts stuff
to the front 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.
m
), where 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 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 * log(n)
).Inserts stuff
after range r
, which must be a range previously extracted from this container. Given that all ranges for a list end at the end of the list, this function essentially appends to the list and uses r
as a potentially fast way to reach the last node in the list. Ideally r
is positioned near or at the last element of the list.
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
. 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"]));
Similar to insertAfter
above, but accepts a range bounded in count. This is important for ensuring fast insertions in the middle of the list. For fast insertions after a specified position r
, use insertAfter(take(r, 1), stuff)
. The complexity of that operation only depends on the number of elements in stuff
.
r.original.empty || r.maxLength > 0
k + m
), where k
is the number of elements in r
and m
is the length of stuff
.Removes a range from the list in linear time.
n
)
Removes a Take!Range
from the list in linear time.
n
)
© 1999–2017 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_container_slist.html