Lecture Notes for CS 509, Advanced Programming II

21 November 2002, Overwriting-Inserting Iterators

Outline

• Reading with the STL.

  • Handling errors.

• Overwrite-Back Insert Iterators

  • The Overwrite-Back Insert Iterator class.

  • Constructors

  • Output iterator operators.

  • The assignment operator.

  • Helper functions.

• Using overwrite iterators.

• So what?

• Trust no one.

Reading Puzzle Outlines

• A tangram puzzle is a sequence of 2-d points.

  • Each point is a pair of floating point numbers.

• Reading tangram puzzles is easy thanks to the STL.

  std::vector<double>
  read_puzzle_coords(std::istream & ins) {
  
    std::vector<double> dvec;
  
    std::copy(
      std::istream_iterator<double>(ins),
      std::istream_iterator<double>(),
      std::back_inserter(dvec));
  
    return dvec;
    }
  

• But, I'd rather read points than coordinates.

  • You should program as close to the problem as possible.

Reading Puzzle Points

typedef std::pair<double, double> point;
typedef std::vector<point> point_vec;

std::istream &
operator >> (std::istream & is, point & p) {
  double f, s;
  if (is >> f >> s)
    p = std::make_pair(f, s);
  return is;
  }

point_vec
read_puzzle_pts(std::istream & ins) {

  point_vec pts;

  std::copy(
    std::istream_iterator<point>(ins),
    std::istream_iterator<point>(),
    std::back_inserter(pts));

  return pts;
  }

• This compiles on Forte CC, but not on g++.

Checking the Error Return

• When reading, any non-eof termination is an error.

point_vec
read_puzzle_pts(std::istream & ins) {

  point_vec pts;

  std::copy(
    std::istream_iterator<point>(ins),
    std::istream_iterator<point>(),
    std::back_inserter(pts));

  if (!ins.eof()) {
    std::cout << "Bad puzzle outline.\n";
    exit(EXIT_FAILURE);
    }

  return pts;
  }

Setting The Error State

• Points have two parts, so handling errors is a little tricky.

  • EOF isn't always acceptable.

  • Errors during the first read remain the same.

  • Errors during the second read are always fatal.

  std::istream &
  operator >> (std::istream & ins, point & p) {
  
    double f, s;
  
    if (ins >> f)
      if (ins >> s)
        p = std::make_pair(f, s);
      else
        ins.clear(std::ios::badbit);
  
    return ins;
    }
  

• Other error actions are possible, but more difficult.

  • Push-back's the problem.

Reading Puzzle Solutions

• Solutions are like puzzles, almost.

  • Solutions are line oriented, puzzles are not.

  bool read_tan(
    std::istream & ins, point_vec & tan) {
  
    std::string ln;
    if (!read_next_nonblank_line(ins, ln))
      return false;
  
    std::istringstream iss(ln);
  
    tan.clear();
  
    std::copy(
      std::istream_iterator<point>(iss),
      std::istream_iterator<point>(),
      std::back_inserter(tan));
  
    if (!ins.eof()) {
      std::cout << "Bad tan read.\n";
      exit(EXIT_FAILURE);
      }
  
    return true;
    }
  

Overwrite-Back Insert Iterators

• I want an iterator that either overwrites an old element or pushes back a new one.

  • Which one depends on where the iterator is in the container.
  

• This would be a overwrite-back insert iterator.

• With such an iterator I wouldn't have to clear tan.

  • Almost.

• How can I get such an iterator?

  • I have to write it.

The Overwrite-Back Insert Iterator Class

template<class Cont>

class overwrite_iterator :

public std::iterator<        // parent class
  std::output_iterator_tag,  // iterator kind
  typename Cont::value_type> // *i type
 {
  public:

    // To come.

  private:

    // The container involved.

       Cont & cont;		    

    // The actual iterator used.

       typename Cont::iterator iter;
  };

• The compiler needs typename to identify types.

Constructors

• There are two iterator-adaptor constructors.

  • Container only and container plus start iterator.

    overwrite_iterator<ctype> 
      oii1(c),
      oii2(c, ++c.begin());
    

• Store the container and starting iterator as private data.

  • Or make the starting iterator if necessary.

  explicit overwrite_iterator(Cont & x)
    : cont(x), iter(x.begin()) { }
  
  overwrite_iterator(
    Cont & x, typename Cont::iterator it)
    : cont(x), iter(it) { }
  

• The explicit cast constructor avoids accidental conversions.

  overwrite_iterator<point_vec> good, bad;
  point_vec pts;
  
  bad = pts;
  good = overwrite_iterator<point_vec>(pts);
  

Output Iterator Operators

• Output iterators support pre and post ++ and l-lvalue *.

  • But - ha ha! - these operators do nothing at all.

    overwrite_iterator & 
    operator * () { return *this; }
    
    overwrite_iterator & 
    operator ++ () { return *this; }
    
    overwrite_iterator & 
    operator ++ (int) { return *this; }
    

  • Where does all the work get done?

• Convert from an overwrite-back insert iterator to a container iterator.

  operator typename Cont::iterator () { 
    return iter; 
    }
  

The Assignment Operator

• The assignment operator is where all the work gets done.

  • Either assign or push-back the right-hand side.

  overwrite_iterator & 
  operator = (
    const typename Cont::value_type & val) {
  
    if (iter == cont.end()) {
      cont.push_back(val);
      iter = cont.end();
      }
    else
      *iter++ = val;
  
    return *this;
    }
  

• Is iteration invalidation handled correctly?

  • How about in

    if (iter == cont.end()) {
      cont.push_back(val);
      ++iter;
      }
    

Helper Functions

• Use template functions to simplify iterator construction.

  • Use

    overwriter(pts)
    

    instead of

    overwrite_iterator<
      std::vector<(point> >(pts);
    

• One for each constructor.

  template<class Cont>
  overwrite_iterator<Cont> 
  overwriter(Cont & x)  {
    return overwrite_iterator<Cont>(x);
    }
  
  template<class Cont>
  overwrite_iterator<Cont> 
  overwriter(
    Cont & x, typename Cont::iterator it) {
    return overwrite_iterator<Cont>(x, it);
    }
  

Using Overwrite Iterators

• We're done. How's it look?

  bool read_tan(
    std::istream & ins, point_vec & tan) {
  
    std::string ln;
    if (!read_next_nonblank_line(ins, ln))
      return false;
  
    std::istringstream iss(ln);
  
    std::copy(
      std::istream_iterator<point>(iss),
      std::istream_iterator<point>(),
      overwriter(tan));
  
    if (!ins.eof()) {
      std::cout << "Bad tan read.\n";
      exit(EXIT_FAILURE);
      }
    return true;
  

  • Cool, no tan.clear().

• But...

Shrink to Fit

• What happens if the original container has more elements than were read?

  • The extra elements are left over at the end.

• Use tan.erase() to remove the extra elements.

  point_vec::iterator e = std::copy(
    std::istream_iterator<point>(iss),
    std::istream_iterator<point>(),
    overwriter(tan));
  
  tan.erase(e, tan.end());
  

• Call clear() before, call erase() after - what's the difference?

  • Probably erase fewer elements than would be cleared.

  • Does it really matter?

Trust No One

• This lecture was based on an article I read.

  C/C++ Tip # 11: Overwrite Iterator by Ray Virzi in C/C++ User's Journal, December, 2002 (Vol. 20, No. 12)

• The article contained four errors.

  • The parent iterator template was wrong.

  • The types in a ? : expression were wrong.

  • There was an iterator invalidation problem.

Points to Remember

• Program in the problem domain.

  • Raise the level of your abstractions.

• If you need something helpful, make it.

  • And use it over and over again.

• Figure out if you've done well.

  • If not, don't be afraid to throw it away.

  • But don't throw it too far away.

• Trust no one.

  • Not even yourself (especially yourself).

This page last modified on 19 December 2002.