1<?xml version="1.0"?> 2<concept name="BidirectionalIterator" category="Iterator"><!-- 3Based on concepts from the SGI Standard Template Library documentation: 4Copyright (c) 1996-1999 5Silicon Graphics Computer Systems, Inc. 6 7Copyright (c) 1994 8Hewlett-Packard Company 9--><!-- 10Copyright 2000-2001 University of Notre Dame du Lac. 11Copyright 2001-2002 Indiana University. 12Some concepts based on versions from the MTL draft manual and Boost Graph 13and Property Map documentation: 14Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 15--> 16 <param name="Iter" role="iterator-type"/> 17 18 <use-header name="iterator"/> 19 20 <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence> 21 22 <description> 23 <para>A bidirectional iterator is an iterator that can read through a sequence 24 of values. It can move in either direction through the sequence, and can 25 be either mutable (data pointed to by it can be changed) or not mutable.</para> 26 27 <para>An iterator represents a position in a sequence. Therefore, the 28 iterator can point into the sequence (returning a value when dereferenced 29 and being incrementable), or be off-the-end (and not dereferenceable or 30 incrementable).</para> 31 </description> 32 33 <associated-type name="value_type"> 34 <get-member-type name="value_type"> 35 <apply-template name="std::iterator_traits"> 36 <type name="Iter"/> 37 </apply-template> 38 </get-member-type> 39 <description><simpara>The value type of the iterator</simpara></description> 40 </associated-type> 41 42 <refines const="no" concept="ForwardIterator"/> 43 44 <notation variables="i j"> 45 <sample-value> 46 <type name="Iter"/> 47 </sample-value> 48 </notation> 49 50 <associated-type name="category"> 51 <get-member-type name="iterator_category"> 52 <apply-template name="std::iterator_traits"> 53 <type name="Iter"/> 54 </apply-template> 55 </get-member-type> 56 <description><simpara>The category of the iterator</simpara></description> 57 </associated-type> 58 59 <notation variables="x"> 60 <sample-value> 61 <type name="value_type"/> 62 </sample-value> 63 </notation> 64 65 <valid-type-expression name="Category tag"> 66 <description/> 67 <type name="category"/> 68 <return-type> 69 <derived-from testable="yes"> 70 <type name="std::bidirectional_iterator_tag"/> 71 </derived-from> 72 </return-type> 73 </valid-type-expression> 74 75 <valid-expression name="Predecrement"> 76 <predecrement> 77 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 78 </predecrement> 79 <return-type> 80 <require-same-type testable="yes"> 81 <reference-to><type name="Iter"/></reference-to> 82 </require-same-type> 83 </return-type> 84 <precondition><code>i</code> is incrementable (not 85 off-the-end) and some dereferenceable iterator <code>j</code> exists 86 such that <code>i == ++j</code></precondition> 87 </valid-expression> 88 89 <valid-expression name="Postdecrement"> 90 <postdecrement> 91 <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> 92 </postdecrement> 93 <return-type> 94 <require-same-type testable="yes"><type name="Iter"/></require-same-type> 95 </return-type> 96 <precondition>Same as for predecrement</precondition> 97 <semantics>Equivalent to <code>{Iter j = i; --i; return j;}</code></semantics> 98 <postcondition><code>i</code> is dereferenceable or 99 off-the-end</postcondition> 100 </valid-expression> 101 102 <complexity> 103 All iterator operations must take amortized constant time. 104 </complexity> 105 106 <invariant name="Predecrement must return object"> 107 <code>&i = &(--i)</code> 108 </invariant> 109 110 <invariant name="Unique path through sequence"> 111 <code>i == j</code> implies <code>--i == --j</code> 112 </invariant> 113 114 <invariant name="Increment and decrement are inverses"> 115 <code>++i; --i;</code> and <code>--i; ++i;</code> must end up with the 116 value of <code>i</code> unmodified, if <code>i</code> both of the 117 operations in the pair are valid. 118 </invariant> 119 120 <example-model> 121 <pointer-to> 122 <type name="T"/> 123 </pointer-to> 124 </example-model> 125 126 <example-model> 127 <get-member-type name="iterator"> 128 <apply-template name="std::list"> 129 <type name="T"/> 130 </apply-template> 131 </get-member-type> 132 </example-model> 133 134 <see-also concept="RandomAccessIterator"/> 135 136</concept> 137