1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Random Access Sequence</title> 5<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Chapter 1. Fusion 2.2"> 8<link rel="up" href="../concepts.html" title="Concepts"> 9<link rel="prev" href="bidirectional_sequence.html" title="Bidirectional Sequence"> 10<link rel="next" href="associative_sequence.html" title="Associative Sequence"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="bidirectional_sequence.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../concepts.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="associative_sequence.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="fusion.sequence.concepts.random_access_sequence"></a><a class="link" href="random_access_sequence.html" title="Random Access Sequence">Random 28 Access Sequence</a> 29</h4></div></div></div> 30<h6> 31<a name="fusion.sequence.concepts.random_access_sequence.h0"></a> 32 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.description"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.description">Description</a> 33 </h6> 34<p> 35 A Random Access Sequence is a <a class="link" href="bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 36 Sequence</a> whose iterators model <a class="link" href="../../iterator/concepts/random_access_iterator.html" title="Random Access Iterator">Random 37 Access Iterator</a>. It guarantees constant time access to arbitrary 38 sequence elements. 39 </p> 40<h6> 41<a name="fusion.sequence.concepts.random_access_sequence.h1"></a> 42 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.refinement_of"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.refinement_of">Refinement 43 of</a> 44 </h6> 45<p> 46 <a class="link" href="bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 47 Sequence</a> 48 </p> 49<div class="variablelist"> 50<p class="title"><b>Notation</b></p> 51<dl class="variablelist"> 52<dt><span class="term"><code class="computeroutput"><span class="identifier">s</span></code></span></dt> 53<dd><p> 54 A Random Access Sequence 55 </p></dd> 56<dt><span class="term"><code class="computeroutput"><span class="identifier">S</span></code></span></dt> 57<dd><p> 58 A Random Access Sequence type 59 </p></dd> 60<dt><span class="term"><code class="computeroutput"><span class="identifier">M</span></code></span></dt> 61<dd><p> 62 An <a href="http://www.boost.org/libs/mpl" target="_top">MPL</a> integral 63 constant 64 </p></dd> 65<dt><span class="term"><code class="computeroutput"><span class="identifier">N</span></code></span></dt> 66<dd><p> 67 An integral constant 68 </p></dd> 69<dt><span class="term"><code class="computeroutput"><span class="identifier">o</span></code></span></dt> 70<dd><p> 71 An arbitrary object 72 </p></dd> 73<dt><span class="term"><code class="computeroutput"><span class="identifier">e</span></code></span></dt> 74<dd><p> 75 A Sequence element 76 </p></dd> 77</dl> 78</div> 79<h6> 80<a name="fusion.sequence.concepts.random_access_sequence.h2"></a> 81 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.valid_expressions"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.valid_expressions">Valid 82 Expressions</a> 83 </h6> 84<p> 85 In addition to the requirements defined in <a class="link" href="bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 86 Sequence</a>, for any Random Access Sequence the following must be met: 87 </p> 88<div class="informaltable"><table class="table"> 89<colgroup> 90<col> 91<col> 92<col> 93<col> 94</colgroup> 95<thead><tr> 96<th> 97 <p> 98 Expression 99 </p> 100 </th> 101<th> 102 <p> 103 Return type 104 </p> 105 </th> 106<th> 107 <p> 108 Type Requirements 109 </p> 110 </th> 111<th> 112 <p> 113 Runtime Complexity 114 </p> 115 </th> 116</tr></thead> 117<tbody> 118<tr> 119<td> 120 <p> 121 <code class="computeroutput"><a class="link" href="../intrinsic/functions/begin.html" title="begin"><code class="computeroutput"><span class="identifier">begin</span></code></a><span class="special">(</span><span class="identifier">s</span><span class="special">)</span></code> 122 </p> 123 </td> 124<td> 125 <p> 126 <a class="link" href="../../iterator/concepts/random_access_iterator.html" title="Random Access Iterator">Random 127 Access Iterator</a> 128 </p> 129 </td> 130<td> 131 </td> 132<td> 133 <p> 134 Constant 135 </p> 136 </td> 137</tr> 138<tr> 139<td> 140 <p> 141 <code class="computeroutput"><a class="link" href="../intrinsic/functions/end.html" title="end"><code class="computeroutput"><span class="identifier">end</span></code></a><span class="special">(</span><span class="identifier">s</span><span class="special">)</span></code> 142 </p> 143 </td> 144<td> 145 <p> 146 <a class="link" href="../../iterator/concepts/random_access_iterator.html" title="Random Access Iterator">Random 147 Access Iterator</a> 148 </p> 149 </td> 150<td> 151 </td> 152<td> 153 <p> 154 Constant 155 </p> 156 </td> 157</tr> 158<tr> 159<td> 160 <p> 161 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">at_c</span></code></a><span class="special"><</span><span class="identifier">N</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span></code> 162 </p> 163 </td> 164<td> 165 <p> 166 Any type 167 </p> 168 </td> 169<td> 170 </td> 171<td> 172 <p> 173 Constant 174 </p> 175 </td> 176</tr> 177<tr> 178<td> 179 <p> 180 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">at_c</span></code></a><span class="special"><</span><span class="identifier">N</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span> 181 <span class="special">=</span> <span class="identifier">o</span></code> 182 </p> 183 </td> 184<td> 185 <p> 186 Any type 187 </p> 188 </td> 189<td> 190 <p> 191 <code class="computeroutput"><span class="identifier">s</span></code> is mutable 192 and <code class="computeroutput"><span class="identifier">e</span> <span class="special">=</span> 193 <span class="identifier">o</span></code>, where <code class="computeroutput"><span class="identifier">e</span></code> is the first element in the 194 sequence, is a valid expression. 195 </p> 196 </td> 197<td> 198 <p> 199 Constant 200 </p> 201 </td> 202</tr> 203<tr> 204<td> 205 <p> 206 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">M</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span></code> 207 </p> 208 </td> 209<td> 210 <p> 211 Any type 212 </p> 213 </td> 214<td> 215 </td> 216<td> 217 <p> 218 Constant 219 </p> 220 </td> 221</tr> 222<tr> 223<td> 224 <p> 225 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">M</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span> 226 <span class="special">=</span> <span class="identifier">o</span></code> 227 </p> 228 </td> 229<td> 230 <p> 231 Any type 232 </p> 233 </td> 234<td> 235 <p> 236 <code class="computeroutput"><span class="identifier">s</span></code> is mutable 237 and <code class="computeroutput"><span class="identifier">e</span> <span class="special">=</span> 238 <span class="identifier">o</span></code>, where <code class="computeroutput"><span class="identifier">e</span></code> is the first element in the 239 sequence, is a valid expression. 240 </p> 241 </td> 242<td> 243 <p> 244 Constant 245 </p> 246 </td> 247</tr> 248</tbody> 249</table></div> 250<h6> 251<a name="fusion.sequence.concepts.random_access_sequence.h3"></a> 252 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.result_type_expressions"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.result_type_expressions">Result 253 Type Expressions</a> 254 </h6> 255<div class="informaltable"><table class="table"> 256<colgroup> 257<col> 258<col> 259</colgroup> 260<thead><tr> 261<th> 262 <p> 263 Expression 264 </p> 265 </th> 266<th> 267 <p> 268 Compile Time Complexity 269 </p> 270 </th> 271</tr></thead> 272<tbody> 273<tr> 274<td> 275 <p> 276 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/begin.html" title="begin"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">begin</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">>::</span><span class="identifier">type</span></code> 277 </p> 278 </td> 279<td> 280 <p> 281 Amortized constant time 282 </p> 283 </td> 284</tr> 285<tr> 286<td> 287 <p> 288 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/end.html" title="end"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">end</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">>::</span><span class="identifier">type</span></code> 289 </p> 290 </td> 291<td> 292 <p> 293 Amortized constant time 294 </p> 295 </td> 296</tr> 297<tr> 298<td> 299 <p> 300 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/at.html" title="at"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> 301 <span class="identifier">M</span><span class="special">>::</span><span class="identifier">type</span></code> 302 </p> 303 </td> 304<td> 305 <p> 306 Amortized constant time 307 </p> 308 </td> 309</tr> 310<tr> 311<td> 312 <p> 313 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">at_c</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> 314 <span class="identifier">N</span><span class="special">>::</span><span class="identifier">type</span></code> 315 </p> 316 </td> 317<td> 318 <p> 319 Amortized constant time 320 </p> 321 </td> 322</tr> 323<tr> 324<td> 325 <p> 326 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/value_at.html" title="value_at"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">value_at</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> 327 <span class="identifier">M</span><span class="special">>::</span><span class="identifier">type</span></code> 328 </p> 329 </td> 330<td> 331 <p> 332 Amortized constant time 333 </p> 334 </td> 335</tr> 336<tr> 337<td> 338 <p> 339 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/value_at_c.html" title="value_at_c"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">value_at_c</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> 340 <span class="identifier">N</span><span class="special">>::</span><span class="identifier">type</span></code> 341 </p> 342 </td> 343<td> 344 <p> 345 Amortized constant time 346 </p> 347 </td> 348</tr> 349</tbody> 350</table></div> 351<div class="note"><table border="0" summary="Note"> 352<tr> 353<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../../doc/src/images/note.png"></td> 354<th align="left">Note</th> 355</tr> 356<tr><td align="left" valign="top"><p> 357 <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/at.html" title="at"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> <span class="identifier">M</span><span class="special">></span></code> 358 returns the actual type returned by <code class="computeroutput"><a class="link" href="../intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">M</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span></code>. 359 In most cases, this is a reference. Hence, there is no way to know the 360 exact element type using <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/at.html" title="at"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> <span class="identifier">M</span><span class="special">></span></code>.The 361 element at <code class="computeroutput"><span class="identifier">M</span></code> may actually 362 be a reference to begin with. For this purpose, you can use <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/value_at.html" title="value_at"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">value_at</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> <span class="identifier">M</span><span class="special">></span></code> 363 (Note that, <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/value_at_c.html" title="value_at_c"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">value_at_c</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> <span class="identifier">N</span><span class="special">></span></code> 364 is a counterpart of <code class="computeroutput"><a class="link" href="../intrinsic/metafunctions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">at_c</span></code></a><span class="special"><</span><span class="identifier">S</span><span class="special">,</span> <span class="identifier">N</span><span class="special">></span></code> 365 as well). 366 </p></td></tr> 367</table></div> 368<h6> 369<a name="fusion.sequence.concepts.random_access_sequence.h4"></a> 370 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.expression_semantics"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.expression_semantics">Expression 371 Semantics</a> 372 </h6> 373<p> 374 The semantics of an expression are defined only where they differ from, 375 or are not defined in <a class="link" href="bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 376 Sequence</a>. 377 </p> 378<div class="informaltable"><table class="table"> 379<colgroup> 380<col> 381<col> 382</colgroup> 383<thead><tr> 384<th> 385 <p> 386 Expression 387 </p> 388 </th> 389<th> 390 <p> 391 Semantics 392 </p> 393 </th> 394</tr></thead> 395<tbody> 396<tr> 397<td> 398 <p> 399 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a><span class="special"><</span><span class="identifier">M</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span></code> 400 </p> 401 </td> 402<td> 403 <p> 404 The Mth element from the beginning of the sequence; see <a class="link" href="../intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a>. 405 </p> 406 </td> 407</tr> 408<tr> 409<td> 410 <p> 411 <code class="computeroutput"><a class="link" href="../intrinsic/functions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">at_c</span></code></a><span class="special"><</span><span class="identifier">N</span><span class="special">>(</span><span class="identifier">s</span><span class="special">)</span></code> 412 </p> 413 </td> 414<td> 415 <p> 416 The Nth element from the beginning of the sequence; see <a class="link" href="../intrinsic/functions/at_c.html" title="at_c"><code class="computeroutput"><span class="identifier">at_c</span></code></a>. 417 </p> 418 </td> 419</tr> 420</tbody> 421</table></div> 422<h6> 423<a name="fusion.sequence.concepts.random_access_sequence.h5"></a> 424 <span class="phrase"><a name="fusion.sequence.concepts.random_access_sequence.models"></a></span><a class="link" href="random_access_sequence.html#fusion.sequence.concepts.random_access_sequence.models">Models</a> 425 </h6> 426<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 427<li class="listitem"> 428 <a class="link" href="../../adapted/std__pair.html" title="std::pair"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code></a> 429 </li> 430<li class="listitem"> 431 <a class="link" href="../../adapted/boost__array.html" title="boost::array"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">array</span></code></a> 432 </li> 433<li class="listitem"> 434 <a class="link" href="../../container/vector.html" title="vector"><code class="computeroutput"><span class="identifier">vector</span></code></a> 435 </li> 436<li class="listitem"> 437 <a class="link" href="../../container/map.html" title="map"><code class="computeroutput"><span class="identifier">map</span></code></a> 438 </li> 439<li class="listitem"> 440 <a class="link" href="../../view/reverse_view.html" title="reverse_view"><code class="computeroutput"><span class="identifier">reverse_view</span></code></a> 441 </li> 442<li class="listitem"> 443 <a class="link" href="../../view/single_view.html" title="single_view"><code class="computeroutput"><span class="identifier">single_view</span></code></a> 444 </li> 445<li class="listitem"> 446 <a class="link" href="../../view/iterator_range.html" title="iterator_range"><code class="computeroutput"><span class="identifier">iterator_range</span></code></a> 447 (where adapted sequence is a Random Access Sequence) 448 </li> 449<li class="listitem"> 450 <a class="link" href="../../view/transform_view.html" title="transform_view"><code class="computeroutput"><span class="identifier">transform_view</span></code></a> 451 (where adapted sequence is a Random Access Sequence) 452 </li> 453<li class="listitem"> 454 <a class="link" href="../../view/zip_view.html" title="zip_view"><code class="computeroutput"><span class="identifier">zip_view</span></code></a> 455 (where adapted sequences are models of Random Access Sequence) 456 </li> 457</ul></div> 458</div> 459<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 460<td align="left"></td> 461<td align="right"><div class="copyright-footer">Copyright © 2001-2006, 2011, 2012 Joel de Guzman, 462 Dan Marsden, Tobias Schwinger<p> 463 Distributed under the Boost Software License, Version 1.0. (See accompanying 464 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 465 </p> 466</div></td> 467</tr></table> 468<hr> 469<div class="spirit-nav"> 470<a accesskey="p" href="bidirectional_sequence.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../concepts.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="associative_sequence.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 471</div> 472</body> 473</html> 474
