123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376 |
- [section:concepts Iterator Concepts]
- [section:access Access]
- [section:readable Readable Iterator Concept]
- A class or built-in type `X` models the *Readable Iterator* concept
- for value type `T` if, in addition to `X` being Assignable and
- Copy Constructible, the following expressions are valid and respect
- the stated semantics. `U` is the type of any specified member of
- type `T`.
- [table Readable Iterator Requirements (in addition to Assignable and Copy Constructible)
- [
- [Expression]
- [Return Type]
- [Note/Precondition]
- ]
- [
- [`iterator_traits<X>::value_type`]
- [`T`]
- [Any non-reference, non cv-qualified type]
- ]
- [
- [`*a`]
- [ Convertible to `T`]
- [pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.]
- ]
- [
- [`a->m`]
- [`U&`]
- [pre: `(*a).m` is well-defined. Equivalent to `(*a).m`.]
- ]
- ]
- [endsect]
- [section:writable Writable Iterator Concept]
- A class or built-in type `X` models the *Writable Iterator* concept
- if, in addition to `X` being Copy Constructible, the following
- expressions are valid and respect the stated semantics. Writable
- Iterators have an associated *set of value types*.
- [table Writable Iterator Requirements (in addition to Copy Constructible)
- [
- [Expression]
- [Return Type]
- [Precondition]
- ]
- [
- [`*a = o` ]
- []
- [pre: The type of `o` is in the set of value types of `X`]
- ]
- ]
- [endsect]
- [section:swappable Swappable Iterator Concept]
- A class or built-in type `X` models the *Swappable Iterator* concept
- if, in addition to `X` being Copy Constructible, the following
- expressions are valid and respect the stated semantics.
- [table Swappable Iterator Requirements (in addition to Copy Constructible)
- [
- [Expression]
- [Return Type]
- [Postcondition]
- ]
- [
- [`iter_swap(a, b)`]
- [`void`]
- [the pointed to values are exchanged]
- ]
- ]
- [blurb *Note:* An iterator that is a model of the *Readable* and *Writable Iterator* concepts
- is also a model of *Swappable Iterator*. *--end note*]
- [endsect]
- [section:lvalue Lvalue Iterator Concept]
- The *Lvalue Iterator* concept adds the requirement that the return
- type of `operator*` type be a reference to the value type of the
- iterator.
- [table Lvalue Iterator Requirements
- [
- [Expression]
- [Return Type]
- [Note/Assertion]
- ]
- [
- [`*a` ]
- [`T&` ]
- [
- `T` is *cv* `iterator_traits<X>::value_type` where *cv* is an optional cv-qualification.
- pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.
- ]
- ]
- ]
- [endsect]
- [endsect]
- [section:traversal Traversal]
- [section:incrementable Incrementable Iterator Concept]
- A class or built-in type `X` models the *Incrementable Iterator*
- concept if, in addition to `X` being Assignable and Copy
- Constructible, the following expressions are valid and respect the
- stated semantics.
- [table Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)
- [
- [Expression ]
- [Return Type]
- [Assertion/Semantics ]
- ]
- [
- [`++r` ]
- [`X&` ]
- [`&r == &++r`]
- ]
- [
- [`r++` ]
- [`X` ]
- [``
- {
- X tmp = r;
- ++r;
- return tmp;
- }
- ``]
- ]
- [
- [`iterator_traversal<X>::type`]
- [Convertible to `incrementable_traversal_tag`]
- []
- ]
- ]
- [endsect]
- [section:single_pass Single Pass Iterator Concept]
- A class or built-in type `X` models the *Single Pass Iterator*
- concept if the following expressions are valid and respect the stated
- semantics.
- [table Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable)
- [
- [Expression]
- [Return Type]
- [Assertion/Semantics / Pre-/Post-condition]
- ]
- [
- [`++r`]
- [`X&`]
- [pre:[br]`r` is dereferenceable;[br]post:[br]`r` is dereferenceable or[br]`r` is past-the-end]
- ]
- [
- [`a == b`]
- [convertible to `bool`]
- [`==` is an equivalence relation over its domain]
- ]
- [
- [`a != b`]
- [convertible to `bool`]
- [`!(a == b)`]
- ]
- [
- [`iterator_traits<X>::difference_type`]
- [A signed integral type representing the distance between iterators]
- []
- ]
- [
- [`iterator_traversal<X>::type`]
- [Convertible to`single_pass_traversal_tag`]
- []
- ]
- ]
- [endsect]
- [section:forward Forward Traversal Concept]
- A class or built-in type `X` models the *Forward Traversal*
- concept if, in addition to `X` meeting the requirements of Default
- Constructible and Single Pass Iterator, the following expressions are
- valid and respect the stated semantics.
- [table Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)
- [
- [Expression]
- [Return Type]
- [Assertion/Note]
- ]
- [
- [`X u;`]
- [`X&`]
- [note: `u` may have a singular value.]
- ]
- [
- [`++r`]
- [`X&`]
- [`r == s` and `r` is dereferenceable implies `++r == ++s.`]
- ]
- [
- [`iterator_traversal<X>::type`]
- [Convertible to `forward_traversal_tag`]
- []
- ]
- ]
- [endsect]
- [section:bidirectional Bidirectional Traversal Concept]
- A class or built-in type `X` models the *Bidirectional Traversal*
- concept if, in addition to `X` meeting the requirements of Forward
- Traversal Iterator, the following expressions are valid and respect
- the stated semantics.
- [table Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal Iterator)
- [
- [Expression]
- [Return Type]
- [Assertion/Semantics/Pre-/Post-condition]
- ]
- [
- [`--r`]
- [`X&`]
- [pre: there exists `s` such that `r == ++s`.[br] post: `s` is dereferenceable. `--(++r) == r`. `--r == --s` implies `r == s`. `&r == &--r`.]
- ]
- [
- [`r--`]
- [convertible to `const X&`]
- [``
- {
- X tmp = r;
- --r;
- return tmp;
- }
- ``]
- ]
- [
- [`iterator_traversal<X>::type`]
- [Convertible to `bidirectional_traversal_tag`]
- []
- ]
- ]
- [endsect]
- [section:random_access Random Access Traversal Concept]
- A class or built-in type `X` models the *Random Access Traversal*
- concept if the following expressions are valid and respect the stated
- semantics. In the table below, `Distance` is
- `iterator_traits<X>::difference_type` and `n` represents a
- constant object of type `Distance`.
- [table Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal)
- [
- [Expression]
- [Return Type]
- [Operational Semantics]
- [Assertion/Precondition]
- ]
- [
- [`r += n`]
- [ `X&`]
- [``
- {
- Distance m = n;
- if (m >= 0)
- while (m--)
- ++r;
- else
- while (m++)
- --r;
- return r;
- }
- ``]
- [ ]
- ]
- [
- [`a + n`, `n + a`]
- [`X`]
- [``
- {
- X tmp = a;
- return tmp+= n;
- }
- ``]
- []
- ]
- [
- [`r -= n`]
- [`X&`]
- [`return r += -n`]
- []
- ]
- [
- [`a - n`]
- [`X`]
- [``
- {
- X tmp = a;
- return tmp-= n;
- }
- ``]
- []
- ]
- [
- [`b - a`]
- [`Distance`]
- [`a < b ? distance(a,b) : -distance(b,a)`]
- [pre: there exists a value `n` of `Distance` such that `a + n == b`. `b == a + (b - a)`.]
- ]
- [
- [`a\[n\]`]
- [convertible to T]
- [`*(a + n)`]
- [pre: a is a *Readable Iterator*]
- ]
- [
- [`a\[n\] = v`]
- [convertible to T]
- [`*(a + n) = v`]
- [pre: a is a *Writable iterator*]
- ]
- [
- [`a < b`]
- [convertible to `bool`]
- [`b - a > 0`]
- [`<` is a total ordering relation]
- ]
- [
- [`a > b`]
- [convertible to `bool`]
- [`b < a`]
- [`>` is a total ordering relation]
- ]
- [
- [`a >= b`]
- [convertible to `bool`]
- [`!(a < b)`]
- []
- ]
- [
- [`a <= b`]
- [convertible to `bool`]
- [`!(a > b)`]
- []
- ]
- [
- [`iterator_traversal<X>::type`]
- [convertible to `random_access_traversal_tag`]
- []
- []
- ]
- ]
- [endsect]
- [endsect]
- [endsect]
|