Bidirectional Iterator LOGN

Category: iterators
Component type: concept

Description

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.

Refinement of

Forward Iterator

Associated types

The same as for Forward Iterator.

Notation

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

Definitions

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;
  --i;
  return tmp;
}
 

Complexity guarantees

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

Invariants

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

Models

Notes

See also

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

 All Classes Files Functions Variables Typedefs