1<?xml version="1.0"?> 2<concept name="RandomAccessIterator" category="Iterator"><!-- 3Based on concepts from the SGI Standard Template Library documentation: 4Copyright (c) 1996-1999 5Silicon Graphics Computer Systems, Inc. 6 7Copyright (c) 1994 8Hewlett-Packard Company 9--><!-- 10Copyright 2000-2001 University of Notre Dame du Lac. 11Copyright 2001-2002 Indiana University. 12Some concepts based on versions from the MTL draft manual and Boost Graph 13and Property Map documentation: 14Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 15--> 16 <param name="Iter" role="iterator-type"/> 17 18 <use-header name="iterator"/> 19 20 <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence> 21 22 <description> 23 <para>A random access iterator is an iterator that can read through 24 a sequence of values. It can move in either direction through the 25 sequence (by any amount in constant time), and can be either mutable 26 (data pointed to by it can be changed) or not mutable.</para> 27 28 <para>An iterator represents a position in a sequence. Therefore, 29 the iterator can point into the sequence (returning a value when 30 dereferenced and being incrementable), or be off-the-end (and not 31 dereferenceable or incrementable).</para> 32 </description> 33 34 <associated-type name="value_type"> 35 <get-member-type name="value_type"> 36 <apply-template name="std::iterator_traits"> 37 <type name="Iter"/> 38 </apply-template> 39 </get-member-type> 40 <description><simpara>The value type of the iterator</simpara></description> 41 </associated-type> 42 43 <refines const="no" concept="BidirectionalIterator"/> 44 <refines const="no" concept="LessThanComparable"/> 45 46 <notation variables="i j"> 47 <sample-value> 48 <type name="Iter"/> 49 </sample-value> 50 </notation> 51 52 <associated-type name="category"> 53 <get-member-type name="iterator_category"> 54 <apply-template name="std::iterator_traits"> 55 <type name="Iter"/> 56 </apply-template> 57 </get-member-type> 58 <description><simpara>The category of the iterator</simpara></description> 59 </associated-type> 60 61 <associated-type name="difference_type"> 62 <get-member-type name="difference_type"> 63 <apply-template name="std::iterator_traits"> 64 <type name="Iter"/> 65 </apply-template> 66 </get-member-type> 67 <description><simpara>The difference type of the iterator (measure of the number 68 of steps between two iterators)</simpara></description> 69 </associated-type> 70 71 <notation variables="x"> 72 <sample-value> 73 <type name="value_type"/> 74 </sample-value> 75 </notation> 76 77 <notation variables="n"> 78 <sample-value> 79 <type name="difference_type"/> 80 </sample-value> 81 </notation> 82 83 <notation variables="int_off"> 84 <sample-value> 85 <type name="int"/> 86 </sample-value> 87 </notation> 88 89 <valid-type-expression name="Category tag"> 90 <description/> 91 <type name="category"/> 92 <return-type> 93 <derived-from testable="yes"> 94 <type name="std::random_access_iterator_tag"/> 95 </derived-from> 96 </return-type> 97 </valid-type-expression> 98 99 <valid-expression name="Motion"> 100 <add-assign> 101 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 102 <sample-value><type name="difference_type"/></sample-value> 103 </add-assign> 104 <return-type> 105 <require-same-type testable="yes"> 106 <reference-to><type name="Iter"/></reference-to> 107 </require-same-type> 108 </return-type> 109 <semantics>Equivalent to applying <code>i++</code> <code>n</code> times 110 if <code>n</code> is positive, applying <code>i--</code> 111 <code>-n</code> times if <code>n</code> is negative, and to a null 112 operation if <code>n</code> is zero.</semantics> 113 </valid-expression> 114 115 <valid-expression name="Motion (with integer offset)"> 116 <add-assign> 117 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 118 <sample-value><type name="int"/></sample-value> 119 </add-assign> 120 <return-type> 121 <require-same-type testable="yes"> 122 <reference-to><type name="Iter"/></reference-to> 123 </require-same-type> 124 </return-type> 125 <semantics>Equivalent to applying <code>i++</code> <code>n</code> times 126 if <code>n</code> is positive, applying <code>i--</code> 127 <code>-n</code> times if <code>n</code> is negative, and to a null 128 operation if <code>n</code> is zero.</semantics> 129 </valid-expression> 130 131 <valid-expression name="Subtractive motion"> 132 <subtract-assign> 133 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 134 <sample-value><type name="difference_type"/></sample-value> 135 </subtract-assign> 136 <return-type> 137 <require-same-type testable="yes"> 138 <reference-to><type name="Iter"/></reference-to> 139 </require-same-type> 140 </return-type> 141 <semantics>Equivalent to <code>i+=(-n)</code></semantics> 142 </valid-expression> 143 144 <valid-expression name="Subtractive motion (with integer offset)"> 145 <subtract-assign> 146 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 147 <sample-value><type name="int"/></sample-value> 148 </subtract-assign> 149 <return-type> 150 <require-same-type testable="yes"> 151 <reference-to><type name="Iter"/></reference-to> 152 </require-same-type> 153 </return-type> 154 <semantics>Equivalent to <code>i+=(-n)</code></semantics> 155 </valid-expression> 156 157 <valid-expression name="Addition"> 158 <add> 159 <sample-value><type name="Iter"/></sample-value> 160 <sample-value><type name="difference_type"/></sample-value> 161 </add> 162 <return-type> 163 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 164 </return-type> 165 <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics> 166 </valid-expression> 167 168 <valid-expression name="Addition with integer"> 169 <add> 170 <sample-value><type name="Iter"/></sample-value> 171 <sample-value><type name="int"/></sample-value> 172 </add> 173 <return-type> 174 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 175 </return-type> 176 <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics> 177 </valid-expression> 178 179 <valid-expression name="Addition (count first)"> 180 <add> 181 <sample-value><type name="difference_type"/></sample-value> 182 <sample-value><type name="Iter"/></sample-value> 183 </add> 184 <return-type> 185 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 186 </return-type> 187 <semantics>Equivalent to <code>i + n</code></semantics> 188 </valid-expression> 189 190 <valid-expression name="Addition with integer (count first)"> 191 <add> 192 <sample-value><type name="int"/></sample-value> 193 <sample-value><type name="Iter"/></sample-value> 194 </add> 195 <return-type> 196 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 197 </return-type> 198 <semantics>Equivalent to <code>i + n</code></semantics> 199 </valid-expression> 200 201 <valid-expression name="Subtraction"> 202 <subtract> 203 <sample-value><type name="Iter"/></sample-value> 204 <sample-value><type name="difference_type"/></sample-value> 205 </subtract> 206 <return-type> 207 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 208 </return-type> 209 <semantics>Equivalent to <code>i + (-n)</code></semantics> 210 </valid-expression> 211 212 <valid-expression name="Subtraction with integer"> 213 <subtract> 214 <sample-value><type name="Iter"/></sample-value> 215 <sample-value><type name="int"/></sample-value> 216 </subtract> 217 <return-type> 218 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 219 </return-type> 220 <semantics>Equivalent to <code>i + (-n)</code></semantics> 221 </valid-expression> 222 223 <valid-expression name="Distance"> 224 <subtract> 225 <sample-value><type name="Iter"/></sample-value> 226 <sample-value><type name="Iter"/></sample-value> 227 </subtract> 228 <return-type> 229 <require-same-type testable="yes"><type name="difference_type"/></require-same-type> 230 </return-type> 231 <semantics>The number of times <code>i</code> must be incremented (or 232 decremented if the result is negative) to reach <code>j</code>. Not 233 defined if <code>j</code> is not reachable from 234 <code>i</code>.</semantics> 235 </valid-expression> 236 237 <valid-expression name="Element access"> 238 <subscript> 239 <sample-value><type name="Iter"/></sample-value> 240 <sample-value><type name="difference_type"/></sample-value> 241 </subscript> 242 <return-type> 243 <require-same-type testable="yes"> 244 <const-if-not-mutable> 245 <reference-to> 246 <type name="value_type"/> 247 </reference-to> 248 </const-if-not-mutable> 249 </require-same-type> 250 </return-type> 251 <semantics>Equivalent to <code>*(i + n)</code></semantics> 252 </valid-expression> 253 254 <valid-expression name="Element access with integer index"> 255 <subscript> 256 <sample-value><type name="Iter"/></sample-value> 257 <sample-value><type name="int"/></sample-value> 258 </subscript> 259 <return-type> 260 <require-same-type testable="yes"> 261 <const-if-not-mutable> 262 <reference-to> 263 <type name="value_type"/> 264 </reference-to> 265 </const-if-not-mutable> 266 </require-same-type> 267 </return-type> 268 <semantics>Equivalent to <code>*(i + n)</code></semantics> 269 </valid-expression> 270 271 <complexity> 272 All iterator operations must take amortized constant time. 273 </complexity> 274 275 <example-model> 276 <pointer-to> 277 <type name="T"/> 278 </pointer-to> 279 </example-model> 280 281 <example-model> 282 <get-member-type name="iterator"> 283 <apply-template name="std::vector"> 284 <type name="T"/> 285 </apply-template> 286 </get-member-type> 287 </example-model> 288 289 <example-model> 290 <get-member-type name="const_iterator"> 291 <apply-template name="std::vector"> 292 <type name="T"/> 293 </apply-template> 294 </get-member-type> 295 </example-model> 296 297 <example-model> 298 <get-member-type name="iterator"> 299 <apply-template name="std::deque"> 300 <type name="T"/> 301 </apply-template> 302 </get-member-type> 303 </example-model> 304 305 <example-model> 306 <get-member-type name="const_iterator"> 307 <apply-template name="std::deque"> 308 <type name="T"/> 309 </apply-template> 310 </get-member-type> 311 </example-model> 312 313</concept> 314