std.container.array - D Programming Language

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

This module provides an Array type with deterministic memory usage not reliant on the GC, as an alternative to the built-in arrays.
This module is a submodule of std.container.

Source: std/container/array.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:

    auto arr = Array!int(0, 2, 3);
    assert(arr[0] == 0);
    assert(arr.front == 0);
    assert(arr.back == 3);

    // reserve space
    arr.reserve(1000);
    assert(arr.length == 3);
    assert(arr.capacity >= 1000);

    // insertion
    arr.insertBefore(arr[1..$], 1);
    assert(arr.front == 0);
    assert(arr.length == 4);

    arr.insertBack(4);
    assert(arr.back == 4);
    assert(arr.length == 5);

    // set elements
    arr[1] *= 42;
    assert(arr[1] == 42);

Examples:

    import std.algorithm.comparison : equal;
    auto arr = Array!int(1, 2, 3);

    // concat
    auto b = Array!int(11, 12, 13);
    arr ~= b;
    assert(arr.length == 6);

    // slicing
    assert(arr[1..3].equal([2, 3]));

    // remove
    arr.linearRemove(arr[1..3]);
    assert(arr[0..2].equal([1, 11]));

Examples:
Array!bool packs together values efficiently by allocating one bit per element

    Array!bool arr;
    arr.insert([true, true, false, true, false]);
    assert(arr.length == 5);

struct `Array`(T) if (!is(Unqual!T == bool));
  `Array` type with deterministic control of memory. The memory allocated for the array is reclaimed as soon as possible; there is no reliance on the garbage collector. `Array` uses malloc and free for managing its own memory.
  This means that pointers to elements of an `Array` will become dangling as soon as the element is removed from the `Array`. On the other hand the memory allocated by an `Array` will be scanned by the GC and GC managed objects referenced from an `Array` will be kept alive.

  Note: When using `Array` with range-based functions like those in std.algorithm, `Array` must be sliced to get a range (for example, use array[].map! instead of array.map!). The container itself is not a range.

  this(U)(U[] `values`...)
  if (isImplicitlyConvertible!(U, T));
    Constructor taking a number of items
  this(Stuff)(Stuff `stuff`)
  if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[]));
    Constructor taking an input range
  const bool `opEquals`(const Array `rhs`);
  const bool `opEquals`(ref const Array `rhs`);
    Comparison for equality.
  alias `Range` = RangeT!Array;
  alias `ConstRange` = RangeT!(const(Array));
  alias `ImmutableRange` = RangeT!(immutable(Array));
    Defines the container's primary range, which is a random-access range.
    `ConstRange` is a variant with const elements. `ImmutableRange` is a variant with immutable elements.
  @property Array `dup`();
    Duplicates the container. The elements themselves are not transitively duplicated.

    Complexity: Ο(n).

  const @property bool `empty`();
    Property returning `true` if and only if the container has no elements.

    Complexity: Ο(1)

  const @property size_t `length`();
  const size_t `opDollar`();
    Returns the number of elements in the container.

    Complexity: Ο(1).

  @property size_t `capacity`();
    Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion.

    Complexity: Ο(1)

  void `reserve`(size_t `elements`);
    Ensures sufficient capacity to accommodate e `elements`.

    Postcondition: capacity >= e

    Complexity: Ο(1)

  Range `opSlice`();
    Returns a range that iterates over elements of the container, in forward order.

    Complexity: Ο(1)

  Range `opSlice`(size_t `i`, size_t `j`);
    Returns a range that iterates over elements of the container from index a up to (excluding) index b.

    Precondition: a <= b && b <= length

    Complexity: Ο(1)

  inout @property ref inout(T) `front`();
  inout @property ref inout(T) `back`();
    Forward to opSlice().`front` and opSlice().`back`, respectively.

    Precondition: !empty

    Complexity: Ο(1)

  inout ref inout(T) `opIndex`(size_t `i`);
    Indexing operators yield or modify the value at a specified index.

    Precondition: `i` < length

    Complexity: Ο(1)

  void `opSliceAssign`(T `value`);
  void `opSliceAssign`(T `value`, size_t `i`, size_t `j`);
  void `opSliceUnary`(string op)()
  if (op == "++" || op == "--");
  void `opSliceUnary`(string op)(size_t `i`, size_t `j`)
  if (op == "++" || op == "--");
  void `opSliceOpAssign`(string op)(T `value`);
  void `opSliceOpAssign`(string op)(T `value`, size_t `i`, size_t `j`);
    Slicing operations execute an operation on an entire slice.

    Precondition: `i` < `j` && `j` < length

    Complexity: Ο(slice.length)

  Array `opBinary`(string op, Stuff)(Stuff `stuff`)
  if (op == "~");
    Returns a new container that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define `opBinary`.

    Complexity: Ο(n + m), where m is the number of elements in `stuff`

  void `opOpAssign`(string op, Stuff)(Stuff `stuff`)
  if (op == "~");
    Forwards to insertBack(`stuff`).
  void `clear`();
    Removes all contents from the container. The container decides how capacity is affected.

    Postcondition: empty

    Complexity: Ο(n)

  @property void `length`(size_t `newLength`);
    Sets the number of elements in the container to newSize. If newSize is greater than `length`, the added elements are added to unspecified positions in the container and initialized with T.init.

    Complexity: Ο(abs(n - `newLength`))

    Postcondition: `length` == `newLength`

  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: Ο(log(n)).

  size_t `insertBack`(Stuff)(Stuff `stuff`)
  if (isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));
  alias `insert` = insertBack;
    Inserts value to the front or 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: Ο(m * log(n)), where m is the number of elements in `stuff`

  void `removeBack`();
  alias `stableRemoveBack` = removeBack;
    Removes the value at the back of the container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

    Precondition: !empty

    Complexity: Ο(log(n)).

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

  size_t `insertBefore`(Stuff)(Range `r`, Stuff `stuff`)
  if (isImplicitlyConvertible!(Stuff, T));
  size_t `insertBefore`(Stuff)(Range `r`, Stuff `stuff`)
  if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));
  size_t `insertAfter`(Stuff)(Range `r`, Stuff `stuff`);
  size_t `replace`(Stuff)(Range `r`, Stuff `stuff`)
  if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));
  size_t `replace`(Stuff)(Range `r`, Stuff `stuff`)
  if (isImplicitlyConvertible!(Stuff, T));
    Inserts `stuff` before, after, or instead range `r`, which must be a valid 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: Ο(n + m), where m is the length of `stuff`

  Range `linearRemove`(Range `r`);
    Removes all elements belonging to `r`, which must be a range obtained originally from this container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.
    Returns:
    A range spanning the remaining elements in the container that initially were right after `r`.

    Complexity: Ο(n - m), where m is the number of elements in `r`

struct `Array`(T) if (is(Unqual!T == bool));
  Array specialized for bool. Packs together values efficiently by allocating one bit per element.
  struct `Range`;
    Defines the container's primary range.
    @property Range `save`();
    @property bool `empty`();
    @property T `front`();
    @property void `front`(bool `value`);
    T `moveFront`();
    void `popFront`();
    @property T `back`();
    @property void `back`(bool `value`);
    T `moveBack`();
    void `popBack`();
    T `opIndex`(size_t `i`);
    void `opIndexAssign`(T `value`, size_t `i`);
    T `moveAt`(size_t `i`);
    const @property size_t `length`();
    Range `opSlice`(size_t `low`, size_t `high`);
      Range primitives
  @property bool `empty`();
    Property returning `true` if and only if the container has no elements.

    Complexity: Ο(1)

  @property Array `dup`();
    Returns a duplicate of the container. The elements themselves are not transitively duplicated.

    Complexity: Ο(n).

  const @property size_t `length`();
    Returns the number of elements in the container.

    Complexity: Ο(log(n)).

  @property size_t `capacity`();
    Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion.

    Complexity: Ο(log(n)).

  void `reserve`(size_t `e`);
    Ensures sufficient capacity to accommodate n elements.

    Postcondition: capacity >= n

    Complexity: Ο(log(`e` - capacity)) if `e` > capacity, otherwise Ο(1).

  Range `opSlice`();
    Returns a range that iterates over all elements of the container, in a container-defined order. The container should choose the most convenient and fast method of iteration for `opSlice`().

    Complexity: Ο(log(n))

  Range `opSlice`(size_t `a`, size_t `b`);
    Returns `a` range that iterates the container between two specified positions.

    Complexity: Ο(log(n))

  @property bool `front`();
  @property void `front`(bool `value`);
  @property bool `back`();
  @property void `back`(bool `value`);
    Equivalent to opSlice().`front` and opSlice().`back`, respectively.

    Complexity: Ο(log(n))

  bool `opIndex`(size_t `i`);
  void `opIndexAssign`(bool `value`, size_t `i`);
  void `opIndexOpAssign`(string op)(bool `value`, size_t `i`);
  T `moveAt`(size_t `i`);
    Indexing operators yield or modify the `value` at a specified index.
  Array!bool `opBinary`(string op, Stuff)(Stuff `rhs`)
  if (op == "~");
    Returns a new container that's the concatenation of this and its argument.

    Complexity: Ο(n + m), where m is the number of elements in stuff

  Array!bool `opOpAssign`(string op, Stuff)(Stuff `stuff`)
  if (op == "~");
    Forwards to insertAfter(this[], `stuff`).
  void `clear`();
    Removes all contents from the container. The container decides how capacity is affected.

    Postcondition: empty

    Complexity: Ο(n)

  @property void `length`(size_t `newLength`);
    Sets the number of elements in the container to newSize. If newSize is greater than `length`, the added elements are added to the container and initialized with ElementType.init.

    Complexity: Ο(abs(n - `newLength`))

    Postcondition: length == `newLength`

  alias `insert` = insertBack;
  alias `stableInsert` = insertBack;
    Inserts stuff in the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType.
    The stable version guarantees that ranges iterating over the container are never invalidated. Client code that counts on non-invalidating insertion should use `stableInsert`.
    Returns:
    The number of elements added.

    Complexity: Ο(m * log(n)), where m is the number of elements in stuff

  alias `linearInsert` = insertBack;
  alias `stableLinearInsert` = insertBack;
    Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear.
  T `removeAny`();
  alias `stableRemoveAny` = removeAny;
    Picks one value 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: Ο(log(n))

  size_t `insertBack`(Stuff)(Stuff `stuff`)
  if (is(Stuff : bool));
  size_t `insertBack`(Stuff)(Stuff `stuff`)
  if (isInputRange!Stuff && is(ElementType!Stuff : bool));
  alias `stableInsertBack` = insertBack;
    Inserts value to the back of the container. `stuff` can be a value convertible to ElementType or a range of objects convertible to ElementType. 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))

  void `removeBack`();
  alias `stableRemoveBack` = removeBack;
    Removes the value at the front or back of the container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated. The optional parameter howMany instructs removal of that many elements. If howMany > n, all elements are removed and no exception is thrown.

    Precondition: !empty

    Complexity: Ο(log(n)).

  size_t `removeBack`(size_t `howMany`);
    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` * log(n)).

    ditto
  size_t `insertBefore`(Stuff)(Range `r`, Stuff `stuff`);
  alias `stableInsertBefore` = insertBefore;
  size_t `insertAfter`(Stuff)(Range `r`, Stuff `stuff`);
  alias `stableInsertAfter` = insertAfter;
  size_t `replace`(Stuff)(Range `r`, Stuff `stuff`)
  if (is(Stuff : bool));
  alias `stableReplace` = replace;
    Inserts `stuff` before, after, or instead range `r`, which must be a valid range previously extracted from this container. `stuff` can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.
    Returns:
    The number of values inserted.

    Complexity: Ο(n + m), where m is the length of `stuff`

  Range `linearRemove`(Range `r`);
    Removes all elements belonging to `r`, which must be a range obtained originally from this container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.
    Returns:
    A range spanning the remaining elements in the container that initially were right after `r`.

    Complexity: Ο(n)

2010- Andrei Alexandrescu. All rights reserved by the respective holders. | Page generated by Ddoc on Sun Jan 22 15:47:34 2017