phobos ~master (2021-10-14T15:40:57Z)

- arraymodule 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.- binaryheapmodule std.container.binaryheap
This module provides a

`BinaryHeap`(aka priority queue) adaptor that makes a binary heap out of any user-provided random-access range.- dlistmodule std.container.dlist
This module implements a generic doubly-linked list container. It can be used as a queue, dequeue or stack.

- rbtreemodule std.container.rbtree
This module implements a red-black tree container.

- slistmodule std.container.slist
This module implements a singly-linked list container. It can be used as a stack.

- utilmodule std.container.util
This module contains some common utilities used by containers.

- std.container.arraypublic
`import std.container.array;`

- std.container.binaryheappublic
`import std.container.binaryheap;`

- std.container.dlistpublic
`import std.container.dlist;`

- std.container.rbtreepublic
`import std.container.rbtree;`

- std.container.slistpublic
`import std.container.slist;`

- TotalContainerstruct TotalContainer(T)
- Undocumented in source.

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

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

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
*O*(n_{r} log n_{c}) complexity in the worst case and
`c.linearRemove(r)` relaxes this guarantee to *O*(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 **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 *O*(·) column. Below, `C` means a container type, `c` is
a value of container type, `n$(SUBSCRIPT x)` represents the effective length of
value `x`, which could be a single element (in which case `n$(SUBSCRIPT x)` is
`1`), a container, or a range.

Syntax | O(·) | Description |
---|---|---|

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

c ~ x | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | Returns the concatenation of c and r. x may be a single
element or an input range. |

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

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

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

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

Access | ||

c.front | log n$(SUBSCRIPT c) | Returns the first element of the container, in a container-defined order. |

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

c.back | log n$(SUBSCRIPT c) | Returns the last element of the container, in a container-defined order. |

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

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

c[x] $(I op)= v | log n$(SUBSCRIPT c) | Performs read-modify-write operation at specified index into the container. |

Operations | ||

e in c | log n$(SUBSCRIPT c) | Returns nonzero if e is found in c. |

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

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

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

Modifiers | ||

c ~= x | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | Appends x to c. x may be a single element or an input range type. |

c.clear() | n$(SUBSCRIPT c) | Removes all elements in c. |

c.insert(x) | n$(SUBSCRIPT x) * log n$(SUBSCRIPT c) | Inserts x in c at a position (or positions) chosen by c. |

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

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

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

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

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

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

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

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

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

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

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

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

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

c.remove(r) | n$(SUBSCRIPT r) * log n$(SUBSCRIPT c) | Removes range r from c. |

c.stableRemove(r) | n$(SUBSCRIPT r) * log n$(SUBSCRIPT c) | Same as c.remove(r), but guarantees iterators are not
invalidated. |

c.linearRemove(r) | n$(SUBSCRIPT c) | Removes range r from c. |

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

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

Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

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.

Note that

makecan infer the element type from the given arguments.