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:

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 doubly-linked 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)) 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)(Stuff rhs)

Constraints:
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)

Constraints:
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)

Constraints:
if (op == "~" && is(typeof(insertBack(rhs))))

Appends the contents of the argument rhs into this.

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

Returns:

The number of values inserted.

Complexity

Ο(k + m), where k is the number of elements in r and m is the length of stuff.

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

Returns:

The number of elements removed

Complexity

Ο(howMany).

Range remove(Range r)
Range linearRemove(Range r)

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 range r.

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 range r.

Compexity

Ο(1)

Range linearRemove(Take!Range r)
alias stableRemove = remove
alias stableLinearRemove = 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)