C++ input iterator (thing)

Input Iterators

In the C++ Standard Template Library, iterators are a generalization of C's pointers. An input iterator is an iterator that supports the minimum operations necessary to get input:

• you're allowed to dereference them (so you can read data)
• you're allowed to increment them (so you can get to the next datapoint).

Notice that this means you're not allowed to do things like write to an input iterator (if you want to do that, you should be using an output iterator of some sort...) In many cases, this is all right. A simple example is if you're reading a set of ints from standard input:

vector<int> V;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(V));

In this tiny code snippet, we create a vector of ints where we're going to store the values we read in. The copy function copies from a range defined by a pair of input iterators to an output iterator. The back_inserter function creates an output iterator that writes values to the end of the supplied vector whenever it's written to.

The nice thing about these abstractions is that you can implement algorithms that can run on certain sorts of streams, before you know how the input stream is going to work. Not only that, but you can easily substitute one iterator for another one that acts the same way. Compare, for example, the following iterators:

• an iterator that's reading a sound sample from a microphone
• an iterator that's generating a sound sample by modelling a sine wave
• an iterator that's decoding a sound sample from an mp3 file

Why should you, as a programmer, care about where the sound sample is coming from? If you're programming in the way STL encourages, playing a sound from any of these sources can be done from the same function.

Using an input iterator

I hate it when people try to describe a concept in programming without giving a concrete example. So, in the following example, I'll show a program to encode or decode a message using a vigenere square, given the key. (If you don't have the key, then you'll probably want to look into breaking the vigenere square.) The way I've written it below, it only works with lowercase characters (it skips everything else) but by using the appropriate template instantiation, it'll work on any values.

#include <vector>
#include <iterator>
#include <iostream>
#include <string>
#include <cctype>   

using namespace std;

template <class T=unsigned char, T low_value='a', T high_value='z'>
class CodeWheel : public iterator<input_iterator_tag, T> {
  // a CodeWheel is an iterator that takes a message iterator and a
  // key vector, and encodes the message pointed to by the message
  // iterator using a vigenere cipher.
  //
  // the type T must be a numerical type.
  private:
    typedef typename vector<T>::iterator T_vector_iterator; 
    T_vector_iterator message_;
    vector<T> key_;
    T_vector_iterator key_iter_;

  public:    
    CodeWheel(T_vector_iterator message, vector<T> key) :
      message_(message), key_(key),
      key_iter_(key_.begin()) {}

    CodeWheel& operator++() { 
      message_++; 
      key_iter_++; 
      if (key_iter_ == key_.end())
        key_iter_ = key_.begin();
      return *this; 
    }

    CodeWheel operator++(int) {
      CodeWheel ret_val(*this);
      message_++;
      key_iter_++; 
      if (key_iter_ == key_.end())
        key_iter_ = key_.begin();
      return ret_val;
    }

    // This is where all the interesting work happens.  Note that since
    // this is an input iterator, it's returning const T (so we can't
    // change the value of what we return.)
    const T operator*() { 
      if (low_value <= (*message_) && (*message_) <= high_value) {
        T rotated_value = *message_ + *key_iter_ - (low_value-1);
	if (rotated_value > high_value) 
          return rotated_value - (high_value-low_value+1);
	else 
          return rotated_value;
      } else
        return (*message_);
    }

    bool operator==(const CodeWheel& x) {
      return x.message_ == message_;
    }
    
    bool operator!=(const CodeWheel& x) {
      return x.message_ != message_;
    }
};

int main(int argc, char *argv[]) {
  if (argc < 2) {
    cerr << "Usage: " << argv[0] << " key [decode]" << endl
         << "Encodes stdin as a vigenere cipher with the appropriate key." 
         << endl
         << "If the second argument exists, decode, otherwise, encode."
         << endl;
    return 1;
  }
 
  string key_string = string(argv[1]);
  vector<unsigned char> key_vector;
  for (string::const_iterator i = key_string.begin(); 
       i != key_string.end(); 
       i++) {
    if (argc == 2) { // encode
      key_vector.push_back(static_cast<unsigned char>(*i));
    } else { // decode
      // if (*i) is the nth letter of the alphabet, then (*i) - 'a' + 1
      // is equal to n.  In order to reverse the shift of the nth letter
      // (thereby decoding it), we need to subtract n from 'z'.
      key_vector.push_back(static_cast<unsigned char>('z' - ((*i) - 'a' + 1)));
    }
  } 
  
  // read in message
  vector<unsigned char> message;
  unsigned char c;
  while (cin.get(static_cast<char>(c)))
    message.push_back(tolower(c));

  // output decoded message:
  for (CodeWheel<> i = CodeWheel<>(message.begin(), key_vector); 
       i != CodeWheel<>(message.end(), key_vector);
       i++)
    cout << (*i);

  return 0;
}

---

References: http://www.sgi.com/tech/stl - the sgi stl reference