Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509, Advanced Programming II

20 February 2003, Introduction to Iterators

Iterators

Iterators provide access to elements in containers.
- They serve as the connection between containers and generic algorithms.
- Iterators work only with containers.
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 element.
- That's "container element", not "container element value".
- This is similar to pointers.
The less-than operator itr1 < itr2 determines if the container element referenced by itr1 appears to the left of the container element referenced by itr2.
- "To the left of" can be read as "closer to .front()".
- Again, That's "container element", not "container element value".
- 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 continers meet iterator operator performance specs.

Iterator Categories

Each iterator category implements a subset of the iterator opererators.
The categories are matched to the ability of the continers to support the operator performace 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 arithmatic 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.

Al 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;

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.

This page last modified on 20 February 2003.