std.container
Defines generic containers. 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
- TotalContainer is an unimplemented container that illustrates a
host of primitives that a container may define. It is to some extent
the bottom of the conceptual container hierarchy. A given container
most often will choose to only implement a subset of these primitives,
and define its own additional ones. Adhering to the standard primitive
names below allows generic code to work independently of containers.
Things to remember: any container must be a reference type, whether
implemented as a class or struct. No primitive below
requires the container to escape addresses of elements, which means
that compliant containers can be defined to use reference counting or
other deterministic memory management techniques.
A container may choose to define additional specific operations. The
only requirement is that those operations bear different names than
the ones below, lest user code gets confused.
Complexity of operations should be interpreted as "at least as good
as". If an operation is required to have Ο(n) complexity, it
could have anything lower than that, e.g. Ο(log(n)). Unless
specified otherwise, n inside a Ο() expression stands for
the number of elements in the container.
- If the container has a notion of key-value mapping, KeyType defines the type of the key of the container.
- If the container has a notion of multikey-value mapping, KeyTypes[k], where k is a zero-based unsigned number, defines the type of the kth key of the container. A container may define both KeyType and KeyTypes, e.g. in the case it has the notion of primary/preferred key.
- If the container has a notion of key-value mapping, ValueType defines the type of the value of the container. Typically, a map-style container mapping values of type K to values of type V defines KeyType to be K, ValueType to be V, and ElementType to be Tuple!(K, V).
- Defines the container's primary range, which embodies one of the archetypal ranges defined in std.range. Generally a container may define several types of ranges.
- 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)) - Forward to opSlice().front and opSlice().back, respectively.
Complexity:
Ο(log(n)) - Indexing operators yield or modify the value at a specified index.
- k in container returns true if the given key is in the container.
- k in container returns true if the given key is in the container.
- Returns a range of all elements containing k (could be empty or a singleton range).
- Returns a range of all elements with keys less than k (could be empty or a singleton range). Only defined by containers that store data sorted at all times.
- Returns a range of all elements with keys larger than k (could be empty or a singleton range). Only defined by containers that store data sorted at all times.
- 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 insertAfter(this[], 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
unspecified positions in the container and initialized with ElementType.init.
Complexity:
Ο(abs(n - newLength)) Postcondition:
length == newLength - Inserts stuff in an unspecified position in the
container. Implementations should choose whichever insertion means is
the most advantageous for the container, but document the exact
behavior. 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. Such code would
not compile against containers that don't support it.
Returns:
The number of elements added. Complexity:
Ο(m * log(n)), where m is the number of elements in stuff - 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 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)). - Removes all values corresponding to key k.
Complexity:
Ο(m * log(n)), where m is the number of elements with the same key. Returns:
The number of elements removed. - 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:
Ο(m * log(n)), where m is the number of elements in r - Same as remove above, but has complexity relaxed to linear.
Returns:
A range spanning the remaining elements in the container that initially were right after r. Complexity:
Ο(n)
- 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.
- Constructor taking a number of nodes
- 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 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))- Inserts stuff to the front 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))
- 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 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:
Ο(k + m), where k is the number of elements in r and m is the length of stuff.- 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 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:
Ο(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.- 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.
- 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).
- 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 ElementType.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 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:
Ο(m * log(n)), where m is the number of elements in stuff- Inserts value to the front or 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:
Ο(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). - template insertBefore(Stuff) if (isImplicitlyConvertible!(Stuff,T))
template insertBefore(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template insertAfter(Stuff)
template replace(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template replace(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 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- 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 - 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.
- 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.