This module defines generic containers.

- Construction
- To implement the different containers both struct and class based approaches have been used.
`std.container.util.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.

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

`null`

pointer dereference. import std.container; RedBlackTree!int rbTree; rbTree.insert(5); // null pointer dereferenceUsing 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

`std.container.util.make`

. This is in fact necessary to put containers into another container. For example, to construct an `Array`

of ten empty `Array`

s, 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
`std.container.array`

module provides an array type with deterministic control of memory, not reliant on the GC unlike built-in arrays. - The
`std.container.binaryheap`

module provides a binary heap implementation that can be applied to any user-provided random-access range. - The
`std.container.dlist`

module provides a doubly-linked list implementation. - The
`std.container.rbtree`

module implements red-black trees. - The
`std.container.slist`

module implements singly-linked lists. - The
`std.container.util`

module contains some generic tools commonly used by container implementations.

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

.

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

`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 Ο(`n`_{r} log n_{c}

) complexity in the worst case and `c.linearRemove(r)`

relaxes this guarantee to Ο(`n`_{c}

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

) column. Below, `C`

means a container type, `c`

is a value of container type, `n`_{x}

represents the effective length of value `x`

, which could be a single element (in which case `n`_{x}

is `1`

), a container, or a range. Syntax | Ο(`·` ) | Description |
---|---|---|

`C(x)` | `n` | 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` | `n` | Returns a duplicate of the container. |

`c ~ x` | `n` | Returns the concatenation of `c` and `r` . `x` may be a single element or an input range. |

`x ~ c` | `n` | 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 n` | Returns a range iterating over the entire container, in a container-defined order. |

`c[a .. b]` | `log n` | 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 n` | Returns the number of elements in the container. |

`c.length = n` | `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 n` | Returns the maximum number of elements that can be stored in the container without triggering a reallocation. |

`c.reserve(x)` | `n` | Forces `capacity` to at least `x` without reducing it. |

Access | ||

`c.front` | `log n` | Returns the first element of the container, in a container-defined order. |

`c.moveFront` | `log n` | 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 n` | Assigns `v` to the first element of the container. |

`c.back` | `log n` | Returns the last element of the container, in a container-defined order. |

`c.moveBack` | `log n` | 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 n` | Assigns `v` to the last element of the container. |

`c[x]` | `log n` | 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 n` | 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 n` | Sets element at specified index into the container. |

`c[x] ` | `log n` | Performs read-modify-write operation at specified index into the container. |

Operations | ||

`e in c` | `log n` | Returns nonzero if e is found in `c` . |

`c.lowerBound(v)` | `log n` | Returns a range of all elements strictly less than `v` . |

`c.upperBound(v)` | `log n` | Returns a range of all elements strictly greater than `v` . |

`c.equalRange(v)` | `log n` | Returns a range of all elements in `c` that are equal to `v` . |

Modifiers | ||

`c ~= x` | `n` | Appends `x` to `c` . `x` may be a single element or an input range type. |

`c.clear()` | `n` | Removes all elements in `c` . |

`c.insert(x)` | `n` | Inserts `x` in `c` at a position (or positions) chosen by `c` . |

`c.stableInsert(x)` | `n` | Same as `c.insert(x)` , but is guaranteed to not invalidate any ranges. |

`c.linearInsert(v)` | `n` | Same as `c.insert(v)` but relaxes complexity to linear. |

`c.stableLinearInsert(v)` | `n` | Same as `c.stableInsert(v)` but relaxes complexity to linear. |

`c.removeAny()` | `log n` | Removes some element from `c` and returns it. |

`c.stableRemoveAny()` | `log n` | Same as `c.removeAny()` , but is guaranteed to not invalidate any iterators. |

`c.insertFront(v)` | `log n` | Inserts `v` at the front of `c` . |

`c.stableInsertFront(v)` | `log n` | Same as `c.insertFront(v)` , but guarantees no ranges will be invalidated. |

`c.insertBack(v)` | `log n` | Inserts `v` at the back of `c` . |

`c.stableInsertBack(v)` | `log n` | Same as `c.insertBack(v)` , but guarantees no ranges will be invalidated. |

`c.removeFront()` | `log n` | Removes the element at the front of `c` . |

`c.stableRemoveFront()` | `log n` | Same as `c.removeFront()` , but guarantees no ranges will be invalidated. |

`c.removeBack()` | `log n` | Removes the value at the back of `c` . |

`c.stableRemoveBack()` | `log n` | Same as `c.removeBack()` , but guarantees no ranges will be invalidated. |

`c.remove(r)` | `n` | Removes range `r` from `c` . |

`c.stableRemove(r)` | `n` | Same as `c.remove(r)` , but guarantees iterators are not invalidated. |

`c.linearRemove(r)` | `n` | Removes range `r` from `c` . |

`c.stableLinearRemove(r)` | `n` | Same as `c.linearRemove(r)` , but guarantees iterators are not invalidated. |

`c.removeKey(k)` | `log n` | Removes an element from `c` by using its key `k` . The key's type is defined by the container. |

- Source
- std/container/package.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:
- Steven Schveighoffer, Andrei Alexandrescu

© 1999–2017 The D Language Foundation

Licensed under the Boost License 1.0.

https://dlang.org/phobos/std_container.html