Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/iterator/doc/RandomAccessTraversal.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 7.8 KB
Line 
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&lt;X&gt;::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&amp;</span></tt></td>
42<td><pre class="first last literal-block">
43{
44  Distance m = n;
45  if (m &gt;= 0)
46    while (m--)
47      ++r;
48  else
49    while (m++)
50      --r;
51  return r;
52}
53</pre>
54</td>
55<td>&nbsp;</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>&nbsp;</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&amp;</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>&nbsp;</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>&nbsp;</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">&lt;</span> <span class="pre">b</span> <span class="pre">?</span>&nbsp; <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">&lt;</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">&gt;</span> <span class="pre">0</span></tt></td>
99<td><tt class="docutils literal"><span class="pre">&lt;</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">&gt;</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">&lt;</span> <span class="pre">a</span></tt></td>
105<td><tt class="docutils literal"><span class="pre">&gt;</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">&gt;=</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">&lt;</span> <span class="pre">b)</span></tt></td>
111<td>&nbsp;</td>
112</tr>
113<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&lt;=</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">&gt;</span> <span class="pre">b)</span></tt></td>
116<td>&nbsp;</td>
117</tr>
118<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::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>&nbsp;</td>
122<td>&nbsp;</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>
Note: See TracBrowser for help on using the repository browser.