1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Bidirectional Iterator</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="forward_iterator.html" title="Forward Iterator"> 10<link rel="next" href="random_access_iterator.html" title="Random Access Iterator"> 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="forward_iterator.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="random_access_iterator.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.iterator.concepts.bidirectional_iterator"></a><a class="link" href="bidirectional_iterator.html" title="Bidirectional Iterator">Bidirectional 28 Iterator</a> 29</h4></div></div></div> 30<h6> 31<a name="fusion.iterator.concepts.bidirectional_iterator.h0"></a> 32 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.description"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.description">Description</a> 33 </h6> 34<p> 35 A Bidirectional Iterator traverses a <a class="link" href="../../sequence.html" title="Sequence">Sequence</a> 36 allowing movement in either direction one element at a time. 37 </p> 38<div class="variablelist"> 39<p class="title"><b>Notation</b></p> 40<dl class="variablelist"> 41<dt><span class="term"><code class="computeroutput"><span class="identifier">i</span></code></span></dt> 42<dd><p> 43 A Bidirectional Iterator 44 </p></dd> 45<dt><span class="term"><code class="computeroutput"><span class="identifier">I</span></code></span></dt> 46<dd><p> 47 A Bidirectional Iterator type 48 </p></dd> 49<dt><span class="term"><code class="computeroutput"><span class="identifier">M</span></code></span></dt> 50<dd><p> 51 An <a href="http://www.boost.org/libs/mpl" target="_top">MPL</a> integral 52 constant 53 </p></dd> 54<dt><span class="term"><code class="computeroutput"><span class="identifier">N</span></code></span></dt> 55<dd><p> 56 An integral constant 57 </p></dd> 58</dl> 59</div> 60<h6> 61<a name="fusion.iterator.concepts.bidirectional_iterator.h1"></a> 62 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.refinement_of"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.refinement_of">Refinement 63 of</a> 64 </h6> 65<p> 66 <a class="link" href="forward_iterator.html" title="Forward Iterator">Forward Iterator</a> 67 </p> 68<h6> 69<a name="fusion.iterator.concepts.bidirectional_iterator.h2"></a> 70 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.expression_requirements"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.expression_requirements">Expression 71 requirements</a> 72 </h6> 73<p> 74 In addition to the requirements defined in <a class="link" href="forward_iterator.html" title="Forward Iterator">Forward 75 Iterator</a>, the following expressions must be valid: 76 </p> 77<div class="informaltable"><table class="table"> 78<colgroup> 79<col> 80<col> 81<col> 82</colgroup> 83<thead><tr> 84<th> 85 <p> 86 Expression 87 </p> 88 </th> 89<th> 90 <p> 91 Return type 92 </p> 93 </th> 94<th> 95 <p> 96 Runtime Complexity 97 </p> 98 </th> 99</tr></thead> 100<tbody> 101<tr> 102<td> 103 <p> 104 <code class="computeroutput"><a class="link" href="../functions/next.html" title="next"><code class="computeroutput"><span class="identifier">next</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">)</span></code> 105 </p> 106 </td> 107<td> 108 <p> 109 <a class="link" href="bidirectional_iterator.html" title="Bidirectional Iterator">Bidirectional 110 Iterator</a> 111 </p> 112 </td> 113<td> 114 <p> 115 Constant 116 </p> 117 </td> 118</tr> 119<tr> 120<td> 121 <p> 122 <code class="computeroutput"><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">)</span></code> 123 </p> 124 </td> 125<td> 126 <p> 127 <a class="link" href="bidirectional_iterator.html" title="Bidirectional Iterator">Bidirectional 128 Iterator</a> 129 </p> 130 </td> 131<td> 132 <p> 133 Constant 134 </p> 135 </td> 136</tr> 137<tr> 138<td> 139 <p> 140 <code class="computeroutput"><a class="link" href="../functions/advance_c.html" title="advance_c"><code class="computeroutput"><span class="identifier">advance_c</span></code></a><span class="special"><</span><span class="identifier">N</span><span class="special">>(</span><span class="identifier">i</span><span class="special">)</span></code> 141 </p> 142 </td> 143<td> 144 <p> 145 <a class="link" href="bidirectional_iterator.html" title="Bidirectional Iterator">Bidirectional 146 Iterator</a> 147 </p> 148 </td> 149<td> 150 <p> 151 Constant 152 </p> 153 </td> 154</tr> 155<tr> 156<td> 157 <p> 158 <code class="computeroutput"><a class="link" href="../functions/advance.html" title="advance"><code class="computeroutput"><span class="identifier">advance</span></code></a><span class="special"><</span><span class="identifier">M</span><span class="special">>(</span><span class="identifier">i</span><span class="special">)</span></code> 159 </p> 160 </td> 161<td> 162 <p> 163 <a class="link" href="bidirectional_iterator.html" title="Bidirectional Iterator">Bidirectional 164 Iterator</a> 165 </p> 166 </td> 167<td> 168 <p> 169 Constant 170 </p> 171 </td> 172</tr> 173</tbody> 174</table></div> 175<h6> 176<a name="fusion.iterator.concepts.bidirectional_iterator.h3"></a> 177 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.meta_expressions"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.meta_expressions">Meta 178 Expressions</a> 179 </h6> 180<div class="informaltable"><table class="table"> 181<colgroup> 182<col> 183<col> 184</colgroup> 185<thead><tr> 186<th> 187 <p> 188 Expression 189 </p> 190 </th> 191<th> 192 <p> 193 Compile Time Complexity 194 </p> 195 </th> 196</tr></thead> 197<tbody><tr> 198<td> 199 <p> 200 <code class="computeroutput"><a class="link" href="../metafunctions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">prior</span></code></a><span class="special"><</span><span class="identifier">I</span><span class="special">>::</span><span class="identifier">type</span></code> 201 </p> 202 </td> 203<td> 204 <p> 205 Amortized constant time 206 </p> 207 </td> 208</tr></tbody> 209</table></div> 210<h6> 211<a name="fusion.iterator.concepts.bidirectional_iterator.h4"></a> 212 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.expression_semantics"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.expression_semantics">Expression 213 Semantics</a> 214 </h6> 215<p> 216 The semantics of an expression are defined only where they differ from, 217 or are not defined in <a class="link" href="forward_iterator.html" title="Forward Iterator">Forward 218 Iterator</a> 219 </p> 220<div class="informaltable"><table class="table"> 221<colgroup> 222<col> 223<col> 224</colgroup> 225<thead><tr> 226<th> 227 <p> 228 Expression 229 </p> 230 </th> 231<th> 232 <p> 233 Semantics 234 </p> 235 </th> 236</tr></thead> 237<tbody><tr> 238<td> 239 <p> 240 <code class="computeroutput"><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">)</span></code> 241 </p> 242 </td> 243<td> 244 <p> 245 An iterator to the element preceding <code class="computeroutput"><span class="identifier">i</span></code> 246 </p> 247 </td> 248</tr></tbody> 249</table></div> 250<h6> 251<a name="fusion.iterator.concepts.bidirectional_iterator.h5"></a> 252 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.invariants"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.invariants">Invariants</a> 253 </h6> 254<p> 255 In addition to the invariants of <a class="link" href="forward_iterator.html" title="Forward Iterator">Forward 256 Iterator</a>, the following invariants always hold: 257 </p> 258<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 259<li class="listitem"> 260 <code class="computeroutput"><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><a class="link" href="../functions/next.html" title="next"><code class="computeroutput"><span class="identifier">next</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">))</span> <span class="special">==</span> <span class="identifier">i</span> <span class="special">&&</span> 261 <a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><a class="link" href="../functions/next.html" title="next"><code class="computeroutput"><span class="identifier">next</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">))</span> <span class="special">==</span> <a class="link" href="../functions/next.html" title="next"><code class="computeroutput"><span class="identifier">next</span></code></a><span class="special">(</span><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">))</span></code> 262 </li> 263<li class="listitem"> 264 <code class="computeroutput"><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">==</span> <a class="link" href="../functions/advance_c.html" title="advance_c"><code class="computeroutput"><span class="identifier">advance_c</span></code></a><span class="special"><-</span><span class="number">1</span><span class="special">>(</span><span class="identifier">i</span><span class="special">)</span></code> 265 </li> 266<li class="listitem"> 267 Using <code class="computeroutput"><a class="link" href="../functions/prior.html" title="prior"><code class="computeroutput"><span class="identifier">prior</span></code></a></code> to traverse a 268 sequence will never return a previously seen position 269 </li> 270</ul></div> 271<h6> 272<a name="fusion.iterator.concepts.bidirectional_iterator.h6"></a> 273 <span class="phrase"><a name="fusion.iterator.concepts.bidirectional_iterator.models"></a></span><a class="link" href="bidirectional_iterator.html#fusion.iterator.concepts.bidirectional_iterator.models">Models</a> 274 </h6> 275<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 276<li class="listitem"> 277 <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> 278 iterator 279 </li> 280<li class="listitem"> 281 <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> 282 iterator 283 </li> 284<li class="listitem"> 285 <a class="link" href="../../container/vector.html" title="vector"><code class="computeroutput"><span class="identifier">vector</span></code></a> 286 iterator 287 </li> 288<li class="listitem"> 289 <a class="link" href="../../container/map.html" title="map"><code class="computeroutput"><span class="identifier">map</span></code></a> 290 iterator 291 </li> 292<li class="listitem"> 293 <a class="link" href="../../view/single_view.html" title="single_view"><code class="computeroutput"><span class="identifier">single_view</span></code></a> 294 iterator 295 </li> 296<li class="listitem"> 297 <a class="link" href="../../view/iterator_range.html" title="iterator_range"><code class="computeroutput"><span class="identifier">iterator_range</span></code></a> 298 (where adapted sequence is a <a class="link" href="../../sequence/concepts/bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 299 Sequence</a>) 300 </li> 301<li class="listitem"> 302 <a class="link" href="../../view/transform_view.html" title="transform_view"><code class="computeroutput"><span class="identifier">transform_view</span></code></a> 303 (where adapted sequence is a <a class="link" href="../../sequence/concepts/bidirectional_sequence.html" title="Bidirectional Sequence">Bidirectional 304 Sequence</a>) 305 </li> 306<li class="listitem"> 307 <a class="link" href="../../view/reverse_view.html" title="reverse_view"><code class="computeroutput"><span class="identifier">reverse_view</span></code></a> 308 </li> 309</ul></div> 310</div> 311<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 312<td align="left"></td> 313<td align="right"><div class="copyright-footer">Copyright © 2001-2006, 2011, 2012 Joel de Guzman, 314 Dan Marsden, Tobias Schwinger<p> 315 Distributed under the Boost Software License, Version 1.0. (See accompanying 316 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>) 317 </p> 318</div></td> 319</tr></table> 320<hr> 321<div class="spirit-nav"> 322<a accesskey="p" href="forward_iterator.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="random_access_iterator.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 323</div> 324</body> 325</html> 326
