Utility and ancillary artifacts of stdx.collections.
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 O(·) column. Below, C means a _collection type, c is a value of _collection type, n$(SUBSCRIPT x) represents the effective length of value x, which could be a single element (in which case n$(SUBSCRIPT x) is 1), a _collection, or a range.
| Syntax | O(·) | Description |
|---|---|---|
| C(x) | n$(SUBSCRIPT x) | 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 | n$(SUBSCRIPT c) | Returns a duplicate of the _collection. |
| c ~ x | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | Returns the concatenation of c and x. x may be a single element or an input range. |
| x ~ c | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | 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[] | n$(SUBSCRIPT c) | Returns a range iterating over the entire _collection, in a _collection-defined order. |
| c[a .. b] | n$(SUBSCRIPT c) | 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(n$(SUBSCRIPT c), 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 | n$(SUBSCRIPT c) | Returns the maximum number of elements that can be stored in the _collection without triggering a reallocation. |
| c.reserve(x) | n$(SUBSCRIPT c) | 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 n$(SUBSCRIPT c) | Returns the last element of the _collection, in a _collection-defined order. |
| c.back = v | n$(SUBSCRIPT c) | Assigns v to the last element of the _collection. |
| c[x] | n$(SUBSCRIPT c) | 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 | n$(SUBSCRIPT c) | Sets element at specified index into the _collection. |
| c[x] $(I op)= v | n$(SUBSCRIPT c) | Performs read-modify-write operation at specified index into the _collection. |
| Operations | ||
| e in c | n$(SUBSCRIPT c) | Returns nonzero if e is found in c. |
| Modifiers | ||
| c ~= x | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | Appends x to c. x may be a single element or an input range type. |
| c.clear() | n$(SUBSCRIPT c) | Removes all elements in c. |
| c.insert(pos, x) | n$(SUBSCRIPT x) | Inserts x at pos in c. x may be a single element or an input range type. |
| c.insertBack(x) | n$(SUBSCRIPT c) + n$(SUBSCRIPT x) | 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. |
This module defines generic collections.