Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
Page wiki
View or edit the community-maintained wiki page associated with this page.

# 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

- template make(T) if (is(T == struct) || is(T == class))
- Returns an initialized object. This function is mainly for eliminating
construction differences between structs and classes. It allows code to not
worry about whether the type it's constructing is a struct or a class.
**Examples:**auto arr = make!(Array!int)([4, 2, 3, 1]); assert(equal(arr[], [4, 2, 3, 1])); auto rbt = make!(RedBlackTree!(int, "a > b"))([4, 2, 3, 1]); assert(equal(rbt[], [4, 3, 2, 1])); alias make!(DList!int) makeList; auto list = makeList([1, 7, 42]); assert(equal(list[], [1, 7, 42]));

- struct SList(T);
- Implements a simple and fast singly-linked list.
- this(U)(U[]
*values*...) if (isImplicitlyConvertible!(U, T)); - Constructor taking a number of nodes
- this(Stuff)(Stuff
*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[])); - Constructor taking an input range
- const bool opEquals(const SList
*rhs*);

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*) if (op == "~" && is(typeof(SList(*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*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t insertFront(Stuff)(Stuff*stuff*) if (isImplicitlyConvertible!(Stuff, T));

alias insert = insertFront;

alias stableInsert = insert;

alias stableInsertFront = 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.
**Returns:**

The number of elements inserted**Complexity:**

m*Ο*(, where m is the length of stuff*)* - T removeAny();

alias stableRemoveAny = removeAny; - 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 = 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.
**Precondition:**

!empty**Complexity:**

1*Ο*(.*)* - size_t removeFront(size_t
*howMany*);

alias stableRemoveFront = removeFront; - 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.*)***Examples:**auto sl = SList!string(["a", "b", "d"]); sl.insertAfter(sl[], "e"); // insert at the end (slowest) assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"])); sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b" assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));

- size_t insertAfter(Stuff)(Take!Range
*r*, Stuff*stuff*);

alias stableInsertAfter = 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.
**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 = linearRemove; - Removes a Take!Range from the list in linear time.
**Returns:**

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

n*Ο*(*)*

- this(U)(U[]
- struct DList(T);
- Implements a doubly-linked list.
DList uses neither reference nor value semantics. They can be seen as
several different handles into an external chain of nodes. Several different
DLists can all reference different points in a same chain.
DList.Range is, for all intents and purposes, a DList with range
semantics. The DList.Range has a view directly into the chain itself.
It is not tied to its parent DList, and may be used to operate on
other lists (that point to the same chain).
The ONLY operation that can invalidate a DList or DList.Range, but
which will invalidate BOTH, is the remove operation, if the cut Range
overlaps with the boundaries of another DList or DList.Range.
**Example:**

auto a = DList!int([3, 4]); //Create a new chain auto b = a; //Point to the same chain // (3 - 4) assert(a[].equal([3, 4])); assert(b[].equal([3, 4])); b.stableInsertFront(1); //insert before of b b.stableInsertBack(5); //insert after of b // (2 - (3 - 4) - 5) assert(a[].equal([3, 4])); //a is not changed assert(b[].equal([1, 3, 4, 5])); // but b is changed a.stableInsertFront(2); //insert in front of a, this will insert "inside" the chain // (1 - (2 - 3 - 4) - 5) assert(a[].equal([2, 3, 4])); //a is modified assert(b[].equal([1, 2, 3, 4, 5])); //and so is b; a.remove(a[]); //remove all the elements of a: This will cut them from the chain; // (1 - 5) assert(a[].empty); //a is empty assert(b[].equal([1, 5])); //b has lost some of its elements; a.insert(2); //insert in a. This will create a new chain // (2) // (1 - 5) assert(a[].equal([2])); //a is a new chain assert(b[].equal([1, 5])); //b is unchanged;

- this(U)(U[]
*values*...) if (isImplicitlyConvertible!(U, T)); - Constructor taking a number of nodes
- this(Stuff)(Stuff
*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[])); - Constructor taking an input range
- const bool opEquals(ref const DList
*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 bidirectional range.
- bool empty();
- Property returning
**true**if and only if the container has no elements.**Complexity:**

1*Ο*(*)* - DList 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*Ο*(*)* - T back();
- Forward to opSlice().back.
**Complexity:**

1*Ο*(*)* - void back(T
*value*); - Forward to opSlice().back(
*value*).**Complexity:**

1*Ο*(*)* - DList opBinary(string op, Stuff)(Stuff
*rhs*) if (op == "~" && isImplicitlyConvertible!(Stuff, T));

DList opBinary(string op, Stuff)(Stuff*rhs*) if (op == "~" && (is(Stuff == DList) || is(typeof(DList(*rhs*))))); - Returns a new DList that's the concatenation of this and its argument.
- DList opBinaryRight(string op, Stuff)(Stuff
*rhs*) if (op == "~" && isImplicitlyConvertible!(Stuff, T));

DList opBinaryRight(string op, Stuff)(Stuff*rhs*) if (op == "~" && isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)); - Returns a new DList that's the concatenation of the argument and this
- DList opOpAssign(string op, Stuff)(Stuff
*rhs*) if (op == "~" && isImplicitlyConvertible!(Stuff, T));

DList opOpAssign(string op, Stuff)(Stuff*rhs*) if (op == "~" && isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)); - Appends the contents of stuff into this.
- void clear();
- Removes all contents from the DList.
**Postcondition:**

empty**Complexity:**

1*Ο*(*)* - size_t insertFront(Stuff)(Stuff
*stuff*);

size_t insertBack(Stuff)(Stuff*stuff*);

alias insert = insertBack;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

alias stableInsertBack = insertBack; - Inserts stuff to the front/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:**

log(n)*Ο*(*)* - T removeAny();

alias stableRemoveAny = removeAny; - Picks one value from the front of the container, removes it from the
container, and returns it.
Elements are not actually removed from the chain, but the DList's,
first/last pointer is advanced.
**Precondition:**

!empty**Returns:**

The element removed.**Complexity:**

1*Ο*(.*)* - void removeFront();

alias stableRemoveFront = removeFront;

void removeBack();

alias stableRemoveBack = removeBack; - Removes the value at the front/back of the container. The stable version
behaves the same, but guarantees that ranges iterating over the
container are never invalidated.
Elements are not actually removed from the chain, but the DList's,
first/last pointer is advanced.
**Precondition:**

!empty**Complexity:**

1*Ο*(.*)* - size_t removeFront(size_t
*howMany*);

alias stableRemoveFront = removeFront;

size_t removeBack(size_t*howMany*);

alias stableRemoveBack = removeBack; - 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. Elements are not actually removed from the chain, but the DList's, first/last pointer is advanced.**Returns:**

The number of elements removed**Complexity:**

*Ο*(*howMany** log(n).*)* - size_t insertBefore(Stuff)(Range
*r*, Stuff*stuff*);

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range*r*, Stuff*stuff*);

alias stableInsertAfter = insertAfter; - Inserts stuff after range r, which must be a non-empty 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.
Elements are not actually removed from the chain, but the DList's,
first/last pointer is advanced.
**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 remove(Range
*r*);

Range linearRemove(R)(R*r*) if (is(R == Range));

Range linearRemove(R)(R*r*) if (is(R == Range)); - Removes all elements belonging to
*r*, which must be a range obtained originally from this container. This function actually removes the elements from the chain. This is the only function that may invalidate a range, as it cuts the chain of elements: Ranges (and other DList) that contain*r*or that are inside*r*, as well a*r*itself, are never invalidated. Ranges (and other DList) which partially overlap with*r*will be cut, and invalidated.**Returns:**

A range spanning the remaining elements in the container that initially were right after*r*.**Complexity:**

1*Ο*(*)* - Range linearRemove(R)(R
*r*) if (is(R == Take!Range)); - linearRemove functions as remove, but also accepts ranges that are
result the of a take operation. This is a convenient way to remove a
fixed amount of elements from the range.
**Complexity:**

r.walkLength*Ο*(*)* - alias stableRemove = remove;

alias stableLinearRemove = linearRemove; - Scheduled for deprecation. These methods are not actually stable. Use the standard remove or linearRemove instead.

- this(U)(U[]
- struct Array(T) if (!is(Unqual!T == 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.
- this(U)(U[]
*values*...) if (isImplicitlyConvertible!(U, T)); - Constructor taking a number of items
- this(Stuff)(Stuff
*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[])); - Constructor taking an input range
- const bool opEquals(const Array
*rhs*);

const bool opEquals(ref const Array*rhs*); - Comparison for equality.
- struct Range;
- Defines the container's primary range, which is a random-access range.
- Array dup();
- Duplicates the container. The elements themselves are not transitively
duplicated.
**Complexity:**

n*Ο*(.*)* - const bool empty();
- Property returning
**true**if and only if the container has no elements.**Complexity:**

1*Ο*(*)* - const size_t length();

const size_t opDollar(); - 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
*i*, size_t*j*); - 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*Ο*(*)* - 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 opIndexUnary(string op)(size_t*i*) if (op == "++" || op == "--");

T opIndexUnary(string op)(size_t*i*) if (op != "++" && op != "--");

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*Ο*(*)* - void opSliceAssign(T
*value*);

void opSliceUnary(string op)(size_t*i*, size_t*j*) if (op == "++" || op == "--");

void opSliceOpAssign(string op)(T*value*);

void opSliceOpAssign(string op)(T*value*, size_t*i*, size_t*j*); - Slicing operations execute an operation on an entire slice.
**Precondition:**

i < j && j < length**Complexity:**

slice.length*Ο*(*)* - Array opBinary(string op, Stuff)(Stuff
*stuff*) if (op == "~"); - 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*) if (op == "~"); - 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 = 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.
**Precondition:**

!empty**Returns:**

The element removed.**Complexity:**

log(n)*Ο*(.*)* - size_t insertBack(Stuff)(Stuff
*stuff*) if (isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

alias insert = 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.
**Returns:**

The number of elements inserted**Complexity:**

m * log(n)*Ο*(, where m is the number of elements in stuff*)* - void removeBack();

alias stableRemoveBack = 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.
**Precondition:**

!empty**Complexity:**

log(n)*Ο*(.*)* - size_t removeBack(size_t
*howMany*);

alias stableRemoveBack = removeBack; - 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*) if (isImplicitlyConvertible!(Stuff, T));

size_t insertBefore(Stuff)(Range*r*, Stuff*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t insertAfter(Stuff)(Range*r*, Stuff*stuff*);

size_t replace(Stuff)(Range*r*, Stuff*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t replace(Stuff)(Range*r*, Stuff*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 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 = remove; - 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*

- this(U)(U[]
- 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 a1*Ο*(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). Performsmin(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.

- this(Store
- BinaryHeap!(Store, less) heapify(alias less = "a < b", 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(Unqual!T == bool));
- Array specialized for bool. Packs together values efficiently by
allocating one bit per element.
- struct Range;
- Defines the container's primary range.
- Range save();

bool empty();

T front();

void front(bool*value*);

T moveFront();

void popFront();

T back();

void back(bool*value*);

T moveBack();

void popBack();

T opIndex(size_t*i*);

void opIndexAssign(T*value*, size_t*i*);

T moveAt(size_t*i*);

const size_t length();

Range opSlice(size_t*low*, size_t*high*); - Range primitives

- Range save();
- bool empty();
- Property returning
**true**if and only if the container has no elements.**Complexity:**

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

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

log(n)*Ο*(.*)* - size_t 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(size_t
*e*); - Ensures sufficient capacity to accommodate n elements.
**Postcondition:**

capacity >= n**Complexity:**

log(*Ο*(*e*- capacity)if*)**e*> capacity, otherwise1*Ο*(.*)* - 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(size_t
*a*, size_t*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(size_t
*i*);

void opIndexAssign(bool*value*, size_t*i*);

void opIndexOpAssign(string op)(bool*value*, size_t*i*);

T moveAt(size_t*i*); - Indexing operators yield or modify the value at a specified index.
- Array!bool opBinary(string op, Stuff)(Stuff
*rhs*) if (op == "~"); - 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*) if (op == "~"); - 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(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 the container and initialized with
ElementType.init.
**Complexity:**

abs(n -*Ο*(*newLength*)*)***Postcondition:**

length ==*newLength* - alias insert = insertBack;

alias stableInsert = insertBack; - 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 = insertBack;

alias stableLinearInsert = insertBack; - Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear.
- T removeAny();

alias stableRemoveAny = 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.
**Precondition:**

!empty**Returns:**

The element removed.**Complexity:**

log(n)*Ο*(*)* - size_t insertBack(Stuff)(Stuff
*stuff*) if (is(Stuff : bool));

size_t insertBack(Stuff)(Stuff*stuff*) if (isInputRange!Stuff && is(ElementType!Stuff : bool));

alias stableInsertBack = 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.
**Returns:**

The number of elements inserted**Complexity:**

log(n)*Ο*(*)* - void removeBack();

alias stableRemoveBack = 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.
**Precondition:**

!empty**Complexity:**

log(n)*Ο*(.*)* - size_t removeBack(size_t
*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*)* - size_t insertBefore(Stuff)(Range
*r*, Stuff*stuff*);

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range*r*, Stuff*stuff*);

alias stableInsertAfter = insertAfter;

size_t replace(Stuff)(Range*r*, Stuff*stuff*) if (is(Stuff : bool));

alias stableReplace = 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.
**Returns:**

The number of values inserted.**Complexity:**

n + m*Ο*(, where m is the length of stuff*)* - Range linearRemove(Range
*r*);

alias stableLinearRemove = 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.**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.- alias Elem = T;
- 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:**

amortized1*Ο*(*)* - void popBack();
- pop the back element from the range
**complexity:**

amortized1*Ο*(*)* - Range save();
- Trivial save implementation, needed for isForwardRange.

- bool empty();
- Check if any elements exist in the container. Returns
**false**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*) if (op == "in"); - in operator. Check to see if the given element exists in the
container.
**Complexity:**

log(n)*Ο*(*)* - bool opEquals(Object
*rhs*); - Compares two trees for equality.
**Complexity:**

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

1*Ο*(*)* - size_t stableInsert(Stuff)(Stuff
*stuff*) if (isImplicitlyConvertible!(Stuff, Elem)); - 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*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem));

alias insert = stableInsert; - 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*) if (allSatisfy!(isImplicitlyConvertibleToElem, U));

size_t removeKey(U)(U[]*elems*) if (isImplicitlyConvertible!(U, Elem));

size_t removeKey(Stuff)(Stuff*stuff*) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !isDynamicArray!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*...) if (is(typeof(binaryFun!less(E.init, E.init)))); - 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);