MFC Programmer's SourceBook : Thinking in C++

A plethora of iterators

As mentioned earlier, the iterator is the abstraction that allows a piece of code to be generic, and to work with different types of containers without knowing the underlying structure of those containers. Every container produces iterators. You must always be able to say:

ContainerType::iterator
ContainerType::const_iterator

to produce the types of the iterators produced by that container. Every container has a begin( ) method that produces an iterator indicating the beginning of the elements in the container, and an end( ) method that produces an iterator which is the as the past-the-end value of the container. If the container is const¸ begin( ) and end( ) produce const iterators.

Every iterator can be moved forward to the next element using the operator++ (an iterator may be able to do more than this, as you shall see, but it must at least support forward movement with operator++).

The basic iterator is only guaranteed to be able to perform == and != comparisons. Thus, to move an iterator it forward without running it off the end you say something like:

while(it != pastEnd) {
  // Do something
  it++;
}

Where pastEnd is the past-the-end value produced by the container’s end( ) member function.

An iterator can be used to produce the element that it is currently selecting within a container by dereferencing the iterator. This can take two forms. If it is an iterator and f( ) is a member function of the objects held in the container that the iterator is pointing within, then you can say either:

(*it).f();

it->f();

Knowing this, you can create a template that works with any container. Here, the apply( ) function template calls a member function for every object in the container, using a pointer to member that is passed as an argument:

//: C20:Apply.cpp
// Using basic iterators
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

template<class Cont, class PtrMemFun>
void apply(Cont& c, PtrMemFun f) {
  typename Cont::iterator it = c.begin();
  while(it != c.end()) {
    (it->*f)(); // Compact form
    ((*it).*f)(); // Alternate form
    it++;
  }
}

class Z {
  int i;
public:
  Z(int ii) : i(ii) {}
  void g() { i++; }
  friend ostream& 
  operator<<(ostream& os, const Z& z) {
    return os << z.i;
  }
};

int main() {
  ostream_iterator<Z> out(cout, " ");
  vector<Z> vz;
  for(int i = 0; i < 10; i++)
    vz.push_back(Z(i));
  copy(vz.begin(), vz.end(), out);
  cout << endl;
  apply(vz, &Z::g);
  copy(vz.begin(), vz.end(), out);
} ///:~

Because operator-> is defined for STL iterators, it can be used for pointer-to-member dereferencing (in the following chapter you’ll learn a more elegant way to handle the problem of applying a member function or ordinary function to every object in a container).

Much of the time, this is all you need to know about iterators – that they are produced by begin( ) and end( ), and that you can use them to move through a container and select elements. Many of the problems that you solve, and the STL algorithms (covered in the next chapter) will allow you to just flail away with the basics of iterators. However, things can at times become more subtle, and in those cases you need to know more about iterators. The rest of this section gives you the details.

Iterators in reversible containers

All containers must produce the basic iterator. A container may also be reversible, which means that it can produce iterators that move backwards from the end, as well as the iterators that move forward from the beginning.

A reversible container has the methods rbegin( ) (to produce a reverse_iterator selecting the end) and rend( ) (to produce a reverse_iterator indicating “one past the beginning”). If the container is const then rbegin( ) and rend( ) will produce const_reverse_iterators.

All the basic sequence containers vector, deque and list are reversible containers. The following example uses vector, but will work with deque and list as well:

//: C20:Reversible.cpp
// Using reversible containers
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include "../require.h"
using namespace std;

int main() {
  ifstream in("Reversible.cpp");
  assure(in, "Reversible.cpp");
  string line;
  vector<string> lines;
  while(getline(in, line))
    lines.push_back(line);
  vector<string>::reverse_iterator r;
  for(r = lines.rbegin(); r != lines.rend(); r++)
    cout << *r << endl;
} ///:~

You move backward through the container using the same syntax as moving forward through a container with an ordinary iterator.

The associative containers set, multiset, map and multimap are also reversible. Using iterators with associative containers is a bit different, however, and will be delayed until those containers are more fully introduced.

Iterator categories

The iterators are classified into different “categories” which describe what they are capable of doing. The order in which they are generally described moves from the categories with the most restricted behavior to those with the most powerful behavior.

Input: read-only, one pass

The only predefined implementations of input iterators are istream_iterator and istreambuf_iterator, to read from an istream. As you can imagine, an input iterator can only be dereferenced once for each element that’s selected, just as you can only read a particular portion of an input stream once. They can only move forward. There is a special constructor to define the past-the-end value. In summary, you can dereference it for reading (once only for each value), and move it forward.

Output: write-only, one pass

This is the complement of an input iterator, but for writing rather than reading. The only predefined implementations of output iterators are ostream_iterator and ostreambuf_iterator, to write to an ostream, and the less-commonly-used raw_storage_iterator. Again, these can only be dereferenced once for each written value, and they can only move forward. There is no concept of a terminal past-the-end value for an output iterator. Summarizing, you can dereference it for writing (once only for each value) and move it forward.

Forward: multiple read/write

The forward iterator contains all the functionality of both the input iterator and the output iterator, plus you can dereference an iterator location multiple times, so you can read and write to a value multiple times. As the name implies, you can only move forward. There are no predefined iterators that are only forward iterators.

Bidirectional: operator--

The bidirectional iterator has all the functionality of the forward iterator, and in addition it can be moved backwards one location at a time using operator--.

Random-access: like a pointer

Finally, the random-access iterator has all the functionality of the bidirectional iterator plus all the functionality of a pointer (a pointer is a random-access iterator). Basically, anything you can do with a pointer you can do with a bidirectional iterator, including indexing with operator[ ] , adding integral values to a pointer to move it forward or backward by a number of locations, and comparing one iterator to another with <, >=, etc.

Is this really important?

Why do you care about this categorization? When you’re just using containers in a straightforward way (for example, just hand-coding all the operations you want to perform on the objects in the container) it usually doesn’t impact you too much. Things either work or they don’t. The iterator categories become important when:

You use some of the fancier built-in iterator types that will be demonstrated shortly. Or you graduate to creating your own iterators (this will also be demonstrated, later in this chapter).
You use the STL algorithms (the subject of the next chapter). Each of the algorithms have requirements that they place on the iterators that they work with. Knowledge of the iterator categories is even more important when you create your own reusable algorithm templates, because the iterator category that your algorithm requires determines how flexible the algorithm will be. If you only require the most primitive iterator category (input or output) then your algorithm will work with everything ( copy( ) is an example of this).

Predefined iterators

The STL has a predefined set of iterator classes that can be quite handy. For example, you’ve already seen reverse_iterator (produced by calling rbegin( ) and rend( ) for all the basic containers).

The insertion iterators are necessary because some of the STL algorithms – copy( ) for example – use the assignment operator= in order to place objects in the destination container. This is a problem when you’re using the algorithm to fill the container rather than to overwrite items that are already in the destination container. That is, when the space isn’t already there. What the insert iterators do is change the implementation of the operator= so that instead of doing an assignment, it calls a “push” or “insert” function for that container, thus causing it to allocate new space. The constructors for both back_insert_iterator and front_insert_iterator take a basic sequence container object ( vector, deque or list) as their argument and produce an iterator that calls push_back( ) or push_front( ), respectively, to perform assignment. The shorthand functions back_inserter( ) and front_inserter( ) produce the same objects with a little less typing. Since all the basic sequence containers support push_back( ), you will probably find yourself using back_inserter( ) with some regularity.

The insert_iterator allows you to insert elements in the middle of the sequence, again replacing the meaning of operator=, but this time with insert( ) instead of one of the “push” functions. The insert( ) member function requires an iterator indicating the place to insert before, so the insert_iterator requires this iterator addition to the container object. The shorthand function inserter( ) produces the same object.

The following example shows the use of the different types of inserters:

//: C20:Inserters.cpp
// Different types of iterator inserters
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <iterator>
using namespace std;

int a[] = { 1, 3, 5, 7, 11, 13, 17, 19, 23 };

template<class Cont>
void frontInsertion(Cont& ci) {
  copy(a, a + sizeof(a)/sizeof(int), 
    front_inserter(ci));
  copy(ci.begin(), ci.end(),
    ostream_iterator<int>(cout, " "));
  cout << endl;
}

template<class Cont>
void backInsertion(Cont& ci) {
  copy(a, a + sizeof(a)/sizeof(int), 
    back_inserter(ci));
  copy(ci.begin(), ci.end(),
    ostream_iterator<int>(cout, " "));
  cout << endl;
}

template<class Cont>
void midInsertion(Cont& ci) {
  typename Cont::iterator it = ci.begin();
  it++; it++; it++;
  copy(a, a + sizeof(a)/(sizeof(int) * 2),
    inserter(ci, it));
  copy(ci.begin(), ci.end(),
    ostream_iterator<int>(cout, " "));
  cout << endl;
}

int main() {
  deque<int> di;
  list<int>  li;
  vector<int> vi;
  // Can't use a front_inserter() with vector
  frontInsertion(di);
  frontInsertion(li);
  di.clear();
  li.clear();
  backInsertion(vi);
  backInsertion(di);
  backInsertion(li);
  midInsertion(vi);
  midInsertion(di);
  midInsertion(li);
} ///:~

Since vector does not support push_front( ), it cannot produce a front_insertion_iterator. However, you can see that vector does support the other two types of insertion (even though, as you shall see later, insert( ) is not a very efficient operation for vector).

IO stream iterators

You’ve already seen some use of the ostream_iterator (an output iterator) in conjuction with copy( ) to place the contents of a container on an output stream. There is a corresponding istream_iterator (an input iterator) which allows you to “iterate” a set of objects of a specified type from an input stream. An important difference between ostream_iterator and istream_iterator comes from the fact that an output stream doesn’t have any concept of an “end,” since you can always just keep writing more elements. However, an input stream eventually terminates (for example, when you reach the end of a file) so there needs to be a way to represent that. An istream_iterator has two constructors, one that takes an istream and produces the iterator you actually read from, and the other which is the default constructor and produces an object which is the past-the-end sentinel. In the following program this object is named end:

//: C20:StreamIt.cpp
// Iterators for istreams and ostreams
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include "../require.h"
using namespace std;

int main() {
  ifstream in("StreamIt.cpp");
  assure(in, "StreamIt.cpp");
  istream_iterator<string> init(in), end;
  ostream_iterator<string> out(cout, "\n");
  vector<string> vs;
  copy(init, end, back_inserter(vs));
  copy(vs.begin(), vs.end(), out);
  out = vs[0];
  out = "That's all, folks!";
} ///:~

When in runs out of input (in this case when the end of the file is reached) then init becomes equivalent to end and the copy( ) terminates.

Because out is an ostream_iterator<string>, you can simply assign any string object to it using operator= and it will put that string on the output stream, as seen in the two assignments to out. Because out is defined with a newline as its second argument, these assignments also cause a newline to be inserted along with each assignment.

While it is possible to create an istream_iterator<char> and ostream_iterator<char>, these actually parse the input and thus will for example automatically eat whitespace (spaces, tabs and newlines), which is not desirable if you want to manipulate an exact representation of an istream. Instead, you can use the special iterators istreambuf_iterator and ostreambuf_iterator, which are designed strictly to move characters [54]. Although these are templates, the only template arguments they will accept are either char or wchar_t (for wide characters). The following example allows you to compare the behavior of the stream iterators vs. the streambuf iterators:

//: C20:StreambufIterator.cpp
// istreambuf_iterator & ostreambuf_iterator
#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include "../require.h"
using namespace std;

int main() {
  ifstream in("StreambufIterator.cpp");
  assure(in, "StreambufIterator.cpp");
  // Exact representation of stream:
  istreambuf_iterator<char> isb(in), end;
  ostreambuf_iterator<char> osb(cout);
  while(isb != end)
    *osb++ = *isb++; // Copy 'in' to cout
  cout << endl;
  ifstream in2("StreambufIterator.cpp");
  // Strips white space:
  istream_iterator<char> is(in2), end2;
  ostream_iterator<char> os(cout);
  while(is != end2)
    *os++ = *is++;
  cout << endl;
} ///:~

The stream iterators use the parsing defined by istream::operator>>, which is probably not

what you want if you are parsing characters directly – it’s fairly rare that you would want all the whitespace stripped out of your character stream. You’ll virtually always want to use a streambuf iterator when using characters and streams, rather than a stream iterator. In addition, istream::operator>> adds significant overhead for each operation, so it is only appropriate for higher-level operations such as parsing floating-point numbers. [55]

Manipulating raw storage

This is a little more esoteric and is generally used in the implementation of other Standard Library functions, but it is nonetheless interesting. The raw_storage_iterator is defined in <algorithm> and is an output iterator. It is provided to enable algorithms to store their results into uninitialized memory. The interface is quite simple: the constructor takes an output iterator that is pointing to the raw memory (thus it is typically a pointer) and the operator= assigns an object into that raw memory. The template parameters are the type of the output iterator pointing to the raw storage, and the type of object that will be stored. Here’s an example which creates Noisy objects (you’ll be introduced to the Noisy class shortly; it’s not necessary to know its details for this example):

//: C20:RawStorageIterator.cpp
// Demonstrate the raw_storage_iterator
#include <iostream>
#include <iterator>
#include <algorithm>
#include "Noisy.h"
using namespace std;

int main() {
  const int quantity = 10;
  // Create raw storage and cast to desired type:
  Noisy* np = 
    (Noisy*)new char[quantity * sizeof(Noisy)];
  raw_storage_iterator<Noisy*, Noisy> rsi(np);
  for(int i = 0; i < quantity; i++)
    *rsi++ = Noisy(); // Place objects in storage
  cout << endl;
  copy(np, np + quantity,
    ostream_iterator<Noisy>(cout, " "));
  cout << endl;
  // Explicit destructor call for cleanup:
  for(int j = 0; j < quantity; j++)
    (&np[j])->~Noisy();
  // Release raw storage:
  delete (char*)np;
} ///:~

To make the raw_storage_iterator template happy, the raw storage must be of the same type as the objects you’re creating. That’s why the pointer from the new array of char is cast to a Noisy*. The assignment operator forces the objects into the raw storage using the copy-constructor. Note that the explicit destructor call must be made for proper cleanup, and this also allows the objects to be deleted one at a time during container manipulation.

[54] These were actually created to abstract the “locale” facets away from iostreams, so that locale facets could operate on any sequence of characters, not only iostreams. Locales allow iostreams to easily handle culturally-different formatting (such as representation of money), and are beyond the scope of this book.

[55] I am indebted to Nathan Myers for explaining this to me.

Contents | Prev | Next