Defines generic containers.
Syntax | Ο(·) | Description |
---|---|---|
C(x) | n_{x} | Creates a container of type C from either another container or a range. |
c.dup | n_{c} | Returns a duplicate of the container. |
c ~ x | n_{c} + n_{x} | Returns the concatenation of c and r. x may be a single element or an input range. |
x ~ c | n_{c} + n_{x} | 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 n_{c} | Returns a range iterating over the entire container, in a container-defined order. |
c[a .. b] | log n_{c} | 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 n_{c} | Returns the number of elements in the container. |
c.length = n | n_{c} + 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 n_{c} | Returns the maximum number of elements that can be stored in the container without triggering a reallocation. |
c.reserve(x) | n_{c} | Forces capacity to at least x without reducing it. |
Access | ||
c.front | log n_{c} | Returns the first element of the container, in a container-defined order. |
c.moveFront | log n_{c} | 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 n_{c} | Assigns v to the first element of the container. |
c.back | log n_{c} | Returns the last element of the container, in a container-defined order. |
c.moveBack | log n_{c} | 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 n_{c} | Assigns v to the last element of the container. |
c[x] | log n_{c} | 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 n_{c} | 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 n_{c} | Sets element at specified index into the container. |
c[x] op= v | log n_{c} | Performs read-modify-write operation at specified index into the container. |
Operations | ||
e in c | log n_{c} | Returns nonzero if e is found in c. |
c.lowerBound(v) | log n_{c} | Returns a range of all elements strictly less than v. |
c.upperBound(v) | log n_{c} | Returns a range of all elements strictly greater than v. |
c.equalRange(v) | log n_{c} | Returns a range of all elements in c that are equal to v. |
Modifiers | ||
c ~= x | n_{c} + n_{x} | Appends x to c. x may be a single element or an input range type. |
c.clear() | n_{c} | Removes all elements in c. |
c.insert(x) | n_{x} * log n_{c} | Inserts x in c at a position (or positions) chosen by c. |
c.stableInsert(x) | n_{x} * log n_{c} | Same as c.insert(x), but is guaranteed to not invalidate any ranges. |
c.linearInsert(v) | n_{c} | Same as c.insert(v) but relaxes complexity to linear. |
c.stableLinearInsert(v) | n_{c} | Same as c.stableInsert(v) but relaxes complexity to linear. |
c.removeAny() | log n_{c} | Removes some element from c and returns it. |
c.stableRemoveAny() | log n_{c} | Same as c.removeAny(), but is guaranteed to not invalidate any iterators. |
c.insertFront(v) | log n_{c} | Inserts v at the front of c. |
c.stableInsertFront(v) | log n_{c} | Same as c.insertFront(v), but guarantees no ranges will be invalidated. |
c.insertBack(v) | log n_{c} | Inserts v at the back of c. |
c.stableInsertBack(v) | log n_{c} | Same as c.insertBack(v), but guarantees no ranges will be invalidated. |
c.removeFront() | log n_{c} | Removes the element at the front of c. |
c.stableRemoveFront() | log n_{c} | Same as c.removeFront(), but guarantees no ranges will be invalidated. |
c.removeBack() | log n_{c} | Removes the value at the back of c. |
c.stableRemoveBack() | log n_{c} | Same as c.removeBack(), but guarantees no ranges will be invalidated. |
c.remove(r) | n_{r} * log n_{c} | Removes range r from c. |
c.stableRemove(r) | n_{r} * log n_{c} | Same as c.remove(r), but guarantees iterators are not invalidated. |
c.linearRemove(r) | n_{c} | Removes range r from c. |
c.stableLinearRemove(r) | n_{c} | Same as c.linearRemove(r), but guarantees iterators are not invalidated. |
c.removeKey(k) | log n_{c} | Removes an element from c by using its key k. The key's type is defined by the container. |
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.
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]));
Implements a simple and fast singly-linked list.
Constructor taking a number of nodes
Constructor taking an input range
Comparison for equality.
Defines the container's primary range, which embodies a forward range.
Property returning true if and only if the container has no elements.
Duplicates the container. The elements themselves are not transitively duplicated.
Returns a range that iterates over all elements of the container, in forward order.
Forward to opSlice(). front.
Forward to opSlice(). front(value).
Returns a new SList that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define opBinary.
Removes all contents from the SList.
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.
Picks one value from the front of the container, removes it from the container, and returns it.
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.
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.
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.
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"]));
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.
Removes a range from the list in linear time.
Removes a Take!Range from the list in linear time.
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.
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;
Constructor taking a number of nodes
Constructor taking an input range
Comparison for equality.
Defines the container's primary range, which embodies a bidirectional range.
Property returning true if and only if the container has no elements.
Duplicates the container. The elements themselves are not transitively duplicated.
Returns a range that iterates over all elements of the container, in forward order.
Forward to opSlice(). front.
Forward to opSlice(). front(value).
Forward to opSlice(). back.
Forward to opSlice(). back(value).
Returns a new DList that's the concatenation of this and its argument.
Returns a new DList that's the concatenation of the argument and this
Appends the contents of stuff into this.
Removes all contents from the DList.
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.
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.
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.
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.
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.
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.
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.
Scheduled for deprecation. These methods are not actually stable. Use the standard remove or linearRemove instead.
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.
Comparison for equality.
Defines the container's primary range, which is a random-access range.
Duplicates the container. The elements themselves are not transitively duplicated.
Property returning true if and only if the container has no elements.
Returns the number of elements in the container.
Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion.
Ensures sufficient capacity to accommodate e elements.
Returns a range that iterates over elements of the container, in forward order.
Returns a range that iterates over elements of the container from index a up to (excluding) index b.
Forward to opSlice(). front and opSlice().back, respectively.
Indexing operators yield or modify the value at a specified index.
Slicing operations execute an operation on an entire slice.
Returns a new container that's the concatenation of this and its argument. opBinaryRight is only defined if Stuff does not define opBinary.
Forwards to insertBack(stuff).
Removes all contents from the container. The container decides how capacity is affected.
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.
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.
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.
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.
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.
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.
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 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 ]));
Converts the store s into a heap. If initialSize is specified, only the first initialSize elements in s are transformed into a heap, after which the heap can grow up to r.length (if Store is a range) or indefinitely (if Store is a container with insertBack). Performs Ο(min(r.length, initialSize)) evaluations of less.
Takes ownership of a store. After this, manipulating s may make the heap work incorrectly.
Takes ownership of a store assuming it already was organized as a heap.
Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property .
Returns true if the heap is empty, false otherwise.
Returns a duplicate of the heap. The underlying store must also support a dup method.
Returns the length of the heap.
Returns the capacity of the heap, which is the length of the underlying store (if the store is a range) or the capacity of the underlying store (if the store is a container).
Returns a copy of the front of the heap, which is the largest element according to less.
Clears the heap by detaching it from the underlying store.
Inserts value into the store. If the underlying store is a range and length == capacity, throws an exception.
Removes the largest element from the heap.
Removes the largest element from the heap and returns a copy of it. The element still resides in the heap's store. For performance reasons you may want to use removeFront with heaps of objects that are expensive to copy.
Replaces the largest element in the store with value.
If the heap has room to grow, inserts value into the store and returns true. Otherwise, if less(value, front), calls replaceFront(value) and returns again true. Otherwise, leaves the heap unaffected and returns false. This method is useful in scenarios where the smallest k elements of a set of candidates must be collected.
Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize.
Array specialized for bool. Packs together values efficiently by allocating one bit per element.
Defines the container's primary range.
Property returning true if and only if the container has no elements.
Returns a duplicate of the container. The elements themselves are not transitively duplicated.
Returns the number of elements in the container.
Returns the maximum number of elements the container can store without (a) allocating memory, (b) invalidating iterators upon insertion.
Ensures sufficient capacity to accommodate n elements.
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().
Returns a range that iterates the container between two specified positions.
Equivalent to opSlice(). front and opSlice().back, respectively.
Indexing operators yield or modify the value at a specified index.
Returns a new container that's the concatenation of this and its argument.
Forwards to insertAfter(this[], stuff).
Removes all contents from the container. The container decides how capacity is affected.
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.
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.
Same as insert(stuff) and stableInsert(stuff) respectively, but relax the complexity constraint to linear.
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.
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.
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.
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.
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.
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.
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.
Element type for the tree
The range type for RedBlackTree
Returns true if the range is empty
Returns the first element in the range
Returns the last element in the range
pop the front element from the range
pop the back element from the range
Trivial save implementation, needed for isForwardRange.
Check if any elements exist in the container. Returns false if at least one element exists.
Returns the number of elements in the container.
Duplicate this container. The resulting container contains a shallow copy of the elements.
Fetch a range that spans all the elements in the container.
The front element in the container
The last element in the container
in operator. Check to see if the given element exists in the container.
Compares two trees for equality.
Removes all elements from the container.
Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.
Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.
Remove an element from the container and return its value.
Remove the front element from the container.
Remove the back element from the container.
Removes the given range from the container.
Removes the given Take!Range from the container
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.
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]));
Get a range from the container with all elements that are > e according to the less comparator
Get a range from the container with all elements that are < e according to the less comparator
Get a range from the container with all elements that are == e according to the less comparator
Constructor. Pass in an array of elements, or individual elements to initialize the tree with.
Convenience function for creating a RedBlackTree!E from a list of values.
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);