Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509, Advanced Programming II

26 February 2004, Some Iterator Adaptors

Outline

Iterator Adaptors
Insert Iterator Adaptors
- Back Insert Iterator Adaptor
- Front Insert Iterator Adaptor
- Insert Iterator Adaptor
Some more bad code
Input and Output Iterators
- Output Iterator Adaptor
- Input Iterator Adaptor
  - The EOS Istream Iterator
  - Istream Iterator Operators

Some Loopy Code

Copy a bunch of ints from one vector to another.

for (i = 0; i < src.size(); i++)
  dst.push_back(src[i])

Filter out all the odd numbers.

for (i = 0; i < ivec.size(); i++)
  if even(ivec[i])
    evens.push_back(ivec[i])

Loops are bad. Can we replace them with generic algorithms?
- And watch out for the mutating-algorithm trap.

The Mutating-Algorithm Trap

Remember the mutating-algorithm trap.
- Generic algorithms can only change container elements, not containers themselves.

Iterators can only overwrite values, they can't insert them.

outi copy(outi d, ini b, ini e)

  while b != e
    *d++ = *b++

  return d

std::vector v1(10);
std::list l2;
copy(l2.begin(), v1.begin(), v1.end())

As an aside, prefer member functions to generic algorithms.

std::vector v1(10);
std::list l2(v1.begin(), v1.end());

Iterator Adaptors

An iterator adaptor changes an iterator's behavior, or extends it use.
Insert iterators let iterators change containers.
I-O stream iterators create iterators into I-O streams.
Reverse iterators make iterators go backwards.
You can write your own iterator adaptors too.
- Overwrite-insert iterator adaptors.

Insert Iterator Adaptors

An insert iterator adapter changes an iterator's behavior from overwriting values to inserting them.
There are three insert iterator adapter kinds for inserting in the front, back, or anywhere in a container.
- As always, not all containers support all insert iterator adaptors kinds.
Insert iterator adaptors are template classes.
- The template parameter is the container type.
- The constructor takes a container and possibly an iterator.
- Helper functions that make declarations easy.
Insert iterator adaptors are defined in <iterator>.
Insert iterator adaptors are output iterators.
- Operations l-value *, pre and post ++, and assignment.
- All but assignment are no-ops.

Back Insert Iterator Adaptor

A back-insert iterator (or just back inserter) inserts values at the end of a container.
The back-insert iterator adapter is a class with one template parameter.
```
template < class ContainerT >
class back_insert_iterator { ... };
```
The constructor accepts the container into which values are inserted.
```
vector<int> ivec;
back_insert_iterator<vector<int> > bi(ivec);
```

The helper function is std::back_inserter(c, pos).

copy(
  l1.begin(), l1.end(), 
  back_insert_iterator<vector<int> >(v1))

copy(
  l1.begin(), l1.end(), back_inserter(v1))

*bi++ = v pushes v onto the end of c.

Back Inserter Implementation

template < class ContainerT >
back_insert_iterator {

  ContainerT cont

  back_insert_iterator(ContainerT c) 
    : cont(c) { }

  operator = (ContainerT::value_type v)
    cont.push_back(v);

  operator * (void) 
    return * this;

  // similarly for pre and post ++
  }

Back Inserter Pointers

A back inserter is always an output iterator.
- The back-inserter container doesn't enter into it.
```
vector<int> ivec;
back_insert_iterator<vector<int> > bi(ivec);
bi[1] = 3
```
The back-inserter container must support push_back().
- Vectors, not maps.
Even though it's not necessary, use all the operators.
```
*bi++ = 3   // ok but redundant.
bi = 4      // ok but confusing.
```
- Good compilers will get rid of the no-ops.
- It's confusing to readers.
Similar pointers apply to the other insert iterator adaptors.

Front Insert Iterator Adaptor

A front-insert iterator (or just front inserter) inserts values at the start of a container.
The front-insert iterator adapter is a class with one template parameter.
```
template < class ContainerT >
class front_insert_iterator { ... };
```
The constructor accepts the container into which values are inserted.
```
vector<int> ivec;
front_insert_iterator<vector<int> > fi(ivec);
```

The helper function is std::front_inserter(c).

std::copy(
  l1.begin(), l1.end(), 
  std::front_inserter(v1))

Vectors not allowed. (why?)

Insert Iterator Adaptor

An insert iterator (or just inserter) inserts values somewhere in a container.
The insert-iterator adapter is a class with one template parameter.
```
template < class ContainerT >
class insert_iterator { ... };
```

The constructor accepts a container and an iterator into the container.

vector<int> ivec(10);
insert_iterator<vector<int> > bi(ivec, ivec.begin() + 1);

The helper function is std::inserter(c, i).
*bi++ = v inserts v at the initial iterator.
- The initial iterator always points to the same element.

Insert Iterators vs. Loops

Copy a bunch of ints from one vector to another.

for (i = 0; i < src.size(); i++)
  dst.push_back(src[i])

std::copy(
  src.begin(), src.end(),
  std::back_inserter(dst))

Filter out all the odd numbers.

for (i = 0; i < ivec.size(); i++)
  if even(ivec[i])
    evens.push_back(ivec[i])

std::remove_copy_if(
  ivec.begin(), ivec.end(),
  std::back_inserter(evens),
  even)

More Loopy Code

Output a bunch of ints.

std::ostream & 
operator << (std::ostream & os, ivec ints)

  ivec_iter i;
  for (i = ints.begin(); i != ints.end(); i++)
    os << *i

  return os

Input a bunch of ints.
```
while iss >> i
  ints.push_back(i)
```
These loops involve stream I-O.
- How can we get rid of them anyway?

Input and Output Iterators

I-O streams are a sequence of values, just like sequential containers are.
It would be nice to treat I-O streams like containers
- Simplify and unify container I-O.
- Use generic algorithms.
Input and output iterators turn i-o streams into iterator accessible containers.
They are template classes.
- The template parameter is the type of the value being read or written.
- The constructor parameter is the stream involved.
- Helper functions aren't provided for I-O streams.
I-O streams are defined in <iterator>.

The Output Iterator Adaptor

An ostream iterator inserts values into an output stream.
The ostream-iterator adaptor is a class with one template parameter (actually three template parameters).
```
template < class ElementT >
class ostream_iterator { ... };
```
The constructor accepts the ostream into which values are written.
```
ostream_iterator<int> osi(cout)
```
- An optional second constructor argument provides a string to output between elements.
  - The default is the empty string.
  - The second argument has type const char *.
```
ostream_iterator<int> osi(cout, ", ")
```
operator << (ElementT) must be defined.

Output Iterator Operators

Ostream iterators are (surprise!) output iterators.

* and ++ are no-ops; = does the write.

ostream_iterator<int> osi(cout, " ");

*osi++ = 1;  // write 1 to std-out
osi = 2;     // write 2 to std-out

Input Iterator Adaptor

An istream iterator extracts values from an input stream.
The istream-iterator adaptor is a class with one template parameter (actually four template parameters).
```
template < class ElementT >
class istream_iterator { ... };
```
The constructor accepts the istream from which values are read.
```
std::istream_iterator<int> isi(cin)
```
- The constructor may read a value (or it may not).
operator >> (ElementT) must be defined.
But what, you may ask, about EOS?

The EOS Istream Iterator

The underlying input stream determines the EOS condition.
The default istream-iterator constructor creates an EOS iterator.
- The next iterator after an EOS or error is the EOS iterator.
- Use == against the EOS iterator, not .eof().
- Testing the underlying istream for EOS directly is not a good idea.

Istream Iterator Operators

An istream iterator is a (surprise!) input iterator.
r-value * returns the most recently read value.
- It may also do the first read if necessary.
Arrow -> returns a field in the most recently read value.
Prefix ++ reads a new value and returns an istream iterator to it.
Postfix ++ reads a new value and returns an istream iterator to the previously read value.
Equality (==) returns true if and only if
- Both istream iterators are at EOS.
- Both istream iterators are not at EOS, and both are based on the same input stream.
- Specific stream values don't matter for equality.

Istream Iterator Pointers

Equality has non-intuitive behavior; be careful.
- For non-EOS istream iterators, i == j does not imply *i == *j.
- Also, i == j does not imply ++i == ++j. (why?)
Istream iterators can do implementation-dependent buffering.
- This makes it hard to know the next value from the istream.
  - Is the next value in the istream or buffered in the iterator?
- Istream EOS may not really be EOS.
  - The iterator could buffer the last value.
Don't use the istream and its associated istream iterator at the same time.

I-O Stream Iterators vs. Loops

Output a bunch of ints.

std::ostream & 
operator << (std::ostream & os, pile p)

  ivec_iter i;
  for (i = ints.begin(); i != ints.end(); i++)
    os << *i

  std::copy(ints.begin(), ints.end(), 
            std::ostream_iterator(os));

  return os

Input a bunch of ints.

while iss >> i
  ints.push_back(i)

std::copy(
  std::istring_stream<int>(iss),
  std::istring_stream<int>(),
  std::back_inserter(ints));

Points to Remember

Replace loops with generic algorithms.
Iterator adaptors change iterator behavior.
Insert iterator adaptors avoid the mutating-algorithm trap.
- And make containers safe for generic algorithms.
There are back, front, and general inserter adaptors.
- Not all containers support all adaptors.
I-O stream iterators turn I-O streams into containers.
- And make them safe for generic algorithms.
Input Iterators are touchy.
- EOS, equality, and buffering behavior.
Don't abuse iterator operator notations.
- It confuses the unwary.

This page last modified on 2 March 2004.