stdx.collections

Collection primitives Collections do not form a class hierarchy, instead they implement a common set of primitives (see table below). These primitives each guarantee a specific worst case complexity and thus allow generic code to be written independently of the collection implementation.

The following table describes the common set of primitives that collections implement. A collection need not implement all primitives, but if a primitive is implemented, it must support the syntax described in the syntax column with the semantics described in the description column, and it must not have a worst-case complexity worse than denoted in big-O notation in the Ο(·) column. Below, C means a collection type, c is a value of collection type, n_x represents the effective length of value x, which could be a single element (in which case n_x is 1), a collection, or a range.

collection primitives

Syntax	Ο(·)	Description
C(x)	nx	Creates a collection of type C from either another collection, a range or an element. The created collection must not be a null reference even if x is empty.
c.dup	nc	Returns a duplicate of the collection.
c ~ x	nc + nx	Returns the concatenation of c and x. 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.popFront()	1	Advances to the next element in the collection.
c.save	1	Return a shallow copy of the collection.
c[]	nc	Returns a range iterating over the entire collection, in a collection-defined order.
c[a .. b]	nc	Fetches a portion of the collection from key a to key b.
Capacity
c.empty	1	Returns true if the collection has no elements, false otherwise.
c.length	1	Returns the number of elements in the collection.
c.length = n	max(nc, n)	Forces the number of elements in the collection to n. If the collection ends up growing, the added elements are initialized in a collection-dependent manner (usually with T.init).
c.capacity	nc	Returns the maximum number of elements that can be stored in the collection without triggering a reallocation.
c.reserve(x)	nc	Forces capacity to at least x without reducing it.
Access
c.front	1	Returns the first element of the collection, in a collection-defined order.
c.front = v	1	Assigns v to the first element of the collection.
c.back	log nc	Returns the last element of the collection, in a collection-defined order.
c.back = v	nc	Assigns v to the last element of the collection.
c[x]	nc	Provides indexed access into the collection. The index type is collection-defined. A collection may define several index types (and consequently overloaded indexing).
c[x] = v	nc	Sets element at specified index into the collection.
c[x] op= v	nc	Performs read-modify-write operation at specified index into the collection.
Operations
e in c	nc	Returns nonzero if e is found in c.
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(pos, x)	nx	Inserts x at pos in c. x may be a single element or an input range type.
c.insertBack(x)	nc + nx	Inserts x at the back of c. x may be a single element or an input range type.
c.remove()	1	Removes the front element of c.