ceph/src/boost/libs/iterator/doc/quickbook/concepts.qbk

   1
   2 [section:concepts Iterator Concepts]
   3
   4 [section:concepts_access Access]
   5
   6 [h2 Readable Iterator Concept]
   7
   8 A class or built-in type `X` models the *Readable Iterator* concept
   9 for value type `T` if, in addition to `X` being Assignable and
  10 Copy Constructible, the following expressions are valid and respect
  11 the stated semantics. `U` is the type of any specified member of
  12 type `T`.
  13
  14 [table Readable Iterator Requirements (in addition to Assignable and Copy Constructible)
  15   [
  16     [Expression]
  17     [Return Type]
  18     [Note/Precondition]
  19   ]
  20   [
  21     [`iterator_traits<X>::value_type`]
  22     [`T`]
  23     [Any non-reference, non cv-qualified type]
  24   ]
  25   [
  26     [`*a`]
  27     [ Convertible to `T`]
  28     [pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.]
  29   ]
  30   [
  31     [`a->m`]
  32     [`U&`]
  33     [pre: `(*a).m` is well-defined. Equivalent to `(*a).m`.]
  34   ]
  35 ]
  36
  37 [h2 Writable Iterator Concept  ]
  38
  39
  40 A class or built-in type `X`   models the *Writable Iterator* concept
  41 if, in addition to `X` being   Copy Constructible, the following
  42 expressions are valid and respect the stated semantics.  Writable
  43 Iterators have an associated *set of value types*.
  44
  45 [table Writable Iterator Requirements (in addition to Copy Constructible)
  46   [
  47     [Expression]
  48     [Return Type]
  49     [Precondition]
  50   ]
  51   [
  52     [`*a = o`  ]
  53     []
  54     [pre: The type of `o` is in the set of value types of `X`]
  55   ]
  56 ]
  57
  58 [h2 Swappable Iterator Concept]
  59
  60 A class or built-in type `X` models the *Swappable Iterator* concept
  61 if, in addition to `X` being Copy Constructible, the following
  62 expressions are valid and respect the stated semantics.
  63
  64 [table Swappable Iterator Requirements (in addition to Copy Constructible)
  65   [
  66     [Expression]
  67     [Return Type]
  68     [Postcondition]
  69   ]
  70   [
  71     [`iter_swap(a, b)`]
  72     [`void`]
  73     [the pointed to values are exchanged]
  74   ]
  75 ]
  76
  77 [blurb *Note:* An iterator that is a model of the *Readable* and *Writable Iterator* concepts
  78   is also a model of *Swappable Iterator*.  *--end note*]
  79
  80 [h2 Lvalue Iterator Concept]
  81
  82 The *Lvalue Iterator* concept adds the requirement that the return
  83 type of `operator*` type be a reference to the value type of the
  84 iterator.
  85
  86 [table Lvalue Iterator Requirements
  87   [
  88     [Expression]
  89     [Return Type]
  90     [Note/Assertion]
  91   ]
  92   [
  93     [`*a`      ]
  94     [`T&`       ]
  95     [
  96       `T` is *cv* `iterator_traits<X>::value_type` where *cv* is an optional cv-qualification.
  97       pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.
  98     ]
  99   ]
 100 ]
 101
 102 [endsect]
 103
 104 [section:concepts_traversal Traversal]
 105
 106 [h2 Incrementable Iterator Concept]
 107
 108
 109 A class or built-in type `X` models the *Incrementable Iterator*
 110 concept if, in addition to `X` being Assignable and Copy
 111 Constructible, the following expressions are valid and respect the
 112 stated semantics.
 113
 114
 115 [table Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)
 116   [
 117     [Expression ]
 118     [Return Type]
 119     [Assertion/Semantics ]
 120   ]
 121   [
 122     [`++r`      ]
 123     [`X&`       ]
 124     [`&r == &++r`]
 125   ]
 126   [
 127     [`r++`      ]
 128     [`X`        ]
 129     [``
 130        {
 131          X tmp = r;
 132          ++r;
 133          return tmp;
 134        }
 135     ``]
 136   ]
 137   [
 138     [`iterator_traversal<X>::type`]
 139     [Convertible to `incrementable_traversal_tag`]
 140     []
 141   ]
 142 ]
 143
 144 [h2 Single Pass Iterator Concept]
 145
 146 A class or built-in type `X` models the *Single Pass Iterator*
 147 concept if the following expressions are valid and respect the stated
 148 semantics.
 149
 150 [table Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable)
 151   [
 152     [Expression]
 153     [Return Type]
 154     [Assertion/Semantics / Pre-/Post-condition]
 155   ]
 156   [
 157     [`++r`]
 158     [`X&`]
 159     [pre:[br]`r` is dereferenceable;[br]post:[br]`r` is dereferenceable or[br]`r` is past-the-end]
 160   ]
 161   [
 162     [`a == b`]
 163     [convertible to `bool`]
 164     [`==` is an equivalence relation over its domain]
 165   ]
 166   [
 167     [`a != b`]
 168     [convertible to `bool`]
 169     [`!(a == b)`]
 170   ]
 171   [
 172     [`iterator_traversal<X>::type`]
 173     [Convertible to`single_pass_traversal_tag`]
 174     []
 175   ]
 176 ]
 177
 178
 179 [h2 Forward Traversal Concept]
 180
 181 A class or built-in type `X` models the *Forward Traversal*
 182 concept if, in addition to `X` meeting the requirements of Default
 183 Constructible and Single Pass Iterator, the following expressions are
 184 valid and respect the stated semantics.
 185
 186 [table Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)
 187   [
 188     [Expression]
 189     [Return Type]
 190     [Assertion/Note]
 191   ]
 192   [
 193     [`X u;`]
 194     [`X&`]
 195     [note: `u` may have a singular value.]
 196   ]
 197   [
 198     [`++r`]
 199     [`X&`]
 200     [`r == s` and `r` is dereferenceable implies `++r == ++s.`]
 201   ]
 202   [
 203     [`iterator_traits<X>::difference_type`]
 204     [A signed integral type representing the distance between iterators]
 205     []
 206   ]
 207   [
 208     [`iterator_traversal<X>::type`]
 209     [Convertible to `forward_traversal_tag`]
 210     []
 211   ]
 212 ]
 213
 214 [h2 Bidirectional Traversal Concept]
 215
 216 A class or built-in type `X` models the *Bidirectional Traversal*
 217 concept if, in addition to `X` meeting the requirements of Forward
 218 Traversal Iterator, the following expressions are valid and respect
 219 the stated semantics.
 220
 221 [table Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal Iterator)
 222   [
 223     [Expression]
 224     [Return Type]
 225     [Assertion/Semantics/Pre-/Post-condition]
 226   ]
 227   [
 228     [`--r`]
 229     [`X&`]
 230     [pre: there exists `s` such that `r == ++s`.[br] post: `s` is dereferenceable. `--(++r) == r`. `--r == --s` implies `r == s`. `&r == &--r`.]
 231   ]
 232   [
 233     [`r--`]
 234     [convertible to `const X&`]
 235     [``
 236         {
 237           X tmp = r;
 238           --r;
 239           return tmp;
 240         }
 241     ``]
 242   ]
 243   [
 244     [`iterator_traversal<X>::type`]
 245     [Convertible to `bidirectional_traversal_tag`]
 246     []
 247   ]
 248 ]
 249
 250 [h2 Random Access Traversal Concept]
 251
 252 A class or built-in type `X` models the *Random Access Traversal*
 253 concept if the following expressions are valid and respect the stated
 254 semantics.  In the table below, `Distance` is
 255 `iterator_traits<X>::difference_type` and `n` represents a
 256 constant object of type `Distance`.
 257
 258 [table Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal)
 259   [
 260     [Expression]
 261     [Return Type]
 262     [Operational Semantics]
 263     [Assertion/Precondition]
 264   ]
 265   [
 266     [`r += n`]
 267     [ `X&`]
 268     [``
 269         {
 270           Distance m = n;
 271           if (m >= 0)
 272             while (m--)
 273               ++r;
 274           else
 275             while (m++)
 276               --r;
 277           return r;
 278         }
 279     ``]
 280     [ ]
 281   ]
 282   [
 283     [`a + n`, `n + a`]
 284     [`X`]
 285     [``
 286         {
 287           X tmp = a;
 288           return tmp+= n;
 289         }
 290     ``]
 291     []
 292   ]
 293   [
 294     [`r -= n`]
 295     [`X&`]
 296     [`return r += -n`]
 297     []
 298   ]
 299   [
 300     [`a - n`]
 301     [`X`]
 302     [``
 303         {
 304           X tmp = a;
 305           return tmp-= n;
 306         }
 307     ``]
 308     []
 309   ]
 310   [
 311     [`b - a`]
 312     [`Distance`]
 313     [`a < b ?  distance(a,b) : -distance(b,a)`]
 314     [pre: there exists a value `n` of `Distance` such that `a + n == b`. `b == a + (b - a)`.]
 315   ]
 316   [
 317     [`a\[n\]`]
 318     [convertible to T]
 319     [`*(a + n)`]
 320     [pre: a is a *Readable Iterator*]
 321   ]
 322   [
 323     [`a\[n\] = v`]
 324     [convertible to T]
 325     [`*(a + n) = v`]
 326     [pre: a is a *Writable iterator*]
 327   ]
 328   [
 329     [`a < b`]
 330     [convertible to `bool`]
 331     [`b - a > 0`]
 332     [`<` is a total ordering relation]
 333   ]
 334   [
 335     [`a > b`]
 336     [convertible to `bool`]
 337     [`b < a`]
 338     [`>` is a total ordering relation]
 339   ]
 340   [
 341     [`a >= b`]
 342     [convertible to `bool`]
 343     [`!(a < b)`]
 344     []
 345   ]
 346   [
 347     [`a <= b`]
 348     [convertible to `bool`]
 349     [`!(a > b)`]
 350     []
 351   ]
 352   [
 353     [`iterator_traversal<X>::type`]
 354     [convertible to `random_access_traversal_tag`]
 355     []
 356     []
 357   ]
 358 ]
 359
 360 [endsect]
 361
 362 [endsect]