Iterators in reversible containers

A container may also be reversible, which means that it can produce iterators that move backward from the end, as well as the iterators that move forward from the beginning. All standard containers support iterators such bidirectional iteration.

A reversible container has the member functions rbegin( ) (to produce a reverse_iterator selecting the end) and rend( ) (to produce a reverse_iterator indicating ?one past the beginning?). If the container is const, rbegin( ) and rend( ) will produce const_reverse_iterators.
The following example uses vector, but will work with all containers that support iteration:

You move backward through the container using the same syntax as moving forward through a container with an ordinary iterator.

Iterator categories

The iterators are classified into ?categories? that describe their capabilities. The order in which they are generally described moves from the categories with the most restricted behavior to those with the most powerful behavior.

Input: read-only, one pass
The only predefined implementations of input iterators are istream_iterator and istreambuf_iterator, to read from an istream. As you can imagine, an input iterator can only be dereferenced once for each element that?s selected, just as you can only read a particular portion of an input stream once. They can only move forward. A special constructor defines the past-the-end value. In summary, you can dereference it for reading (once only for each value) and move it forward.

Output: write-only, one pass
This is the complement of an input iterator, but for writing rather than reading. The only predefined implementations of output iterators are ostream_iterator and ostreambuf_iterator, to write to an ostream, and the less commonly used raw_storage_iterator. Again, these can only be dereferenced once for each written value, and they can only move forward. There is no concept of a terminal past-the-end value for an output iterator. Summarizing, you can dereference it for writing (once only for each value) and move it forward.

Forward: multiple read/write
The forward iterator contains all the functionality of both the input iterator and the output iterator, plus you can dereference an iterator location multiple times, so you can read and write to a value multiple times. As the name implies, you can only move forward. There are no predefined iterators that are only forward iterators.

Bidirectional: operator–
The bidirectional iterator has all the functionality of the forward iterator, and in addition it can be moved backward one location at a time using operator–.

Random-access: like a pointer
Finally, the random-access iterator has all the functionality of the bidirectional iterator plus all the functionality of a pointer (a pointer is a random-access iterator). Basically, anything you can do with a pointer you can do with a random-access iterator, including indexing with operator[ ], adding integral values to a pointer to move it forward or backward by a number of locations, and comparing one iterator to another with <, >=, and so on.

Is this really important?
Why do you care about this categorization? When you?re just using containers in a straightforward way (for example, just hand-coding all the operations you want to perform on the objects in the container), it usually doesn?t impact you too much. Things either work or they don?t. The iterator categories become important when:

1. You use some of the fancier built-in iterator types that will be demonstrated shortly. Or you graduate to creating your own iterators.
2 . You use the STL algorithms. Each of the algorithms has requirements that it places on the iterators with which it works. Knowledge of the iterator categories is even more important when you create your own reusable algorithm templates, because the iterator category that your algorithm requires determines how flexible the algorithm will be. If you require only the most primitive iterator category (input or output), your algorithm will work with everything (copy( ) is an example of this).
A hierarchy of iterator tag classes identify the category of an iterator. The class names correspond to the iterator categories, as you would expect, and their derivation reflects the relationship between them:

The class forward_iterator_tag derives only from input_iterator_tag, not from output_iterator_tag, because we need to have past-the-end iterators in algorithms that use forward iterators, and output iterators don?t have them. For efficiency, certain algorithms provide different implementations for different iterator types, which they infer from the iterator tag defined by the iterator.

Share
Tweet
Share
Pin