Lecture Notes for CS 509, Advanced Programming II

30 October 2001, More on Iterators

  1. iterator types

    1. there are five types of iterators arranged in an hierarchy

    3. each type adds operators to the previous type

    4. all iterators respond to pre and post ++

      1. ++itr - advance the iterator itr to the next element and return the newly advanced iterator

      2. itr++ - remember the iterator itr, advance itr to the next element and return the old itr

    5. input iterators (read iterators)

      1. the equality operators == and != - tests if two iterators refer to the same value or two different values

        1. be careful - it's not a test of the values being referred to

      2. r-value *itr - return the value being referenced by the iterator itr

        1. 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

          1. i = *itr; is correct because * is being used to read itr

          2. *itr = i; is incorrect because * is being used to write itr

    6. output iterators (write iterators)

      1. l-value *itr - return the location being referenced by the iterator itr

        1. 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

          1. i = *itr; is incorrect because * is being used to read itr

          2. *itr = i; is correct because * is being used to write itr

    7. forward iterators (read-write iterators, or unidirectional iterators)

      1. all the operators for both read and write iterators and assignment

    8. bidirectional iterators

      1. all the operations for forward iterators

      2. pre and post -- - for moving the iterator back to the previous value

    9. random iterators

      1. all the operators for bidirectional iterators

      2. iterator-integer addition and subtraction

        1. x = *(itr + 5), x = itr[5]

      3. addition- and subtraction-assignment += and -= for jumping around

        1. itr += 5

      4. iterator-iterator subtraction for finding distances between iterators

        1. cnt = end_itr - start_itr - 1;

        2. just as with pointers, the two iterators being subtracted must be from the same container for the subtraction to be meaningful - but the compiler doesn't (can't) check to make sure

      5. the < operator - does one iterator refer to a value earlier in the sequence than another iterator

    10. the iterator hierarchy

      1. why not just make all iterators random

        1. principle of least privilege

        2. not all containers can support all iterator operations efficiently

  2. iterator adaptors - insert iterators

    1. the problem: copy(src.begin(), src.end(), dst.begin()); doesn't work - just iterators can't change container size

    2. the solution - insert iterators, behave like iterators, but can change container size

    3. they are template classes

      1. the template parameter is the container type

      2. the constructor argument is the container and possibly an iterator

      3. there are helper functions that make declarations easy

    4. three inserters - back inserter, front inserter, and general inserter

      1. back inserter - insert elements at container end

        1. class back_insert_iterator<typename T> bi(C)

        2. helper function back_inserter(c)

        3. when assigned to, calls C.push_back(V)

        4. C must support push_back()

      2. front inserter - insert elements at container front

        1. class front_insert_iterator<typename T> fi(C)

        2. helper function front_inserter(c)

        3. when assigned to, calls C.push_front(v)

        4. C must support push_front()

      3. front inserter - insert elements somewhere in the container

        1. class insert_iterator<typename T> ii(c, p)

        2. helper function inserter(c, p)

        3. when assigned to, calls C.insert(p, v)

        4. the inserter points to the new element when done

  3. iterator adaptors - input and output iterators

    1. i-o streams are like sequential containers - a sequence of values

    2. treat i-o streams like containers - iterator access in paritcular

    3. simplify and unify container i-o

    4. input and output iterators turn i-o strems into iterator accessable containers

    5. they are template classes

      1. the template parameter is the type of the value being read or written

      2. the constructor parameter is the stream involved

      3. helper functions aren't provided

    6. ostream iterators

      1. class ostream_iter<T> oi(ostream, delim)

      2. delim is optional, put between successive elements; it has type const char *

      3. example - copy(ivec.begin(), ivec.end(), ostream_iter<int>(cout, " "))

      4. the operator << must be defined for values of type T

    7. istream iterators

      1. like ostream interators, but there's the eof problem, and the error problem

      2. use the default constructor to return an eof indicator

      3. example - class istream_iter<T> ii_eof()

      4. class istream_iter<T> ii(istream)

      5. the next iterator after an eof or error is the eof iterator

      6. example - copy(istream_iter<int>(cin), istream_iter<int>(), back_inserter(ivec))

      7. the >> operator must be defined for the value being read

This page last modified on 1 November 2001.