Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
Container primitives. A container 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 worse worst-case
complexity than denoted in big-O notation in the Ο(·) column.
Below, C means a container type, c is a value of container
type, n represents the effective length of value x,
which could be a single element (in which case nx is 1),
a container, or a range.
Syntax | Ο(·) | Description |
C(x) | nx | Creates a
container of type C from either another container or a range. |
c.dup | nc | Returns a
duplicate of the container. |
c ~ x | nc + nx | Returns the concatenation of c and r. 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.Range | | The primary range
type associated with the container. |
c[] | log nc | Returns a range
iterating over the entire container, in a container-defined order. |
c[a .. b] | log nc | 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 nc | Returns the
number of elements in the container. |
c.length = n | nc + 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 nc | Returns the
maximum number of elements that can be stored in the container
without triggering a reallocation. |
c.reserve(x) | nc | Forces capacity to at least x without reducing it. |
Access |
c.front | log nc | Returns the
first element of the container, in a container-defined order. |
c.moveFront | log nc | 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 front returns a ref. |
c.front = v | log nc | Assigns
v to the first element of the container. |
c.back | log nc | Returns the
last element of the container, in a container-defined order. |
c.moveBack | log nc | 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 front returns a ref. |
c.back = v | log nc | Assigns
v to the last element of the container. |
c[x] | log nc | 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 nc | 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 nc | Sets
element at specified index into the container. |
c[x] op= v | log nc |
Performs read-modify-write operation at specified index into the
container. |
Operations |
e in c | log nc | Returns nonzero if e is found in c. |
c.lowerBound(v) | log nc | Returns a range of all elements strictly less than v. |
c.upperBound(v) | log nc | Returns a range of all elements strictly greater than v. |
c.equalRange(v) | log nc | Returns a range of all elements in c that are equal to v. |
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(x) | nx * log nc |
Inserts x in c at a position (or positions) chosen by c. |
c.stableInsert(x) |
nx * log nc | Same as c.insert(x),
but is guaranteed to not invalidate any ranges. |
c.linearInsert(v) | nc | Same
as c.insert(v) but relaxes complexity to linear. |
c.stableLinearInsert(v) | nc |
Same as c.stableInsert(v) but relaxes complexity to linear. |
c.removeAny() | log nc |
Removes some element from c and returns it. |
c.stableRemoveAny() | log nc |
Same as c.removeAny(), but is guaranteed to not invalidate any
iterators. |
c.insertFront(v) | log nc |
Inserts v at the front of c. |
c.stableInsertFront(v) | log nc |
Same as c.insertFront(v), but guarantees no ranges will be
invalidated. |
c.insertBack(v) | log nc |
Inserts v at the back of c. |
c.stableInsertBack(v) | log nc |
Same as c.insertBack(v), but guarantees no ranges will be
invalidated. |
c.removeFront() | log nc |
Removes the element at the front of c. |
c.stableRemoveFront() | log nc |
Same as c.removeFront(), but guarantees no ranges will be
invalidated. |
c.removeBack() | log nc |
Removes the value at the back of c. |
c.stableRemoveBack() | log nc |
Same as c.removeBack(), but guarantees no ranges will be
invalidated. |
c.remove(r) | nr * log nc |
Removes range r from c. |
c.stableRemove(r) |
nr * log nc |
Same as c.remove(r), but guarantees iterators are not
invalidated. |
c.linearRemove(r) | nc |
Removes range r from c. |
c.stableLinearRemove(r) | nc |
Same as c.linearRemove(r), but guarantees iterators are not
invalidated. |
c.removeKey(k) | log nc |
Removes an element from c by using its key k.
The key's type is defined by the container. |
| | |