Categories of iterators

Lecture 6 - Slide 5 : 40

Tabular overview of the five catetories at the top of page 956 in The C++ Prog. Lang. (4. edition)

The classification below shows operations that can be implemented efficiently - O(1)

The C++ Prog. Lang. (3. edition): Page 550

The C++ Prog. Lang. (4. edition): Page 955

Iterator categories at cplusplus.com

All iterators
- ++, *
Input iterator p
- Can read the current element (at least once) by x = *p
- Cannot necessarily write to current element by *p = x
- Other operators: ==, !=
Output iterator p
- Can write (once) into the container with *p = x
- Cannot necessarily read the current element by x = *p
Forward
- Like input and output iterator
- Can read and write repeatedly
Bidirectional
- Like forward iterator
- -- applies
Random-access
- Like bidirectional iterator
- Can add and subtract integers to/from iterators
- Can compare iterators with <, <=, >, and >=

The categories are not represented by inheritance, but they appear in iterator tags types (page 956 The C++ Prog. Lang. (4. edition)) - used for convenient functions overloding

The distance between two iterators can be calculated for most iterators, simply by advancing the first until it meets the other