1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" /> 7<title>Random Access Traversal Concept</title> 8<link rel="stylesheet" href="../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="random-access-traversal-concept"> 12<h1 class="title">Random Access Traversal Concept</h1> 13 14<!-- Copyright David Abrahams 2006. Distributed under the Boost --> 15<!-- Software License, Version 1.0. (See accompanying --> 16<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 17<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Random Access Traversal</em> 18concept if the following expressions are valid and respect the stated 19semantics. In the table below, <tt class="docutils literal"><span class="pre">Distance</span></tt> is 20<tt class="docutils literal"><span class="pre">iterator_traits<X>::difference_type</span></tt> and <tt class="docutils literal"><span class="pre">n</span></tt> represents a 21constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p> 22<table border="1" class="docutils"> 23<colgroup> 24<col width="28%" /> 25<col width="30%" /> 26<col width="23%" /> 27<col width="20%" /> 28</colgroup> 29<thead valign="bottom"> 30<tr><th class="head" colspan="4">Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal)</th> 31</tr> 32<tr><th class="head">Expression</th> 33<th class="head">Return Type</th> 34<th class="head">Operational Semantics</th> 35<th class="head">Assertion/ 36Precondition</th> 37</tr> 38</thead> 39<tbody valign="top"> 40<tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">+=</span> <span class="pre">n</span></tt></td> 41<td><tt class="docutils literal"><span class="pre">X&</span></tt></td> 42<td><pre class="first last literal-block"> 43{ 44 Distance m = n; 45 if (m >= 0) 46 while (m--) 47 ++r; 48 else 49 while (m++) 50 --r; 51 return r; 52} 53</pre> 54</td> 55<td> </td> 56</tr> 57<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span></tt>, <tt class="docutils literal"><span class="pre">n</span> <span class="pre">+</span> <span class="pre">a</span></tt></td> 58<td><tt class="docutils literal"><span class="pre">X</span></tt></td> 59<td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span> 60<span class="pre">+=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td> 61<td> </td> 62</tr> 63<tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">-=</span> <span class="pre">n</span></tt></td> 64<td><tt class="docutils literal"><span class="pre">X&</span></tt></td> 65<td><tt class="docutils literal"><span class="pre">return</span> <span class="pre">r</span> <span class="pre">+=</span> <span class="pre">-n</span></tt></td> 66<td> </td> 67</tr> 68<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">-</span> <span class="pre">n</span></tt></td> 69<td><tt class="docutils literal"><span class="pre">X</span></tt></td> 70<td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span> 71<span class="pre">-=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td> 72<td> </td> 73</tr> 74<tr><td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span></tt></td> 75<td><tt class="docutils literal"><span class="pre">Distance</span></tt></td> 76<td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span> <span class="pre">?</span> <span class="pre">distance(a,b)</span> 77<span class="pre">:</span> <span class="pre">-distance(b,a)</span></tt></td> 78<td>pre: there exists a 79value <tt class="docutils literal"><span class="pre">n</span></tt> of 80<tt class="docutils literal"><span class="pre">Distance</span></tt> such that 81<tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">b</span></tt>. <tt class="docutils literal"><span class="pre">b</span> 82<span class="pre">==</span> <span class="pre">a</span> <span class="pre">+</span> <span class="pre">(b</span> <span class="pre">-</span> <span class="pre">a)</span></tt>.</td> 83</tr> 84<tr><td><tt class="docutils literal"><span class="pre">a[n]</span></tt></td> 85<td>convertible to T</td> 86<td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span></tt></td> 87<td>pre: a is a <em>Readable 88Iterator</em></td> 89</tr> 90<tr><td><tt class="docutils literal"><span class="pre">a[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt></td> 91<td>convertible to T</td> 92<td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">v</span></tt></td> 93<td>pre: a is a <em>Writable 94iterator</em></td> 95</tr> 96<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span></tt></td> 97<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> 98<td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span> <span class="pre">></span> <span class="pre">0</span></tt></td> 99<td><tt class="docutils literal"><span class="pre"><</span></tt> is a total 100ordering relation</td> 101</tr> 102<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">></span> <span class="pre">b</span></tt></td> 103<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> 104<td><tt class="docutils literal"><span class="pre">b</span> <span class="pre"><</span> <span class="pre">a</span></tt></td> 105<td><tt class="docutils literal"><span class="pre">></span></tt> is a total 106ordering relation</td> 107</tr> 108<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">>=</span> <span class="pre">b</span></tt></td> 109<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> 110<td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre"><</span> <span class="pre">b)</span></tt></td> 111<td> </td> 112</tr> 113<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><=</span> <span class="pre">b</span></tt></td> 114<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> 115<td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">></span> <span class="pre">b)</span></tt></td> 116<td> </td> 117</tr> 118<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> 119<td>Convertible to 120<tt class="docutils literal"><span class="pre">random_access_traversal_tag</span></tt></td> 121<td> </td> 122<td> </td> 123</tr> 124</tbody> 125</table> 126</div> 127<div class="footer"> 128<hr class="footer" /> 129<a class="reference external" href="RandomAccessTraversal.rst">View document source</a>. 130Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. 131 132</div> 133</body> 134</html> 135