Category: iterators
Component type: concept
A Bidirectional Iterator LOGN is an iterator that can be both incremented and decremented. The requirement that a Bidirectional Iterator LOGN can be decremented (in logarithmic time) is the only thing that distinguishes Bidirectional Iterators LOGN from Forward Iterators.
A Bidirectional Iterator LOGN is identical to a Bidirectional Iterator except that the performance requirement has been changed to logarithmic time when decrementing. Incrementing remains a constant time operation.
The same as for Forward Iterator.
X | A type that is a model of Bidirectional Iterator LOGN |
T | The value type of X |
i, j | Object of type X |
t | Object of type T |
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 |
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;
--i;
return tmp;
}
|
The complexity of decrement operations on bidirectional iterators is guaranteed to be amortized logarithmic time.
| Symmetry of increment and decrement | If i is dereferenceable, then ++i; --i; is a null operation. Similarly, --i; ++i; is a null operation. |
IndexedSSkipList< T, R >::iterator IndexedSSkipList< T, R >::const_iterator IndexedTinySkipList< T, R >::iterator IndexedTinySkipList< T, R >::const_iterator SSkipList< T, Pr, R >::iterator SSkipList< T, Pr, R >::const_iterator AutoSSkipList< T, Pr, R >::iterator AutoSSkipList< T, Pr, R >::const_iterator MultiSSkipList< T, Pr, R >::iterator MultiSSkipList< T, Pr, R >::const_iterator MultiAutoSSkipList< T, Pr, R >::iterator MultiAutoSSkipList< T, Pr, R >::const_iterator KeyedSSkipList< K, T, Pr, R >::iterator KeyedSSkipList< K, T, Pr, R >::const_iterator KeyedMultiSSkipList< K, T, Pr, R >::iterator MultiKeyedSSkipList< K, T, Pr, R >::const_iterator AutoKeyedSSkipList< K, T, Pr, R >::iterator AutoKeyedSSkipList< K, T, Pr, R >::const_iterator MultiAutoKeyedSSkipList< K, T, Pr, R >::iterator MultiAutoKeyedSSkipList< K, T, Pr, R >::const_iterator AccessSSkipList< K, T, A, Pr, R >::iterator AccessSSkipList< K, T, A, Pr, R >::const_iterator MultiAccessSSkipList< K, T, A, Pr, R >::iterator MultiAccessSSkipList< K, T, A, Pr, R >::const_iterator AutoAccessSSkipList< K, T, A, Pr, R >::iterator AutoAccessSSkipList< K, T, A, Pr, R >::const_iterator MultiAutoAccessSSkipList< K, T, A, Pr, R >::iterator MultiAutoAccessSSkipList< K, T, A, Pr, R >::const_iterator SSkipList, KeyedSSkipList, AutoSSkipList, AutoKeyedSSkipList, MultiSSkipList, MultiKeyedSSkipList, MultiAutoSSkipList, MultiAutoKeyedSSkipList, IndexedSSkipList, IndexedTinySkipList, AccessSSkipList, AutoAccessSSkipList, MultiAccessSSkipList, MultiAutoAccessSSkipList,
Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, 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
1.7.3