Bidirectional Iterator

Category: iterators
Component type: concept


A Bidirectional Iterator is an iterator that can be both incremented and decremented. The requirement that a Bidirectional Iterator can be decremented is the only thing that distinguishes Bidirectional Iterators from Forward Iterators.

Refinement of

Forward Iterator

Associated types

The same as for Forward Iterator.


X A type that is a model of Bidirectional Iterator
T The value type of X
i, j Object of type X
t Object of type T


Valid expressions

In addition to the expressions defined in Forward Iterator, the following expressions must be valid.

Name Expression Type requirements Return type
Predecrement --i   X&
Postdecrement i--   X

Expression Semantics

Semantics of an expression is defined only where it is not defined in Forward Iterator.

Name Expression Precondition Semantics Postcondition
Predecrement --i i is dereferenceable or past-the-end. There exists a dereferenceable iterator j such that i == ++j. i is modified to point to the previous element. i is dereferenceable. &i = &--i. If i == j, then --i == --j. If j is dereferenceable and i == ++j, then --i == j.
Postdecrement i-- i is dereferenceable or past-the-end. There exists a dereferenceable iterator j such that i == ++j. Equivalent to
  X tmp = i;
  return tmp;

Complexity guarantees

The complexity of operations on bidirectional iterators is guaranteed to be amortized constant time.


Symmetry of increment and decrement If i is dereferenceable, then ++i; --i; is a null operation. Similarly, --i; ++i; is a null operation.



See also

SkipList, KeyedSkipList, AutoSkipList, AutoKeyedSkipList, MultiSkipList, MultiKeyedSkipList, MultiAutoSkipList, MultiAutoKeyedSkipList, IndexedSkipList, XIndexedSkipList, XMultiSkipList, XMultiAutoSkipList, AccessSkipList, AutoAccessSkipList, MultiAccessSkipList, MultiAutoAccessSkipList, XMultiAccessSkipList, XMultiAutoAccessSkipList,

Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator LOGN, Random Access Iterator, Random Access Iterator LOGN, Arbitrary Access Iterator LOGN, Forward Arbitrary Access Iterator, Forward Arbitrary Access Iterator LOGN, Reverse Arbitrary Access Iterator, Reverse Arbitrary Access Iterator LOGN, Iterator Overview

 All Classes Files Functions Variables Typedefs