Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Forums
  - IRC
  - Wiki
  - GitHub
  - Issues
  - Foundation
  - Donate
- Resources
  - Books
  - Tutorials
  - Tools
  - Editors
  - IDEs
  - Visual D
  - Acknowledgments
  - D Style
  - Glossary
  - Sitemap

Search
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:
Andrei Alexandrescu
Examples:

    import std.container : DList;
    import std.algorithm.comparison : equal;

    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]);
    assert(countUntil(sl[], 2) == 1);

    auto r = sl[];
    popFrontN(r, 2);
    popBackN(r, 2);
    assert(r.equal([3]));
    assert(walkLength(r) == 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 DList `rhs`)
  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`)
  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`)
  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`)
  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)

  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)

2010- Andrei Alexandrescu. All rights reserved by the respective holders. | Page generated by Ddoc on Thu Mar 9 17:49:42 2017