View source code
Display the source code in std/container/package.d from which this page was generated on github.
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 local clone.

Module std.container

This module defines generic containers.

Construction

To implement the different containers both struct and class based approaches have been used. make allows for uniform construction with either approach.

import std.container;
// Construct a red-black tree and an array both containing the values 1, 2, 3.
// RedBlackTree should typically be allocated using `new`
RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3);
// But `new` should not be used with Array
Array!int array = Array!int(1, 2, 3);
// `make` hides the differences
RedBlackTree!int rbTree2 = make!(RedBlackTree!int)(1, 2, 3);
Array!int array2 = make!(Array!int)(1, 2, 3);

Note that make can infer the element type from the given arguments.

import std.container;
auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!int
auto array = make!Array("1", "2", "3"); // Array!string

Reference semantics

All containers have reference semantics, which means that after assignment both variables refer to the same underlying data.

To make a copy of a container, use the c.dup container primitive.

import std.container, std.range;
Array!int originalArray = make!(Array!int)(1, 2, 3);
Array!int secondArray = originalArray;
assert(equal(originalArray[], secondArray[]));

// changing one instance changes the other one as well!
originalArray[0] = 12;
assert(secondArray[0] == 12);

// secondArray now refers to an independent copy of originalArray
secondArray = originalArray.dup;
secondArray[0] = 1;
// assert that originalArray has not been affected
assert(originalArray[0] == 12);

Attention: If the container is implemented as a class, using an uninitialized instance can cause a null pointer dereference.

import std.container;

RedBlackTree!int rbTree;
rbTree.insert(5); // null pointer dereference

Using an uninitialized struct-based container will work, because the struct intializes itself upon use; however, up to this point the container will not have an identity and assignment does not create two references to the same data.

import std.container;

// create an uninitialized array
Array!int array1;
// array2 does _not_ refer to array1
Array!int array2 = array1;
array2.insertBack(42);
// thus array1 will not be affected
assert(array1.empty);

// after initialization reference semantics work as expected
array1 = array2;
// now affects array2 as well
array1.removeBack();
assert(array2.empty);

It is therefore recommended to always construct containers using make.

This is in fact necessary to put containers into another container. For example, to construct an Array of ten empty Arrays, use the following that calls make ten times.

import std.container, std.range;

auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10));

Submodules

This module consists of the following submodules:

The primary range of a container

While some containers offer direct access to their elements e.g. via opIndex, c.front or c.back, access and modification of a container's contents is generally done through its primary range type, which is aliased as C.Range. For example, the primary range type of Array!int is Array!int.Range.

If the documentation of a member function of a container takes a parameter of type Range, then it refers to the primary range type of this container. Oftentimes Take!Range will be used, in which case the range refers to a span of the elements in the container. Arguments to these parameters must be obtained from the same container instance as the one being worked with. It is important to note that many generic range algorithms return the same range type as their input range.

import std.algorithm.comparison : equal;
import std.algorithm.iteration : find;
import std.container;
import std.range : take;

auto array = make!Array(1, 2, 3);

// `find` returns an Array!int.Range advanced to the element "2"
array.linearRemove(array[].find(2));

assert(array[].equal([1]));

array = make!Array(1, 2, 3);

// the range given to `linearRemove` is a Take!(Array!int.Range)
// spanning just the element "2"
array.linearRemove(array[].find(2).take(1));

assert(array[].equal([1, 3]));

When any range can be passed as an argument to a member function, the documention usually refers to the parameter's templated type as Stuff.

import std.algorithm.comparison : equal;
import std.container;
import std.range : iota;

auto array = make!Array(1, 2);

// the range type returned by `iota` is completely unrelated to Array,
// which is fine for Array.insertBack:
array.insertBack(iota(3, 10));

assert(array[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));

Container primitives

Containers do not form a class hierarchy, instead they implement a common set of primitives (see table below). These primitives each guarantee a specific worst case complexity and thus allow generic code to be written independently of the container implementation.

For example the primitives c.remove(r) and c.linearRemove(r) both remove the sequence of elements in range r from the container c. The primitive c.remove(r) guarantees Ο(nr log nc) complexity in the worst case and c.linearRemove(r) relaxes this guarantee to Ο(nc).

Since a sequence of elements can be removed from a doubly linked list in constant time, DList provides the primitive c.remove(r) as well as c.linearRemove(r). On the other hand Array only offers c.linearRemove(r).

The following table describes the common set of primitives that containers implement. A container need not implement all primitives, but if a primitive is implemented, it must support the syntax described in the syntax column with the semantics described in the description column, and it must not have a worst-case complexity worse than denoted in big-O notation in the Ο(·) column. Below, C means a container type, c is a value of container type, nx represents the effective length of value x, which could be a single element (in which case nx is 1), a container, or a range.

Container primitives
Syntax Ο(·) Description
C(x) nx Creates a container of type C from either another container or a range. The created container must not be a null reference even if x is empty.
c.dup nc Returns a duplicate of the container.
c ~ x nc + nx Returns the concatenation of c and r. x may be a single element or an input range.
x ~ c nc + nx Returns the concatenation of x and c. x may be a single element or an input range type.
    Iteration
c.Range The primary range type associated with the container.
c[] log nc Returns a range iterating over the entire container, in a container-defined order.
c[a .. b] log nc Fetches a portion of the container from key a to key b.
    Capacity
c.empty 1 Returns true if the container has no elements, false otherwise.
c.length log nc Returns the number of elements in the container.
c.length = n nc + n Forces the number of elements in the container to n. If the container ends up growing, the added elements are initialized in a container-dependent manner (usually with T.init).
c.capacity log nc Returns the maximum number of elements that can be stored in the container without triggering a reallocation.
c.reserve(x) nc Forces capacity to at least x without reducing it.
    Access
c.front log nc Returns the first element of the container, in a container-defined order.
c.moveFront log nc Destructively reads and returns the first element of the container. The slot is not removed from the container; it is left initialized with T.init. This routine need not be defined if front returns a ref.
c.front = v log nc Assigns v to the first element of the container.
c.back log nc Returns the last element of the container, in a container-defined order.
c.moveBack log nc Destructively reads and returns the last element of the container. The slot is not removed from the container; it is left initialized with T.init. This routine need not be defined if front returns a ref.
c.back = v log nc Assigns v to the last element of the container.
c[x] log nc Provides indexed access into the container. The index type is container-defined. A container may define several index types (and consequently overloaded indexing).
c.moveAt(x) log nc Destructively reads and returns the value at position x. The slot is not removed from the container; it is left initialized with T.init.
c[x] = v log nc Sets element at specified index into the container.
c[x] op= v log nc Performs read-modify-write operation at specified index into the container.
    Operations
e in c log nc Returns nonzero if e is found in c.
c.lowerBound(v) log nc Returns a range of all elements strictly less than v.
c.upperBound(v) log nc Returns a range of all elements strictly greater than v.
c.equalRange(v) log nc Returns a range of all elements in c that are equal to v.
    Modifiers
c ~= x nc + nx Appends x to c. x may be a single element or an input range type.
c.clear() nc Removes all elements in c.
c.insert(x) nx * log nc Inserts x in c at a position (or positions) chosen by c.
c.stableInsert(x) nx * log nc Same as c.insert(x), but is guaranteed to not invalidate any ranges.
c.linearInsert(v) nc Same as c.insert(v) but relaxes complexity to linear.
c.stableLinearInsert(v) nc Same as c.stableInsert(v) but relaxes complexity to linear.
c.removeAny() log nc Removes some element from c and returns it.
c.stableRemoveAny() log nc Same as c.removeAny(), but is guaranteed to not invalidate any iterators.
c.insertFront(v) log nc Inserts v at the front of c.
c.stableInsertFront(v) log nc Same as c.insertFront(v), but guarantees no ranges will be invalidated.
c.insertBack(v) log nc Inserts v at the back of c.
c.stableInsertBack(v) log nc Same as c.insertBack(v), but guarantees no ranges will be invalidated.
c.removeFront() log nc Removes the element at the front of c.
c.stableRemoveFront() log nc Same as c.removeFront(), but guarantees no ranges will be invalidated.
c.removeBack() log nc Removes the value at the back of c.
c.stableRemoveBack() log nc Same as c.removeBack(), but guarantees no ranges will be invalidated.
c.remove(r) nr * log nc Removes range r from c.
c.stableRemove(r) nr * log nc Same as c.remove(r), but guarantees iterators are not invalidated.
c.linearRemove(r) nc Removes range r from c.
c.stableLinearRemove(r) nc Same as c.linearRemove(r), but guarantees iterators are not invalidated.
c.removeKey(k) log nc Removes an element from c by using its key k. The key's type is defined by the container.

Authors

Steven Schveighoffer, Andrei Alexandrescu

License

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).