// Written in the D programming language. /**This module defines generic containers. $(H3 $(LNAME2 construction, Construction)) To implement the different containers, both struct and class basedapproaches have been used. $(REF make, std,container,util) allows foruniform construction with either approach. $(RUNNABLE_EXAMPLE---import std.container;// Construct a red-black tree and an array both containing the values 1, 2, 3.// RedBlackTree should typically be allocated using `new`RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3);// But `new` should not be used with ArrayArray!int array = Array!int(1, 2, 3); // `make` hides the differencesRedBlackTree!int rbTree2 = make!(RedBlackTree!int)(1, 2, 3);Array!int array2 = make!(Array!int)(1, 2, 3); assert(rbTree == rbTree2);assert(array == array2);---) Note that `make` can infer the element type from the given arguments. ---import std.container; auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!intauto array = make!Array("1", "2", "3"); // Array!string--- $(H3 $(LNAME2 reference-semantics, Reference Semantics)) All containers have reference semantics, which means that afterassignment both variables refer to the same underlying data. To make a copy of a container, use the `c.dup` container primitive. $(RUNNABLE_EXAMPLE---import std.algorithm, std.container, std.range; Array!int originalArray = make!(Array!int)(1, 2, 3);Array!int secondArray = originalArray;assert(equal(originalArray[], secondArray[])); // changing one instance changes the other one as well!originalArray[0] = 12;assert(secondArray[0] == 12); // secondArray now refers to an independent copy of originalArraysecondArray = originalArray.dup;secondArray[0] = 1;// assert that originalArray has not been affectedassert(originalArray[0] == 12);---) $(B Attention:) If the container is implemented as a class, using anuninitialized instance can cause a null pointer dereference. ---import std.container; RedBlackTree!int rbTree;rbTree.insert(5); // null pointer dereference--- Using an uninitialized struct-based container will work, because the structintializes itself upon use; however, up to this point the container will nothave an identity and assignment does not create two references to the samedata. $(RUNNABLE_EXAMPLE---import std.container; // create an uninitialized arrayArray!int array1;// array2 does _not_ refer to array1Array!int array2 = array1;array2.insertBack(42);// thus array1 will not be affectedassert(array1.empty); // after initialization reference semantics work as expectedarray1 = array2;// now affects array2 as wellarray1.removeBack();assert(array2.empty);---) It is therefore recommended to always construct containers using$(REF make, std,container,util). This is in fact necessary to put containers into another container.For example, to construct an `Array` of ten empty `Array`s, usethe following that calls `make` ten times. ---import std.container, std.range; auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10));--- $(H3 $(LNAME2 submodules, Submodules)) This module consists of the following submodules: $(UL    $(LI        The $(MREF std, container, array) module provides        an array type with deterministic control of memory, not reliant on        the GC unlike built-in arrays.    )    $(LI        The $(MREF std, container, binaryheap) module        provides a binary heap implementation that can be applied to any        user-provided random-access range.    )    $(LI        The $(MREF std, container, dlist) module provides        a doubly-linked list implementation.    )    $(LI        The $(MREF std, container, rbtree) module        implements red-black trees.    )    $(LI        The $(MREF std, container, slist) module        implements singly-linked lists.    )    $(LI        The $(MREF std, container, util) module contains        some generic tools commonly used by container implementations.    )) $(H3 $(LNAME2 primary-range, The Primary Range of a Container)) While some containers offer direct access to their elements e.g. via`opIndex`, `c.front` or `c.back`, accessand modification of a container's contents is generally done throughits primary $(MREF_ALTTEXT range, std, range) type,which is aliased as `C.Range`. For example, the primary range type of`Array!int` is `Array!int.Range`. If the documentation of a member function of a container takesa parameter of type `Range`, then it refers to the primary range type ofthis container. Oftentimes `Take!Range` will be used, in which casethe range refers to a span of the elements in the container. Arguments tothese parameters $(B must) be obtained from the same container instanceas the one being worked with. It is important to note that many generic rangealgorithms return the same range type as their input range. $(RUNNABLE_EXAMPLE---import std.algorithm.comparison : equal;import std.algorithm.searching : find;import std.container;import std.range : take; auto array = make!Array(1, 2, 3); // `find` returns an Array!int.Range advanced to the element "2"array.linearRemove(array[].find(2)); assert(array[].equal([1])); array = make!Array(1, 2, 3); // the range given to `linearRemove` is a Take!(Array!int.Range)// spanning just the element "2"array.linearRemove(array[].find(2).take(1)); assert(array[].equal([1, 3]));---) When any $(MREF_ALTTEXT range, std, range) can be passed as an argument toa member function, the documention usually refers to the parameter's templatedtype as `Stuff`. $(RUNNABLE_EXAMPLE---import std.algorithm.comparison : equal;import std.container;import std.range : iota; auto array = make!Array(1, 2); // the range type returned by `iota` is completely unrelated to Array,// which is fine for Array.insertBack:array.insertBack(iota(3, 10)); assert(array[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));---) $(H3 $(LNAME2 primitives, Container Primitives)) Containers do not form a class hierarchy, instead they implement acommon set of primitives (see table below). These primitives each guaranteea specific worst case complexity and thus allow generic code to be writtenindependently of the container implementation. For example the primitives `c.remove(r)` and `c.linearRemove(r)` bothremove the sequence of elements in range `r` from the container `c`.The primitive `c.remove(r)` guarantees$(BIGOH n$(SUBSCRIPT r) log n$(SUBSCRIPT c)) complexity in the worst case and`c.linearRemove(r)` relaxes this guarantee to $(BIGOH n$(SUBSCRIPT c)). Since a sequence of elements can be removed from a $(MREF_ALTTEXT doubly linked list,std,container,dlist)in constant time, `DList` provides the primitive `c.remove(r)`as well as `c.linearRemove(r)`. On the other hand$(MREF_ALTTEXT Array, std,container, array) only offers `c.linearRemove(r)`. The following table describes the common set of primitives that containersimplement.  A container need not implement all primitives, but if aprimitive is implemented, it must support the syntax described in the $(Bsyntax) column with the semantics described in the $(B description) column, andit must not have a worst-case complexity worse than denoted in big-O notation inthe $(BIGOH ·) column.  Below, `C` means a container type, `c` isa value of container type, $(D n$(SUBSCRIPT x)) represents the effective length ofvalue `x`, which could be a single element (in which case $(D n$(SUBSCRIPT x)) is`1`), a container, or a range. $(BOOKTABLE Container primitives,$(TR    $(TH Syntax)    $(TH $(BIGOH ·))    $(TH Description))$(TR    $(TDNW `C(x)`)    $(TDNW $(D n$(SUBSCRIPT x)))    $(TD Creates a container of type `C` from either another container or a range.    The created container must not be a null reference even if x is empty.))$(TR    $(TDNW `c.dup`)    $(TDNW $(D n$(SUBSCRIPT c)))    $(TD Returns a duplicate of the container.))$(TR    $(TDNW $(D c ~ x))    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))    $(TD Returns the concatenation of `c` and `r`. `x` may be a single        element or an input range.))$(TR    $(TDNW $(D x ~ c))    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))    $(TD Returns the concatenation of `x` and `c`.  `x` may be a        single element or an input range type.))$(LEADINGROWN 3, Iteration)$(TR    $(TD `c.Range`)    $(TD)    $(TD The primary range type associated with the container.))$(TR    $(TD `c[]`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns a range         iterating over the entire container, in a container-defined order.))$(TR    $(TDNW $(D c[a .. b]))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Fetches a portion of the container from key `a` to key `b`.))$(LEADINGROWN 3, Capacity)$(TR    $(TD `c.empty`)    $(TD `1`)    $(TD Returns `true` if the container has no elements, `false` otherwise.))$(TR    $(TD `c.length`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns the number of elements in the container.))$(TR    $(TDNW $(D c.length = n))    $(TDNW $(D n$(SUBSCRIPT c) + n))    $(TD 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`).))$(TR    $(TD `c.capacity`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns the maximum number of elements that can be stored in the    container without triggering a reallocation.))$(TR    $(TD `c.reserve(x)`)    $(TD $(D n$(SUBSCRIPT c)))    $(TD Forces `capacity` to at least `x` without reducing it.))$(LEADINGROWN 3, Access)$(TR    $(TDNW `c.front`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns the first element of the container, in a container-defined order.))$(TR    $(TDNW `c.moveFront`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Destructively reads and returns the first element of the         container. The slot is not removed from the container; it is left         initialized with `T.init`. This routine need not be defined if $(D         front) returns a `ref`.))$(TR    $(TDNW $(D c.front = v))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Assigns `v` to the first element of the container.))$(TR    $(TDNW `c.back`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns the last element of the container, in a container-defined order.))$(TR    $(TDNW `c.moveBack`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Destructively reads and returns the last element of the         container. The slot is not removed from the container; it is left         initialized with `T.init`. This routine need not be defined if $(D         front) returns a `ref`.))$(TR    $(TDNW $(D c.back = v))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Assigns `v` to the last element of the container.))$(TR    $(TDNW `c[x]`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Provides indexed access into the container. The index type is         container-defined. A container may define several index types (and         consequently overloaded indexing).))$(TR    $(TDNW `c.moveAt(x)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Destructively reads and returns the value at position `x`. The slot         is not removed from the container; it is left initialized with $(D         T.init).))$(TR    $(TDNW $(D c[x] = v))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Sets element at specified index into the container.))$(TR    $(TDNW $(D c[x] $(I op)= v))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Performs read-modify-write operation at specified index into the        container.))$(LEADINGROWN 3, Operations)$(TR    $(TDNW $(D e in c))    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns nonzero if e is found in `c`.))$(TR    $(TDNW `c.lowerBound(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns a range of all elements strictly less than `v`.))$(TR    $(TDNW `c.upperBound(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns a range of all elements strictly greater than `v`.))$(TR    $(TDNW `c.equalRange(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Returns a range of all elements in `c` that are equal to `v`.))$(LEADINGROWN 3, Modifiers)$(TR    $(TDNW $(D c ~= x))    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))    $(TD Appends `x` to `c`. `x` may be a single element or an input range type.))$(TR    $(TDNW `c.clear()`)    $(TDNW $(D n$(SUBSCRIPT c)))    $(TD Removes all elements in `c`.))$(TR    $(TDNW `c.insert(x)`)    $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c)))    $(TD Inserts `x` in `c` at a position (or positions) chosen by `c`.))$(TR    $(TDNW `c.stableInsert(x)`)    $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c)))    $(TD Same as `c.insert(x)`, but is guaranteed to not invalidate any ranges.))$(TR    $(TDNW `c.linearInsert(v)`)    $(TDNW $(D n$(SUBSCRIPT c)))    $(TD Same as `c.insert(v)` but relaxes complexity to linear.))$(TR    $(TDNW `c.stableLinearInsert(v)`)    $(TDNW $(D n$(SUBSCRIPT c)))    $(TD Same as `c.stableInsert(v)` but relaxes complexity to linear.))$(TR    $(TDNW `c.removeAny()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Removes some element from `c` and returns it.))$(TR    $(TDNW `c.stableRemoveAny()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Same as `c.removeAny()`, but is guaranteed to not invalidate any         iterators.))$(TR    $(TDNW `c.insertFront(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Inserts `v` at the front of `c`.))$(TR    $(TDNW `c.stableInsertFront(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Same as `c.insertFront(v)`, but guarantees no ranges will be         invalidated.))$(TR    $(TDNW `c.insertBack(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Inserts `v` at the back of `c`.))$(TR    $(TDNW `c.stableInsertBack(v)`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Same as `c.insertBack(v)`, but guarantees no ranges will be         invalidated.))$(TR    $(TDNW `c.removeFront()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Removes the element at the front of `c`.))$(TR    $(TDNW `c.stableRemoveFront()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Same as `c.removeFront()`, but guarantees no ranges will be         invalidated.))$(TR    $(TDNW `c.removeBack()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Removes the value at the back of `c`.))$(TR    $(TDNW `c.stableRemoveBack()`)    $(TDNW $(D log n$(SUBSCRIPT c)))    $(TD Same as `c.removeBack()`, but guarantees no ranges will be         invalidated.))$(TR    $(TDNW `c.remove(r)`)    $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c)))    $(TD Removes range `r` from `c`.))$(TR    $(TDNW `c.stableRemove(r)`)    $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c)))    $(TD Same as `c.remove(r)`, but guarantees iterators are not         invalidated.))$(TR    $(TDNW `c.linearRemove(r)`)    $(TDNW $(D n$(SUBSCRIPT c)))    $(TD Removes range `r` from `c`.))

Lines 1–500 of 1173. Load more