1.. Iterators/Concepts//Bidirectional Iterator |20 2 3Bidirectional Iterator 4====================== 5 6Description 7----------- 8 9A |Bidirectional Iterator| is a |Forward Iterator| that provides a way to 10obtain an iterator to the previous element in a sequence. 11 12Refinement of 13------------- 14 15|Forward Iterator| 16 17Definitions 18----------- 19 20* a bidirectional iterator ``i`` is `decrementable` if there is a "previous" 21 iterator, that is, if ``prior<i>::type`` expression is well-defined; 22 iterators pointing to the first element of the sequence are not 23 decrementable. 24 25 26Expression requirements 27----------------------- 28 29In addition to the requirements defined in |Forward Iterator|, 30the following requirements must be met. 31 32+-----------------------+-------------------------------------------+---------------------------+ 33| Expression | Type | Complexity | 34+=======================+===========================================+===========================+ 35| ``next<i>::type`` | |Bidirectional Iterator| | Amortized constant time | 36+-----------------------+-------------------------------------------+---------------------------+ 37| ``prior<i>::type`` | |Bidirectional Iterator| | Amortized constant time | 38+-----------------------+-------------------------------------------+---------------------------+ 39| ``i::category`` | |Integral Constant|, convertible | Constant time | 40| | to ``bidirectional_iterator_tag`` | | 41+-----------------------+-------------------------------------------+---------------------------+ 42 43 44Expression semantics 45-------------------- 46 47.. parsed-literal:: 48 49 typedef prior<i>::type j; 50 51:Precondition: 52 ``i`` is decrementable 53 54:Semantics: 55 ``j`` is an iterator pointing to the previous element of the 56 sequence 57 58:Postcondition: 59 ``j`` is dereferenceable and incrementable 60 61 62Invariants 63---------- 64 65For any bidirectional iterators ``i`` and ``j`` the following invariants 66always hold: 67 68* If ``i`` is incrementable, then ``prior< next<i>::type >::type`` is a null 69 operation; similarly, if ``i`` is decrementable, ``next< prior<i>::type >::type`` 70 is a null operation. 71 72 73See also 74-------- 75 76|Iterators|, |Forward Iterator|, |Random Access Iterator|, |Bidirectional Sequence|, |prior| 77 78 79.. copyright:: Copyright � 2001-2009 Aleksey Gurtovoy and David Abrahams 80 Distributed under the Boost Software License, Version 1.0. (See accompanying 81 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 82