Lecture Notes for SE 598, Data Structures and Algorithms

7 June 2000, Introduction to Iterators

1. iterators - analogous to pointers

   1. references to values in a sequence

   2. the unary * operator follows an iterator to its value

2. iterator types

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

   2. each type adds operators to the previous type

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

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

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

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

   1. all the operators for both read and write iterators

      1. *itr = *itr + 1; is correct for a forward iterator

6. bidirectional iterators

   1. all the operations for forward iterators

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

7. random iterators

   1. all the operators for bidirectional iterators

   2. iterator-integer addition and subtraction

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

8. the iterator hierarchy

   1. 

   2. why not just make all iterators random

      1. principle of least privilege

      2. not all containers can support all iterator operations efficiently

9. generic functions - now it can be told

   1. template <class InputIterator, class T>
      InputIterator find(InputIterator first, InputIterator last, const T & value)
      

   2. template <class ForwardIterator1, class ForwardIterator2>
      ForwardIterator1 search(ForwardIterator1 start1, ForwardIterator1 end1,
                              ForwardIterator2 start2, ForwardIterator2 end2)
      

10. iterator ranges - (start, end),

    1. the end iterator refers to the value just past the end of the range

       1. standard C-C++ pointer practice

       2. 

       3. the end iterator may point to a non-existent element

    2. only sensible if start and end refers to values within the same container

11. from where do iterators come

    1. each container class defines its own iterator type

       1. vector<T>::iterator

       2. vector<T>::const_iterator

       3. there are others

    2. each container class has member functions that return iterators

       1. begin() - return an iterator to the first element in a container

          1. what does this do

             vector<int> ivec;
             vector<int>::iterator start = ivec.begin();
             

       2. end() - return an iterator to the last element in a container

       3. vector<int>::iterator five = find(ivec.start(), ivec.end(), 5);

       4. there are others

This page last modified on 7 June 2000.