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
Class / struct Name | Description |
---|---|
Array | 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. |
BinaryHeap | 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. |
RedBlackTree | Implementation of a red-black tree container. |
SList | Implements a simple and fast singly-linked list. |
Function Name | Description |
---|---|
heapify | Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize. |
make | Returns an initialized container. This function is mainly for eliminating construction differences between class containers and struct containers. |
redBlackTree | Convenience function for creating a RedBlackTree!E from a list of values. |
- Container make(Container, T...)(T arguments);
Container make(Container, T...)(T arguments); - Returns an initialized container. This function is mainly for eliminating construction differences between class containers and struct containers.
- struct SList(T);
- Implements a simple and fast singly-linked list.
Member Quick Reference Member Name Description Range Defines the container's primary range, which embodies a forward range. clear Removes all contents from the SList. dup Duplicates the container. The elements themselves are not transitively duplicated. empty Forward range primitives. front Forward range primitives. insert 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. insertAfter 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. insertFront 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. linearRemove Removes a Take!Range from the list in linear time. opBinary Returns a new SList that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define opBinary. opEquals Comparison for equality. opSlice Returns a range that iterates over all elements of the container, in forward order. popFront Forward range primitives. removeAny Picks one value from the front of the container, removes it from the container, and returns it. removeFront 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. save Forward range primitives. stableInsert 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. stableInsertAfter 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. stableInsertFront 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. stableLinearRemove Removes a Take!Range from the list in linear time. stableRemoveAny Picks one value from the front of the container, removes it from the container, and returns it. stableRemoveFront 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. - this(U)(U[] values...);
- Constructor taking a number of nodes
- this(Stuff)(Stuff stuff);
- Constructor taking an input range
- const bool opEquals(ref const SList rhs);
- Comparison for equality.
Complexity:
Ο(min(n, n1)) where n1 is the number of elements in rhs. - struct Range;
- Defines the container's primary range, which embodies a forward range.
- const bool empty();
- Property returning true if and only if the container has no
elements.
Complexity:
Ο(1) - SList dup();
- Duplicates the container. The elements themselves are not transitively
duplicated.
Complexity:
Ο(n). - Range opSlice();
- Returns a range that iterates over all elements of the container, in
forward order.
Complexity:
Ο(1) - T front();
- Forward to opSlice().front.
Complexity:
Ο(1) - void front(T value);
- Forward to opSlice().front(value).
Complexity:
Ο(1) - SList opBinary(string op, Stuff)(Stuff rhs);
- Returns a new SList that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define opBinary.
- void clear();
- Removes all contents from the SList.
Postcondition:
empty Complexity:
Ο(1) - size_t insertFront(Stuff)(Stuff stuff);
size_t insertFront(Stuff)(Stuff stuff);
alias insert;
alias stableInsert;
alias stableInsertFront; - 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)) - T removeAny();
alias stableRemoveAny; - 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). - void removeFront();
alias stableRemoveFront; - 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). - size_t removeFront(size_t howMany);
alias stableRemoveFront; - 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)). - size_t insertAfter(Stuff)(Range r, Stuff 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 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. - size_t insertAfter(Stuff)(Take!(Range) r, Stuff stuff);
alias stableInsertAfter; - 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. - Range linearRemove(Range r);
- Removes a range from the list in linear time.
Returns:
An empty range. Complexity:
Ο(n) - Range linearRemove(Take!(Range) r);
alias stableLinearRemove; - Removes a Take!Range from the list in linear time.
Returns:
A range comprehending the elements after the removed range. Complexity:
Ο(n)
- struct Array(T) if (!is(T : const(bool)));
- 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.
Member Quick Reference Member Name Description Range Defines the container's primary range, which is a random-access range. back Forward to opSlice().front and opSlice().back, respectively. capacity Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion. clear Removes all contents from the container. The container decides how capacity is affected. dup Duplicates the container. The elements themselves are not transitively duplicated. empty Property returning true if and only if the container has no elements. front Forward to opSlice().front and opSlice().back, respectively. insert 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. insertAfter 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. insertBack 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. insertBefore 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. length Returns the number of elements in the container. linearRemove 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. opBinary Returns a new container that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define opBinary. opDollar @@@BUG@@@ This doesn't work yet opEquals Comparison for equality. opIndex Indexing operators yield or modify the value at a specified index. opIndexAssign Indexing operators yield or modify the value at a specified index. opIndexOpAssign Indexing operators yield or modify the value at a specified index. opOpAssign Forwards to insertBack(stuff). opSlice Returns a range that iterates over elements of the container from index a up to (excluding) index b. removeAny 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. removeBack 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. replace 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. reserve Ensures sufficient capacity to accommodate e elements. stableLinearRemove 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. stableRemoveAny 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. stableRemoveBack 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. - const bool opEquals(ref const Array rhs);
- Comparison for equality.
- struct Range;
- Defines the container's primary range, which is a random-access range.
- const bool empty();
- Property returning true if and only if the container has no
elements.
Complexity:
Ο(1) - Array dup();
- Duplicates the container. The elements themselves are not transitively
duplicated.
Complexity:
Ο(n). - const size_t length();
- Returns the number of elements in the container.
Complexity:
Ο(1). - size_t capacity();
- Returns the maximum number of elements the container can store without
(a) allocating memory, (b) invalidating iterators upon insertion.
Complexity:
Ο(1) - void reserve(size_t elements);
- Ensures sufficient capacity to accommodate e elements.
Postcondition:
capacity >= e Complexity:
Ο(1) - Range opSlice();
- Returns a range that iterates over elements of the container, in
forward order.
Complexity:
Ο(1) - Range opSlice(size_t a, size_t b);
- 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) - const size_t opDollar();
- @@@BUG@@@ This doesn't work yet
- T front();
void front(T value);
T back();
void back(T value); - Forward to opSlice().front and opSlice().back, respectively.
Precondition:
!empty Complexity:
Ο(1) - T opIndex(size_t i);
void opIndexAssign(T value, size_t i);
void opIndexOpAssign(string op)(T value, size_t i); - Indexing operators yield or modify the value at a specified index.
Precondition:
i < length Complexity:
Ο(1) - Array opBinary(string op, Stuff)(Stuff stuff);
- 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 - void opOpAssign(string op, Stuff)(Stuff stuff);
- Forwards to insertBack(stuff).
- void clear();
- Removes all contents from the container. The container decides how capacity is affected.
Postcondition:
empty Complexity:
Ο(n) - void length(size_t newLength);
- 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 - T removeAny();
alias stableRemoveAny; - 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)). - size_t insertBack(Stuff)(Stuff stuff);
alias insert; - 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 - void removeBack();
alias stableRemoveBack; - 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)). - size_t removeBack(size_t howMany);
alias stableRemoveBack; - 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). - size_t insertBefore(Stuff)(Range r, Stuff stuff);
size_t insertBefore(Stuff)(Range r, Stuff stuff);
size_t insertAfter(Stuff)(Range r, Stuff stuff);
size_t replace(Stuff)(Range r, Stuff stuff);
size_t replace(Stuff)(Range r, Stuff 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 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 - Range linearRemove(Range r);
alias stableLinearRemove; - 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
- struct BinaryHeap(Store,alias less = "a < b") if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])));
- 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 ]));
Member Quick Reference Member Name Description acquire Takes ownership of a store. After this, manipulating s may make the heap work incorrectly. assume Takes ownership of a store assuming it already was organized as a heap. capacity 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). clear Clears the heap by detaching it from the underlying store. conditionalInsert 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. dup Returns a duplicate of the heap. The underlying store must also support a dup method. empty Returns true if the heap is empty, false otherwise. front Returns a copy of the front of the heap, which is the largest element according to less. insert Inserts value into the store. If the underlying store is a range and length == capacity, throws an exception. length Returns the length of the heap. release Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property. removeAny 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. removeFront Removes the largest element from the heap. replaceFront Replaces the largest element in the store with value. - 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.
- void acquire(Store s, size_t initialSize = size_t.max);
- Takes ownership of a store. After this, manipulating s may make the heap work incorrectly.
- void assume(Store s, size_t initialSize = size_t.max);
- Takes ownership of a store assuming it already was organized as a heap.
- auto release();
- Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property.
- bool empty();
- Returns true if the heap is empty, false otherwise.
- BinaryHeap dup();
- Returns a duplicate of the heap. The underlying store must also support a dup method.
- size_t length();
- Returns the length of the heap.
- size_t capacity();
- 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).
- ElementType!(Store) front();
- Returns a copy of the front of the heap, which is the largest element according to less.
- void clear();
- Clears the heap by detaching it from the underlying store.
- size_t insert(ElementType!(Store) value);
- Inserts value into the store. If the underlying store is a range and length == capacity, throws an exception.
- void removeFront();
- Removes the largest element from the heap.
- ElementType!(Store) removeAny();
- 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.
- void replaceFront(ElementType!(Store) value);
- Replaces the largest element in the store with value.
- bool conditionalInsert(ElementType!(Store) 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.
- BinaryHeap!(Store) heapify(Store)(Store s, size_t initialSize = size_t.max);
- Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize.
- struct Array(T) if (is(T == bool));
- Array specialized for bool. Packs together values efficiently by
allocating one bit per element.
Member Quick Reference Member Name Description Range Defines the container's primary range. back Equivalent to opSlice().front and opSlice().back, respectively. capacity Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion. clear Removes all contents from the container. The container decides how capacity is affected. dup Returns a duplicate of the container. The elements themselves are not transitively duplicated. empty Property returning true if and only if the container has no elements. front Range primitives insert Inserts stuff in the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. insertAfter 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. insertBack 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. insertBefore 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. length Range primitives linearInsert Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear. linearRemove 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. moveAt Range primitives moveBack Range primitives moveFront Range primitives opBinary Returns a new container that's the concatenation of this and its argument. opIndex Range primitives opIndexAssign Indexing operators yield or modify the value at a specified index. opIndexOpAssign Indexing operators yield or modify the value at a specified index. opOpAssign Forwards to insertAfter(this[], stuff). opSlice Returns a range that iterates the container between two specified positions. popBack Range primitives popFront Range primitives removeAny 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. removeBack 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. replace 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. reserve Ensures sufficient capacity to accommodate n elements. save Range primitives stableInsert Inserts stuff in the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. stableInsertAfter 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. stableInsertBack 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. stableInsertBefore 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. stableLinearInsert Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear. stableLinearRemove 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. stableRemoveAny 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. stableRemoveBack 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. stableReplace 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. - struct Range;
- Defines the container's primary range.
- bool empty();
- Property returning true if and only if the container has
no elements.
Complexity:
Ο(1) - Array!(bool) dup();
- Returns a duplicate of the container. The elements themselves
are not transitively duplicated.
Complexity:
Ο(n). - ulong length();
- Returns the number of elements in the container.
Complexity:
Ο(log(n)). - ulong capacity();
- Returns the maximum number of elements the container can store
without (a) allocating memory, (b) invalidating iterators upon
insertion.
Complexity:
Ο(log(n)). - void reserve(ulong e);
- Ensures sufficient capacity to accommodate n elements.
Postcondition:
capacity >= n Complexity:
Ο(log(e - capacity)) if e > capacity, otherwise Ο(1). - Range opSlice();
- 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)) - Range opSlice(ulong a, ulong b);
- Returns a range that iterates the container between two
specified positions.
Complexity:
Ο(log(n)) - bool front();
void front(bool value);
bool back();
void back(bool value); - Equivalent to opSlice().front and opSlice().back,
respectively.
Complexity:
Ο(log(n)) - bool opIndex(ulong i);
void opIndexAssign(bool value, ulong i);
void opIndexOpAssign(string op)(bool value, ulong i);
T moveAt(ulong i); - Indexing operators yield or modify the value at a specified index.
- Array!(bool) opBinary(string op, Stuff)(Stuff rhs);
- 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 - Array!(bool) opOpAssign(string op, Stuff)(Stuff stuff);
- Forwards to insertAfter(this[], stuff).
- void clear();
- Removes all contents from the container. The container decides
how capacity is affected.
Postcondition:
empty Complexity:
Ο(n) - void length(ulong newLength);
- 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 - alias insert;
alias stableInsert; - 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 - alias linearInsert;
alias stableLinearInsert; - Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear.
- T removeAny();
alias stableRemoveAny; - 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)) - ulong insertBack(Stuff)(Stuff stuff);
ulong insertBack(Stuff)(Stuff stuff);
alias stableInsertBack; - 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)) - void removeBack();
alias stableRemoveBack; - 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)). - ulong removeBack(ulong howMany);
- 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 - ulong insertBefore(Stuff)(Range r, Stuff stuff);
alias stableInsertBefore;
ulong insertAfter(Stuff)(Range r, Stuff stuff);
alias stableInsertAfter;
size_t replace(Stuff)(Range r, Stuff stuff);
alias stableReplace; - 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 - Range linearRemove(Range r);
alias stableLinearRemove; - 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)
- class RedBlackTree(T,alias less = "a < b",bool allowDuplicates = false) if (is(typeof(binaryFun!(less)(T.init,T.init))));
- 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.
Member Quick Reference Member Name Description Elem Element type for the tree Range The range type for RedBlackTree back Returns the last element in the range clear Removes all elements from the container. dup Duplicate this container. The resulting container contains a shallow copy of the elements. empty Returns true if the range is empty equalRange Get a range from the container with all elements that are == e according to the less comparator front The front element in the container insert Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container. length Returns the number of elements in the container. lowerBound Get a range from the container with all elements that are < e according to the less comparator opBinaryRight in operator. Check to see if the given element exists in the container. opSlice Fetch a range that spans all the elements in the container. popBack pop the back element from the range popFront pop the front element from the range remove Removes the given range from the container. removeAny Remove an element from the container and return its value. removeBack Remove the back element from the container. removeFront Remove the front element from the container. removeKey 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. save Trivial save implementation, needed for isForwardRange. stableInsert Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container. upperBound Get a range from the container with all elements that are > e according to the less comparator - alias Elem;
- Element type for the tree
- struct Range;
- The range type for RedBlackTree
- const bool empty();
- Returns true if the range is empty
- Elem front();
- Returns the first element in the range
- Elem back();
- Returns the last element in the range
- void popFront();
- pop the front element from the range
complexity:
amortized Ο(1) - void popBack();
- pop the back element from the range
complexity:
amortized Ο(1) - Range save();
- Trivial save implementation, needed for isForwardRange.
- bool empty();
- Check if any elements exist in the container. Returns true if at least one element exists.
- size_t length();
- Returns the number of elements in the container.
Complexity:
Ο(1). - RedBlackTree dup();
- Duplicate this container. The resulting container contains a shallow
copy of the elements.
Complexity:
Ο(n) - Range opSlice();
- Fetch a range that spans all the elements in the container.
Complexity:
Ο(log(n)) - Elem front();
- The front element in the container
Complexity:
Ο(log(n)) - Elem back();
- The last element in the container
Complexity:
Ο(log(n)) - bool opBinaryRight(string op)(Elem e);
- in operator. Check to see if the given element exists in the
container.
Complexity:
Ο(log(n)) - void clear();
- Removes all elements from the container.
Complexity:
Ο(1) - size_t stableInsert(Stuff)(Stuff stuff);
- Insert a single element in the container. Note that this does not
invalidate any ranges currently iterating the container.
Complexity:
Ο(log(n)) - size_t stableInsert(Stuff)(Stuff stuff);
alias insert; - Insert a range of elements in the container. Note that this does not
invalidate any ranges currently iterating the container.
Complexity:
Ο(m * log(n)) - Elem removeAny();
- Remove an element from the container and return its value.
Complexity:
Ο(log(n)) - void removeFront();
- Remove the front element from the container.
Complexity:
Ο(log(n)) - void removeBack();
- Remove the back element from the container.
Complexity:
Ο(log(n)) - Range remove(Range r);
- 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) - Range remove(Take!(Range) r);
- 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) - size_t removeKey(U)(U[] elems...);
size_t removeKey(Stuff)(Stuff stuff); - 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]));
- Range upperBound(Elem e);
- Get a range from the container with all elements that are > e according
to the less comparator
Complexity:
Ο(log(n)) - Range lowerBound(Elem e);
- Get a range from the container with all elements that are < e according
to the less comparator
Complexity:
Ο(log(n)) - Range equalRange(Elem e);
- 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.
- auto redBlackTree(E)(E[] elems...);
auto redBlackTree(bool allowDuplicates, E)(E[] elems...);
auto redBlackTree(alias less, E)(E[] elems...);
auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...); - 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);