about iterators

The advantages to an iterator--over say a simpler mechanism, like say a pointer--is that they can provide an interface for performing operations on the object they refer or can provide an interface for accessing other objects in the container.  

So for example an iterator might have a Delete() member function that cn be used to delete the object from the container/collection.  Or it might have an operator ++() member that can be used to access the next item in the container's sequence.

Another advantage of iterators, which actually depends in part on these advantages, is that they can be used to write generic algorithms for manipulating items in containers/collection that do not depend on the nature of the container/collection.  For example you could write a sort() algoprithm that sorts all the items in a container when passed an iterator to the container's elements.  That single sort algorithm may be able to sort containers that use greatly different implimentations, for storing the items, like say dynamic arrays or linked lists, because the iterators provide a consistent interface to the container's items.  for example the iterator's operator ++() (or something like it) could always be used to get from one item to the next, even though the process for doing so is greatly different depending on the container's implimentation.

continues

>> how does it work?
Very well.

:-)


It depends.  It depends on what sort of container/collection is being iterated and it depends on what sort of features are needed in the iterator and it depends on who wrote it.

But for exanple, in the STL a vector's iterator is often simply a pointer.  In the STL a pointer provides all the necessary interface to be an interator to a vector's items.   However a pointer does not work as an iterator to a STL list<>'s items.  So the iterator for a list<> will be a true object that contains a pointer to the node that the current item is stored in.  This pointer can then be used to access the node's data and use the pointers stored in the node to find the current item and also to find the next and previous items in the list.

Let me know if you have any questions.

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();

or

     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:

     //: C04: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:

     //: C04:Reversible.cpp
     // Using reversible containers
     #include "../require.h"
     #include <vector>
     #include <iostream>
     #include <fstream>
     #include <string>
     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 random-access 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:

   1.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).
   2.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 in 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:

     //: C04: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 conjunction 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:

     //: C04:StreamIt.cpp
     // Iterators for istreams and ostreams
     #include "../require.h"
     #include <iostream>
     #include <fstream>
     #include <vector>
     #include <string>
     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 the dereferenced iterator using operator= and that string will be
placed 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[17]. 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:

     //: C04:StreambufIterator.cpp
     // istreambuf_iterator & ostreambuf_iterator
     #include "../require.h"
     #include <iostream>
     #include <fstream>
     #include <iterator>
     #include <algorithm>
     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.[18]

Don't confuse iterators, which are a general concept, with STL iterators, which are a specific application of the concept.  Much of what you say applies ONLY to STL iterators and classes, not to iterators in general.