Utility and ancillary artifacts of stdx.collection.
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.