www.digitalmars.com

D Programming Language 2.0

Last update Sat Jun 12 14:41:25 2010

std.container

Defines generic containers.

License:
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).

Authors:
Andrei Alexandrescu

struct TotalContainer(Whatever);
TotalContainer is an unimplemented container that illustrates a host of primitives that a container may define. It is to some extent the bottom of the conceptual container hierarchy. A given container most often will choose to only implement a subset of these primitives, and define its own additional ones. Adhering to the standard primitive names below allows generic code to work independently of containers.

Things to remember: any container must be a reference type, whether implemented as a class or struct. No primitive below requires the container to escape addresses of elements, which means that compliant containers can be defined to use reference counting or other deterministic memory management techniques.

A container may choose to define additional specific operations. The only requirement is that those operations bear different names than the ones below, lest user code gets confused.

Complexity of operations should be interpreted as "at least as good as". If an operation is required to have Ο(n) complexity, it could have anything lower than that, e.g. Ο(log(n)). Unless specified otherwise, n inside a Ο() expression stands for the number of elements in the container.

alias KeyType;
If the container has a notion of key-value mapping, KeyType defines the type of the key of the container.

alias KeyTypes;
If the container has a notion of multikey-value mapping, KeyTypes[k], where k is a zero-based unsigned number, defines the type of the kth key of the container.

A container may define both KeyType and KeyTypes, e.g. in the case it has the notion of primary/preferred key.

alias ValueType;
If the container has a notion of key-value mapping, ValueType defines the type of the value of the container. Typically, a map-style container mapping values of type K to values of type V defines KeyType to be K, ValueType to be V, and ElementType to be Tuple!(K, V).

alias Range;
Defines the container's primary range, which embodies one of the archetypal ranges defined in std.range.

Generally a container may define several types of ranges.

bool empty();
Property returning true if and only if the container has no elements.

Complexity:
Ο(1)

TotalContainer dup();
Returns a duplicate of the container. The elements themselves are not transitively duplicated.

Complexity:
Ο(n).

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

ElementType front();
ElementType back();
Forward to opSlice().front and opSlice().back, respectively.

Complexity:
Ο(log(n))

ValueType opIndex(KeyType);
void opIndexAssign(KeyType);
template opIndexOpAssign(string op)
Indexing operators yield or modify the value at a specified index.

template opBinary(string op) if (op == "in")
k in container returns true if the given key is in the container.

bool opBinary(KeyType k);
k in container returns true if the given key is in the container.

Range equalRange(KeyType k);
Returns a range of all elements containing k (could be empty or a singleton range).

Range lowerBound(KeyType k);
Returns a range of all elements with keys less than k (could be empty or a singleton range). Only defined by containers that store data sorted at all times.

Range upperBound(KeyType k);
Returns a range of all elements with keys larger than k (could be empty or a singleton range). Only defined by containers that store data sorted at all times.

template opBinary(string op) if (op == "~")
template opBinaryRight(string op) 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

TotalContainer opBinary(Stuff rhs);
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

template opOpAssign(string op) if (op == "~")
Forwards to insertAfter(this[], stuff).

void opOpAssign(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(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 ElementType.init.

Complexity:
Ο(abs(n - newLength))

Postcondition:
length == newLength

size_t insert(Stuff stuff);
size_t stableInsert(Stuff stuff);
Inserts stuff in an unspecified position in the container. Implementations should choose whichever insertion means is the most advantageous for the container, but document the exact behavior. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType.

The stable version guarantees that ranges iterating over the container are never invalidated. Client code that counts on non-invalidating insertion should use stableInsert. Such code would not compile against containers that don't support it.

Returns:
The number of elements added.

Complexity:
Ο(m * log(n)), where m is the number of elements in stuff

ElementType removeAny();
ElementType 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 insertFront(Stuff stuff);
size_t stableInsertFront(Stuff stuff);
size_t insertBack(Stuff stuff);
size_t stableInsertBack(T value);
Inserts value to the front or back of the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of elements inserted

Complexity:
Ο(log(n)).

void removeFront();
void stableRemoveFront();
void removeBack();
void 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)).

size_t removeFront(size_t howMany);
size_t stableRemoveFront(size_t howMany);
size_t removeBack(size_t howMany);
size_t stableRemoveBack(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)).

size_t removeKey(KeyType k);
Removes all values corresponding to key k.

Complexity:
Ο(m * log(n)), where m is the number of elements with the same key.

Returns:
The number of elements removed.

size_t insertBefore(Range r, Stuff stuff);
size_t stableInsertBefore(Range r, Stuff stuff);
size_t insertAfter(Range r, Stuff stuff);
size_t stableInsertAfter(Range r, Stuff stuff);
size_t replace(Range r, Stuff stuff);
size_t stableReplace(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 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 remove(Range r);
Range stableRemove(Range r);
Removes all elements belonging to r, which must be a range obtained originally from this container. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

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

Complexity:
Ο(m * log(n)), where m is the number of elements in r

Range linearRemove(Range r);
Range stableLinearRemove(Range r);
Same as remove above, but has complexity relaxed to linear.

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

Complexity:
Ο(n)

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.

template __ctor(U) if (isImplicitlyConvertible!(U,T))
Constructor taking a number of nodes

template __ctor(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T) && !is(Stuff == T[]))
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();
T front();
void front(T value);
void popFront();
Forward range primitives.

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)

template opBinary(string op,Stuff) 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.

SList opBinary(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)

template insertFront(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template insertFront(Stuff) if (isImplicitlyConvertible!(Stuff,T))
alias insert;
alias stableInsert;
alias stableInsertFront;
Inserts stuff to the front of the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of elements inserted

Complexity:
Ο(log(n))

size_t insertFront(Stuff stuff);
Inserts stuff to the front of the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of elements inserted

Complexity:
Ο(log(n))

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

template insertAfter(Stuff)
Inserts stuff after range r, which must be a range previously extracted from this container. Given that all ranges for a list end at the end of the list, this function essentially appends to the list and uses r as a potentially fast way to reach the last node in the list. (Ideally r is positioned near or at the last element of the list.)

stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of values inserted.

Complexity:
Ο(k + m), where k is the number of elements in r and m is the length of stuff.

size_t insertAfter(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 ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of values inserted.

Complexity:
Ο(k + m), where k is the number of elements in r and m is the length of stuff.

template insertAfter(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.

size_t insertAfter(Take!(Range) r, Stuff stuff);
Similar to insertAfter above, but accepts a range bounded in count. This is important for ensuring fast insertions in the middle of the list. For fast insertions after a specified position r, use insertAfter(take(r, 1), stuff). The complexity of that operation only depends on the number of elements in stuff.

Precondition:
r.original.empty || r.maxLength > 0

Returns:
The number of values inserted.

Complexity:
Ο(k + m), where k is the number of elements in r and m is the length of stuff.

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

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);
template opIndexOpAssign(string op)
Indexing operators yield or modify the value at a specified index.

Precondition:
i < length

Complexity:
Ο(1)

template opBinary(string op,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

Array opBinary(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

template opOpAssign(string op,Stuff) if (op == "~")
Forwards to insertBack(stuff).

void opOpAssign(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 ElementType.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)).

template insertBack(Stuff) if (isImplicitlyConvertible!(Stuff,T))
template insertBack(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
alias insert;
Inserts value to the front or back of the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of elements inserted

Complexity:
Ο(m * log(n)), where m is the number of elements in stuff

size_t insertBack(Stuff stuff);
Inserts value to the front or back of the container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of elements inserted

Complexity:
Ο(m * log(n)), where m is the number of elements in stuff

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

template insertBefore(Stuff) if (isImplicitlyConvertible!(Stuff,T))
template insertBefore(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template insertAfter(Stuff)
template replace(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template replace(Stuff) if (isImplicitlyConvertible!(Stuff,T))
Inserts stuff before, after, or instead range r, which must be a valid range previously extracted from this container. stuff can be a value convertible to ElementType or a range of objects convertible to ElementType. The stable version behaves the same, but guarantees that ranges iterating over the container are never invalidated.

Returns:
The number of values inserted.

Complexity:
Ο(n + m), where m is the length of stuff

size_t insertBefore(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 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 - 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.

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.