Most of the requirements on containers are presented in the ISO standard - in the form of tables. In order to avoid massive duplication of effort - while documenting all the classes, we follow the standard's lead and - present the base information here. Individual classes will only document - their departures from these tables (removed functions, additional functions, - changes, etc). -
- -We will not try to duplicate all of the surrounding text (footnotes, - explanations, etc) from the standard, because that would also entail a - duplication of effort. Some of the surrounding text has been paraphrased - here for clarity. If you are uncertain about the meaning or interpretation - of these notes, consult a good textbook, and/or purchase your own copy of - the standard (it's cheap, see our FAQ). -
- -The table numbers are the same as those used in the standard. Tables can - be jumped to using their number, e.g., "tables.html#67". Only - Tables 65 through 69 are presented. Some of the active Defect Reports - are also noted or incorporated. -
- --
| -Anything calling itself a container must meet these minimum requirements. - | ||||
|---|---|---|---|---|
| expression | -result type | -operational semantics | -notes, pre-/post-conditions, assertions | -complexity | -
| X::value_type | -T | -- | T is Assignable | -compile time | -
| X::reference | -lvalue of T | -- | - | compile time | -
| X::const_reference | -const lvalue of T | -- | - | compile time | -
| X::iterator | -iterator type pointing to T | -- | Any iterator category except output iterator. - Convertible to X::const_iterator. | -compile time | -
| X::const_iterator | -iterator type pointing to const T | -- | Any iterator category except output iterator. | -compile time | -
| X::difference_type | -signed integral type | -- | identical to the difference type of X::iterator and X::const_iterator | -compile time | -
| X::size_type | -unsigned integral type | -- | size_type can represent any non-negative value of difference_type | -compile time | -
| X u; | -- | - | post: u.size() == 0 | -constant | -
| X(); | -- | - | X().size == 0 | -constant | -
| X(a); | -- | - | a == X(a) | -linear | -
| X u(a); X u = a; |
-- | - | post: u == a. Equivalent to: X u; u = a; | -linear | -
| (&a)->~X(); | -void | -- | dtor is applied to every element of a; all the memory is deallocated | -linear | -
| a.begin() | -iterator; const_iterator for constant a | -- | - | constant | -
| a.end() | -iterator; const_iterator for constant a | -- | - | constant | -
| a == b | -convertible to bool | -- | == is an equivalence relation. a.size()==b.size() && - equal(a.begin(),a.end(),b.begin()) | -linear | -
| a != b | -convertible to bool | -- | equivalent to !(a==b) | -linear | -
| a.swap(b) | -void | -- | swap(a,b) | -may or may not have constant complexity | -
| r = a | -X& | -- | r == a | -linear | -
| a.size() | -size_type | -a.end() - a.begin() | -- | may or may not have constant complexity | -
| a.max_size() | -size_type | -size() of the largest possible container | -- | may or may not have constant complexity | -
| a.empty() | -convertible to bool | -a.size() == 0 | -- | constant | -
| a < b | -convertible to bool | -lexographical_compare( a.begin, a.end(), b.begin(), b.end()) | -pre: < is defined for T and is a total ordering relation | -linear | -
| a > b | -convertible to bool | -b < a | -- | linear | -
| a <= b | -convertible to bool | -!(a > b) | -- | linear | -
| a >= b | -convertible to bool | -!(a < b) | -- | linear | -
-
| -If a container's iterator is bidirectional or random-access, then the -container also meets these requirements. -Deque, list, vector, map, multimap, set, and multiset are such containers. - | |||
|---|---|---|---|
| expression | -result type | -notes, pre-/post-conditions, assertions | -complexity | -
| X::reverse_iterator | -iterator type pointing to T | -reverse_iterator<iterator> | -compile time | -
| X::const_reverse_iterator | -iterator type pointing to const T | -reverse_iterator<const_iterator> | -compile time | -
| a.rbegin() | -reverse_iterator; const_reverse_iterator for constant a | -reverse_iterator(end()) | -constant | -
| a.rend() | -reverse_iterator; const_reverse_iterator for constant a | -reverse_iterator(begin()) | -constant | -
-
| -These are in addition to the requirements of containers. -Deque, list, and vector are such containers. - | ||
|---|---|---|
| expression | -result type | -notes, pre-/post-conditions, assertions | -
| X(n,t) X a(n,t) |
-- | constructs a sequence with n copies of t post: size() == n |
-
| X(i,j) X a(i,j) |
-- | constructs a sequence equal to the range [i,j) - post: size() == distance(i,j) |
-
| a.insert(p,t) | -iterator (points to the inserted copy of t) | -inserts a copy of t before p | -
| a.insert(p,n,t) | -void | -inserts n copies of t before p | -
| a.insert(p,i,j) | -void | -inserts copies of elements in [i,j) before p - pre: i, j are not iterators into a |
-
| a.erase(q) | -iterator (points to the element following q (prior to erasure)) | -erases the element pointed to by q | -
| a.erase(q1,q1) | -iterator (points to the element pointed to by q2 (prior to erasure)) | -erases the elements in the range [q1,q2) | -
| a.clear() | -void | -erase(begin(),end()) post: size() == 0 |
-
-
| -These operations are only included in containers when the operation can be -done in constant time. - | |||
|---|---|---|---|
| expression | -result type | -operational semantics | -container | -
| a.front() | -reference; const_reference for constant a | -*a.begin() | -vector, list, deque | -
| a.back() | -reference; const_reference for constant a | -*--a.end() | -vector, list, deque | -
| a.push_front(x) | -void | -a.insert(a.begin(),x) | -list, deque | -
| a.push_back(x) | -void | -a.insert(a.end(),x) | -vector, list, deque | -
| a.pop_front() | -void | -a.erase(a.begin()) | -list, deque | -
| a.pop_back() | -void | -a.erase(--a.end()) | -vector, list, deque | -
| a[n] | -reference; const_reference for constant a | -*(a.begin() + n) | -vector, deque | -
| a.at(n) | -reference; const_reference for constant a | -*(a.begin() + n) throws out_of_range if n>=a.size() |
-vector, deque | -
-
-These are in addition to the requirements of containers.
-Map, multimap, set, and multiset are such containers. An associative
-container supports unique keys (and is written as
-a_uniq instead of a) if it may contain at most
-one element for each key. Otherwise it supports equivalent keys
-(and is written a_eq). Examples of the former are set and map,
-examples of the latter are multiset and multimap.
- | |||
|---|---|---|---|
| expression | -result type | -notes, pre-/post-conditions, assertions | -complexity | -
| X::key_type | -Key | -Key is Assignable | -compile time | -
| X::key_compare | -Compare | -defaults to less<key_type> | -compile time | -
| X::value_compare | -a binary predicate type | -same as key_compare for set and multiset; an ordering relation on - pairs induced by the first component (Key) for map and multimap | -compile time | -
| X(c) X a(c) |
-- | constructs an empty container which uses c as a comparison object | -constant | -
| X() X a |
-- | constructs an empty container using Compare() as a comparison object | -constant | -
| X(i,j,c) X a(i,j,c) |
-- | constructs an empty container and inserts elements from the range [i,j) - into it; uses c as a comparison object | -NlogN in general where N is distance(i,j); linear if [i,j) is - sorted with value_comp() | -
| X(i,j) X a(i,j) |
-- | same as previous, but uses Compare() as a comparison object | -same as previous | -
| a.key_comp() | -X::key_compare | -returns the comparison object out of which a was constructed | -constant | -
| a.value_comp() | -X::value_compare | -returns an object constructed out of the comparison object | -constant | -
| a_uniq.insert(t) | -pair<iterator,bool> | -"Inserts t if and only if there is no element in the container with - key equivalent to the key of t. The bool component of the returned pair - is true -iff- the insertion took place, and the iterator component of - the pair points to the element with key equivalent to the key of - t." | -logarithmic | -
| a_eq.insert(t) | -iterator | -inserts t, returns the iterator pointing to the inserted element | -logarithmic | -
| a.insert(p,t) | -iterator | -possibly inserts t (depending on whether a_uniq or a_eq); returns iterator - pointing to the element with key equivalent to the key of t; iterator p - is a hint pointing to where the insert should start to search | -logarithmic in general, amortized constant if t is inserted right
- after p - [but see DR 233 and our - specific notes] |
-
| a.insert(i,j) | -void | -pre: i, j are not iterators into a. possibly inserts each element from - the range [i,j) (depending on whether a_uniq or a_eq) | -Nlog(size()+N) where N is distance(i,j) in general | -
| a.erase(k) | -size_type | -erases all elements with key equivalent to k; returns number of erased - elements | -log(size()) + count(k) | -
| a.erase(q) | -void | -erases the element pointed to by q | -amortized constant | -
| a.erase(q1,q2) | -void | -erases all the elements in the range [q1,q2) | -log(size()) + distance(q1,q2) | -
| a.clear() | -void | -erases everthing; post: size() == 0 | -linear | -
| a.find(k) | -iterator; const_iterator for constant a | -returns iterator pointing to element with key equivalent to k, or - a.end() if no such element found | -logarithmic | -
| a.count(k) | -size_type | -returns number of elements with key equivalent to k | -log(size()) + count(k) | -
| a.lower_bound(k) | -iterator; const_iterator for constant a | -returns iterator pointing to the first element with key not less than k | -logarithmic | -
| a.upper_bound(k) | -iterator; const_iterator for constant a | -returns iterator pointing to the first element with key greater than k | -logarithmic | -
| a.equal_range(k) | -pair<iterator,iterator>; - pair<const_iterator, const_iterator> for constant a | -equivalent to make_pair(a.lower_bound(k), a.upper_bound(k)) | -logarithmic | -
-See mainpage.html for copying conditions. -See the libstdc++-v3 homepage -for more information. -
- - - - -