Phobos

Github Page

The D Programming Language

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















































































































Container primitives. Below, C means a container type, c is a value of container type, nx represents the effective length of value x, which could be a single element (in which case nx is 1), a container, or a range.
Syntax Ο(·) Description
C(x) nx Creates a container of type C from either another container or a range.
c.dup nc Returns a duplicate of the container.
c ~ x nc + nx Returns the concatenation of c and r. x may be a single element or an input range.
x ~ c nc + nx Returns the concatenation of x and c. x may be a single element or an input range type.
    Iteration
c.Range The primary range type associated with the container.
c[] log nc Returns a range iterating over the entire container, in a container-defined order.
c[a .. b] log nc Fetches a portion of the container from key a to key b.
    Capacity
c.empty 1 Returns true if the container has no elements, false otherwise.
c.length log nc Returns the number of elements in the container.
c.length = n nc + n Forces the number of elements in the container to n. If the container ends up growing, the added elements are initialized in a container-dependent manner (usually with T.init).
c.capacity log nc Returns the maximum number of elements that can be stored in the container without triggering a reallocation.
c.reserve(x) nc Forces capacity to at least x without reducing it.
    Access
c.front log nc Returns the first element of the container, in a container-defined order.
c.moveFront log nc Destructively reads and returns the first element of the container. The slot is not removed from the container; it is left initalized with T.init. This routine need not be defined if front returns a ref.
c.front = v log nc Assigns v to the first element of the container.
c.back log nc Returns the last element of the container, in a container-defined order.
c.moveBack log nc Destructively reads and returns the last element of the  container. The slot is not removed from the container; it is left initalized with T.init. This routine need not be defined if front returns a ref.
c.back = v log nc Assigns v to the last element of the container.
c[x] log nc Provides indexed access into the container. The index type is container-defined. A  container may define several index types (and consequently overloaded indexing).
c.moveAt(x) log nc Destructively reads and returns the value at position x. The slot is not removed from the container; it is left initialized with T.init.
c[x] = v log nc Sets element at specified index into the container.
c[x] op= v log nc Performs read-modify-write operation at specified index into the container.
    Operations
e in c log nc Returns nonzero if e is found in c.
c.lowerBound(v) log nc Returns a range of all elements strictly less than v.
c.upperBound(v) log nc Returns a range of all elements strictly greater than v.
c.equalRange(v) log nc Returns a range of all elements in c that are equal to v.
    Modifiers
c ~= x nc + nx Appends x to c. x may be a single element or an input range type.
c.clear() nc Removes all elements in c.
c.insert(x) nx * log nc Inserts x in c at a position (or positions) chosen by c.
c.stableInsert(x) nx * log nc Same as c.insert(x), but is guaranteed to not invalidate any ranges.
c.linearInsert(v) nc Same as c.insert(v) but relaxes complexity to linear.
c.stableLinearInsert(v) nc Same as c.stableInsert(v) but relaxes complexity to linear.
c.removeAny() log nc Removes some element from c and returns it.
c.stableRemoveAny() log nc Same as c.removeAny(), but is guaranteed to not invalidate any iterators.
c.insertFront(v) log nc Inserts v at the front of c.
c.stableInsertFront(v) log nc Same as c.insertFront(v), but guarantees no ranges will be invalidated.
c.insertBack(v) log nc Inserts v at the back of c.
c.stableInsertBack(v) log nc Same as c.insertBack(v), but guarantees no ranges will be invalidated.
c.removeFront() log nc Removes the element at the front of c.
c.stableRemoveFront() log nc Same as c.removeFront(), but guarantees no ranges will be invalidated.
c.removeBack() log nc Removes the value at the back of c.
c.stableRemoveBack() log nc Same as c.removeBack(), but guarantees no ranges will be invalidated.
c.remove(r) nr * log nc Removes range r from c.
c.stableRemove(r) nr * log nc Same as c.remove(r), but guarantees iterators are not invalidated.
c.linearRemove(r) nc Removes range r from c.
c.stableLinearRemove(r) nc Same as c.linearRemove(r), but guarantees iterators are not invalidated.
c.removeKey(k) log nc Removes an element from c by using its key k. The key's type is defined by the container.

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();
T  front();
void  front(T value);
void  popFront();

Input range primitives.

Range  save();

Forward range primitive.

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)

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();
T  front();
void  front(T value);
void  popFront();

Input range primitives.

Range  save();

Forward range primitive.

T  back();
void  back(T value);
void  popBack();

Bidirectional range primitives.

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.

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.

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

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

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

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, 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(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();
T  moveBack();
void  popBack();
T  opIndex(size_t i);
void  opIndexAssign(T value, size_t i);
T  moveAt(size_t i);
const ulong  length();

Range primitives

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) 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(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 = 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))

ulong  insertBack(Stuff)(Stuff stuff) if (is(Stuff : bool));
ulong  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)).

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 = insertBefore;
ulong  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:
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 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);