# std.container

Defines generic containers.**Source:**

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

- Returns an initialized container. This function is mainly for eliminating construction differences between class containers and struct containers.
- Implements a simple and fast singly-linked list.
- this(U)(U[]
*values*...); - Constructor taking a number of nodes
- this(Stuff)(Stuff
*stuff*); - Constructor taking an input range
- Comparison for equality.
**Complexity:**

**Ο****(**min(n, n1)**)**where n1 is the number of elements in*rhs*. - Defines the container's primary range, which embodies a forward range.
- Forward range primitives.

- Property returning
**true**if and only if the container has no elements.**Complexity:**

**Ο****(**1**)** - Duplicates the container. The elements themselves are not transitively
duplicated.
**Complexity:**

**Ο****(**n**)**. - Returns a range that iterates over all elements of the container, in
forward order.
**Complexity:**

**Ο****(**1**)** - Forward to opSlice().
__front__.**Complexity:**

**Ο****(**1**)** - Forward to opSlice().
__front__(*value*).**Complexity:**

**Ο****(**1**)** - Returns a new SList that's the concatenation of this and its
argument. opBinaryRight is only defined if Stuff does not
define
__opBinary__. - Removes all contents from the SList.
**Postcondition:**

empty**Complexity:**

**Ο****(**1**)** - Inserts stuff to the front 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)**)** - Picks one value from the front of the container, removes it from the
container, and returns it.
**Precondition:**

!empty**Returns:**

The element removed.**Complexity:**

**Ο****(**1**)**. - Removes the value at the front of the container. The stable version
behaves the same, but guarantees that ranges iterating over the
container are never invalidated.
**Precondition:**

!empty**Complexity:**

**Ο****(**1**)**. - 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)**)**. - Inserts stuff after range r, which must be a range
previously extracted from this container. Given that all ranges for a
list end at the end of the list, this function essentially appends to
the list and uses r as a potentially fast way to reach the last
node in the list. (Ideally r is positioned near or at the last
element of the list.)
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. - Similar to
__insertAfter__above, but accepts a range bounded in count. This is important for ensuring fast insertions in the middle of the list. For fast insertions after a specified position r, use__insertAfter__(take(r, 1), stuff). The complexity of that operation only depends on the number of elements in stuff.**Precondition:**

r.original.empty || r.maxLength > 0**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. - Removes a range from the list in linear time.
**Returns:**

An empty range.**Complexity:**

**Ο****(**n**)** - Removes a Take!Range from the list in linear time.
**Returns:**

A range comprehending the elements after the removed range.**Complexity:**

**Ο****(**n**)**

__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.- Comparison for equality.
- Defines the container's primary range, which is a random-access range.
- Property returning
**true**if and only if the container has no elements.**Complexity:**

**Ο****(**1**)** - Duplicates the container. The elements themselves are not transitively
duplicated.
**Complexity:**

**Ο****(**n**)**. - Returns the number of elements in the container.
**Complexity:**

**Ο****(**1**)**. - Returns the maximum number of elements the container can store without
(a) allocating memory, (b) invalidating iterators upon insertion.
**Complexity:**

**Ο****(**1**)** - Ensures sufficient capacity to accommodate e
*elements*.**Postcondition:**

capacity >= e**Complexity:**

**Ο****(**1**)** - Returns a range that iterates over elements of the container, in
forward order.
**Complexity:**

**Ο****(**1**)** - 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**)** - @@@BUG@@@ This doesn't work yet
- Forward to opSlice().
__front__and opSlice().back, respectively.**Precondition:**

!empty**Complexity:**

**Ο****(**1**)** - Indexing operators yield or modify the value at a specified index.
**Precondition:**

*i*< length**Complexity:**

**Ο****(**1**)** - 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 - Forwards to insertBack(stuff).
- Removes all contents from the container. The container decides how capacity is affected.
**Postcondition:**

empty**Complexity:**

**Ο****(**n**)** - 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* - Picks one value in an unspecified position in the container, removes
it from the container, and returns it. Implementations should pick the
value that's the most advantageous for the container, but document the
exact behavior. 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)**)**. - 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 - 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)**)**. - 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***)**. - 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 - 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*

- Implements a binary heap
container on top of a given random-access range type (usually T[]) or a random-access container type (usually Array!T). The
documentation of
__BinaryHeap__will refer to the underlying range or container as the*store*of the heap. The binary heap induces structure over the underlying store such that accessing the largest element (by using the front property) is a**Ο****(**1**)**operation and extracting it (by using the removeFront() method) is done fast in**Ο****(**log n**)**time. If less is the less-than operator, which is the default option, then__BinaryHeap__defines a so-called max-heap that optimizes extraction of the*largest*elements. To define a min-heap, instantiate__BinaryHeap__with "a > b" as its predicate. Simply extracting elements from a__BinaryHeap__container is tantamount to lazily fetching elements of Store in descending order. Extracting elements from the__BinaryHeap__to completion leaves the underlying store sorted in ascending order but, again, yields elements in descending order. If Store is a range, the__BinaryHeap__cannot grow beyond the size of that range. If Store is a container that supports insertBack, the__BinaryHeap__may grow by adding elements to the container.**Example:**

// Example from "Introduction to Algorithms" Cormen et al, p 146 int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; auto h = heapify(a); // largest element assert(h.front == 16); // a has the heap property assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ]));

- this(Store
*s*, size_t*initialSize*= size_t.max); - Converts the store
*s*into a heap. If*initialSize*is specified, only the first*initialSize*elements in*s*are transformed into a heap, after which the heap can grow up to r.length (if Store is a range) or indefinitely (if Store is a container with insertBack). Performs**Ο****(**min(r.length,*initialSize*)**)**evaluations of less. - Takes ownership of a store. After this, manipulating
*s*may make the heap work incorrectly. - Takes ownership of a store assuming it already was organized as a heap.
- Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property.
- Returns
**true**if the heap is empty,**false**otherwise. - Returns a duplicate of the heap. The underlying store must also
support a
__dup__method. - Returns the length of the heap.
- Returns the capacity of the heap, which is the length of the underlying store (if the store is a range) or the capacity of the underlying store (if the store is a container).
- Returns a copy of the front of the heap, which is the largest element according to less.
- Clears the heap by detaching it from the underlying store.
- Inserts
*value*into the store. If the underlying store is a range and length == capacity, throws an exception. - Removes the largest element from the heap.
- Removes the largest element from the heap and returns a copy of it. The element still resides in the heap's store. For performance reasons you may want to use removeFront with heaps of objects that are expensive to copy.
- Replaces the largest element in the store with
*value*. - If the heap has room to grow, inserts
*value*into the store and returns**true**. Otherwise, if less(*value*, front), calls replaceFront(*value*) and returns again**true**. Otherwise, leaves the heap unaffected and returns**false**. This method is useful in scenarios where the smallest k elements of a set of candidates must be collected.

- Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize.
- Array specialized for bool. Packs together values efficiently by
allocating one bit per element.
- Defines the container's primary range.
- Range primitives

- Property returning
**true**if and only if the container has no elements.**Complexity:**

**Ο****(**1**)** - Returns a duplicate of the container. The elements themselves
are not transitively duplicated.
**Complexity:**

**Ο****(**n**)**. - Returns the number of elements in the container.
**Complexity:**

**Ο****(**log(n)**)**. - Returns the maximum number of elements the container can store
without (a) allocating memory, (b) invalidating iterators upon
insertion.
**Complexity:**

**Ο****(**log(n)**)**. - Ensures sufficient capacity to accommodate n elements.
**Postcondition:**

capacity >= n**Complexity:**

**Ο****(**log(*e*- capacity)**)**if*e*> capacity, otherwise**Ο****(**1**)**. - 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)**)** - Returns
*a*range that iterates the container between two specified positions.**Complexity:**

**Ο****(**log(n)**)** - Equivalent to opSlice().
__front__and opSlice().back, respectively.**Complexity:**

**Ο****(**log(n)**)** - Indexing operators yield or modify the value at a specified index.
- 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 - Forwards to insertAfter(this[], stuff).
- Removes all contents from the container. The container decides
how capacity is affected.
**Postcondition:**

empty**Complexity:**

**Ο****(**n**)** - 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* - 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 - Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear.
- 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)**)** - 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)**)** - 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)**)**. - 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 - 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 - 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**)**

- Implementation of a red-black tree container.
All inserts, removes, searches, and any function in general has complexity
of
**Ο****(**lg(n)**)**. To use a different comparison than "a < b", pass a different operator string that can be used by std.functional.binaryFun, or pass in a function, delegate, functor, or any type where less(a, b) results in a bool value. Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal**false**. If allowDuplicates is set to**true**, then inserting the same element more than once continues to add more elements. If it is**false**, duplicate elements are ignored on insertion. If duplicates are allowed, then new elements are inserted after all existing duplicate elements.- Element type for the tree
- The range type for RedBlackTree
- Returns
**true**if the range is empty - Returns the first element in the range
- Returns the last element in the range
- pop the front element from the range
**complexity:**

amortized**Ο****(**1**)** - pop the back element from the range
**complexity:**

amortized**Ο****(**1**)** - Trivial save implementation, needed for isForwardRange.

- Check if any elements exist in the container. Returns
**true**if at least one element exists. - Returns the number of elements in the container.
**Complexity:**

**Ο****(**1**)**. - Duplicate this container. The resulting container contains a shallow
copy of the elements.
**Complexity:**

**Ο****(**n**)** - Fetch a range that spans all the elements in the container.
**Complexity:**

**Ο****(**log(n)**)** - The
__front__element in the container**Complexity:**

**Ο****(**log(n)**)** - The last element in the container
**Complexity:**

**Ο****(**log(n)**)** - in operator. Check to see if the given element exists in the
container.
**Complexity:**

**Ο****(**log(n)**)** - Removes all elements from the container.
**Complexity:**

**Ο****(**1**)** - Insert a single element in the container. Note that this does not
invalidate any ranges currently iterating the container.
**Complexity:**

**Ο****(**log(n)**)** - Insert a range of elements in the container. Note that this does not
invalidate any ranges currently iterating the container.
**Complexity:**

**Ο****(**m * log(n)**)** - Remove an element from the container and return its value.
**Complexity:**

**Ο****(**log(n)**)** - Remove the front element from the container.
**Complexity:**

**Ο****(**log(n)**)** - Remove the back element from the container.
**Complexity:**

**Ο****(**log(n)**)** - Removes the given range from the container.
**Returns:**

A range containing all of the elements that were after the given range.**Complexity:**

**Ο****(**m * log(n)**)**(where m is the number of elements in the range) - Removes the given Take!Range from the container
**Returns:**

A range containing all of the elements that were after the given range.**Complexity:**

**Ο****(**m * log(n)**)**(where m is the number of elements in the range) - Removes elements from the container that are equal to the given values
according to the less comparator. One element is removed for each value
given which is in the container. If allowDuplicates is
**true**, duplicates are removed only if duplicate values are given.**Returns:**

The number of elements removed.**Complexity:**

**Ο****(**m log(n)**)**(where m is the number of elements to remove)**Examples:**auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7); rbt.removeKey(1, 4, 7); assert(std.algorithm.equal(rbt[], [0, 1, 1, 5])); rbt.removeKey(1, 1, 0); assert(std.algorithm.equal(rbt[], [5]));

- Get a range from the container with all elements that are >
*e*according to the less comparator**Complexity:**

**Ο****(**log(n)**)** - Get a range from the container with all elements that are <
*e*according to the less comparator**Complexity:**

**Ο****(**log(n)**)** - Get a range from the container with all elements that are ==
*e*according to the less comparator**Complexity:**

**Ο****(**log(n)**)** - this();
- this(Elem[]
*elems*...); - Constructor. Pass in an array of elements, or individual elements to initialize the tree with.

- Convenience function for creating a RedBlackTree!E from a list of
values.
**Examples:**auto rbt1 = redBlackTree(0, 1, 5, 7); auto rbt2 = redBlackTree!string("hello", "world"); auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5); auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7); auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);