]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
18 | concept if the following expressions are valid and respect the stated | |
19 | semantics. 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 | |
21 | constant 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/ | |
36 | Precondition</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 | |
79 | value <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 | |
88 | Iterator</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 | |
94 | iterator</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 | |
100 | ordering 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 | |
106 | ordering 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>. | |
130 | Generated 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> |