Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509, Advanced Programming II

12 February 2004, An Introduction to Iterators

Outline

Iterators
- Operators and relations.
- Operator Performance Specs
Iterator categories
- The Iterator Hierarchy
- Input output, forward, bidirectional, and random.
Iterator Ranges
Declaring Iterators
Creating Iterators

Iterators

Iterators provide access to elements in containers.
- They serve as the connection between containers and generic algorithms.
- Iterators work with containers and other value sequences.
An iterator is a reference to a container element.
- Note that's "reference" not "address".
Iterators are better and worse than pointers.
- Better because there's less legacy C mischief to maintain.
- Worse because they can be magically broken through iterator invalidation.

Iterator Operators

The unary * operator follows an iterator to its container element.
- *itr = e: put e in a container element.
- v = *itr: get the container element.
The address-of operator & is not useful for iterators.
- ~~itr = &v;~~ is almost certainly wrong.
The pre- and post-increment operators ++ behave as for pointers.
- ++itr advances the iterator itr to the next element and returns the newly advanced iterator.
- itr++ advances itr to the next element and returns the original itr value.
- Analogously for the pre- and post-decrement operators --.

Iterator Relations

The equality operator == determines if two iterators reference the same container location.
- That's "container location", not "container element".
- This is similar to pointers.
The less-than operator itr1 < itr2 determines if the container location referenced by itr1 appears to the left of the container location referenced by itr2.
- "To the left of" can be read as "closer to .front()".
- Again, That's "container location", not "container element".
- itr1 < itr2 only makes sense if both iterators refer to the same container.
The other relations can be formed from == and <.

Operator Performance Specs

The Standard specifies performance criteria for iterator operators.
- For example, less-than has to take constant time.
But not all containers can support specified iterator performance.
- Constant less-than is easy for vector iterators.
  - Vector iterators are implemented with pointers.
- List iterators, however, can't implement a constant less-than.
  - It requires a list traversal, which is linear.
The Standard defines five iterator categories to help containers meet iterator operator performance specs.

Iterator Categories

Each iterator category implements a subset of the iterator operators.
The categories are matched to the ability of the containers to support the operator performance criteria.
There are five iterator categories arranged in an hierarchy.
Each category adds operators to the previous category.

Input Iterators

Also known as read-only iterators.
Input iterators support r-value *, member access ->, pre- and post-fix ++, and equality and inequality.
R-value *itr returns the value being referenced by the iterator itr.
- It's called r-value * because it can only appear on the right-hand side of an assignment statement.
- If itr is an input iterator, than
  - i = *itr is correct because * is being used to read itr
  - ~~*itr = i~~ is incorrect because * is being used to write itr
The member-access operator -> is defined as it is for pointers.
- itr->mbr is the same as (*itr).mbr.
Input streams std::istream support input iterators.

Output Iterators

Also known as write-only iterators.
Output iterators support l-value * and pre- and post-fix ++.
- No equality or inequality, no member access.
L-value *itr returns the container element being referenced by itr.
- It's called l-value * because it can only appear on the left-hand side of an assignment statement.
- If itr is an output iterator, than
  - ~~i = *itr~~ is incorrect because * is being used to read itr.
  - *itr = i is correct because * is being used to write itr
Output streams std::ostream support output iterators.

Forward Iterators

Forward iterators inherit from both input and output iterators.
- Forward iterators inherit l- and r-value *, member access ->, pre- and post-fix ++, and equality and inequality.
Forward iterators add the assignment operator =.
Also know as read-write iterators, or unidirectional iterators.
- *itr = *itr + 1; is correct for a forward iterator.
There are no containers that support only forward iterators.

Bidirectional Iterators

Bidirectional iterators inherit the forward iterator operators.
Forward iterators add pre- and post-fix -- for moving the iterator back to the previous container element.
Lists and the sorted associative containers support bidirectional iterators.

Random Iterators

Random iterators inherit the bidirectional-iterator operators.
Random iterators add iterator arithmetic, iterator distance, array access [], and ordering operator <.
Iterator arithmetic lets random iterators jump around the container.
- itr = itr + 5; is equivalent to
```
for (unsigned i = 0; i < 5; i++) ++itr;
```
- The plus-and-becomes operator += is also supported.
- Similarly for subtraction.
Iterator distance returns the number of elements between two iterators.
- e_cnt = end_itr - start_itr;
- The two iterators being subtracted must be from the same container.
- The compiler doesn't (can't) check to make sure.
Vectors, deques, strings, and C++ arrays support random iterators.

The Iterator Hierarchy

Why not just make all iterators random?
Not all containers can support all iterator operations efficiently.
Principle of least privilege.
- Allows the maximum number of containers to take part.
- Random iterators required? Vectors only.
- Bidirectional iterators required? Vectors and lists.

Iterator Ranges

An iterator range is a pair of iterators start,end) that defines a sequence of container elements.
An iterator range (start, end) is only sensible when
1. start and end refers to elements within the same container.
2. start appears before end start < end.
- The compiler can check neither of these conditions (usually).
By convention, the end iterator refers to the value just past the end of the range.
- Standard C-C++ pointer practice.
- The end iterator may point to a non-existent element.

Declaring Iterators

Each container class C defines its own iterator types C::iterator and C::const_iterator.
```
std::vector<int> ivec;
std::vector<int>::iterator itr;
std::vector<int>::const_iterator citr;
```
- C defines other iterator types too.

As always, typedefs help keep declarations manageable.

typedef std::vector<int>        int_vec;
typedef int_vec::iterator       ivec_itr;
typedef int_vec::const_iterator ivec_citr;

int_vec ivec;
ivec_itr itr;
ivec_citr citr;

It is not possible to declare iterators of a particular category.
- ~~std::vector<int>::random_iterator i~~
- The iterator category is defined by the associated container.

Creating Iterators

Each container class C has member functions that return iterators referencing C's elements.
C.begin() returns an iterator to the first element in C.
- C.begin() returns an iterator even if C has no elements.
```
std::vector<int> ivec;
std::vector<int>::iterator start = ivec.begin();
```
- This is not illegal, but requires care.

C.end() returns an iterator to one-past the last element in C.

std::vector<int> ivec;
std::vector<int>::iterator end = ivec.end();

C.begin() equals C.end() when C is empty.
Some containers have other member functions returning iterators.
Many generic algorithms return iterators too.

Other Iterator Types

There are three other iterator types defined for each container.
1. C::const_iterator
2. C::reverse_iterator
3. C::const_reverse_iterator
4. ~~C::reverse_const_iterator~~
These are generally less useful then C::iterator, but handy on occasion.
- Some member functions require iterators, not constant iterators.
- Conversions between iterator types is either impossible, difficult, inefficient, or confusing.

Constant Iterators

A constant iterator cannot change the value stored at the location associated with the iterator.
- The iterator itself is not constant.
```
ivec::const_iterator i = iv.begin();
if (*i == 1) i++;
if (*i == 2) *i = 3;
```
Constant iterators come from constant containers or by promoting non-constant iterators.
```
void f(const C & in, C & out)
  C::const_iterator 
    i = out.begin(),
    j = in.begin();
  C::iterator k = in.begin();
```
- Constant iterators can't be converted to non-constant iterators.
Constant iterators are useful, but getting everything just so can be a pain.

Reverse Iterators

Reverse iterators are just like iterators except backward.
Reverse iterators come from the r member functions.
Reverse and regular iterators convert in both directions.
- Although not particularly easily or conveniently.

Points to Remember

Iterators connect containers and generic algorithms.
Iterators access values in containers.
- Iterators are like pointers, except when they're not.
There are five iterator categories in an hierarchy.
- The available operators differ between categories.
Iterator ranges describe value sequences.
- This is standard C-C++ practice.
And don't forget constant and reverse iterators.
- Just the right tool at the right time.

This page last modified on 25 February 2004.