The article on the new standard c++ library indicates that the standard library should include the STL. The STL was created at Hewlet Packard. It has become the standard for template container classes. As the article indicates, these classes depend heavily on iterators because they are packaged with generic algorithms such as copy, find and sort.
These generic algorithms were designed to be very efficient. The sort for example is a heap sort whose implementation is very complex. The copy and find algorithms are very easily understood and appear here. I have used these template functions along with modified versions of my array iterator, and a new class of iterator for input streams in the accompanying zipped file. My iterators are still very simple compared to those in the STL, but I tried to capture the essence of these classes. The functions shown here work with my classes.
template <class InputIterator, class ContainerIterator>
ContainerIterator copy(InputIterator first,InputIterator last, ContainerIterator result)
{
while (first != last)
*result++ = *first++;
return result;
}
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
}
These functions illustrate the heavy dependence on iterators found throughout the STL. In each function an iterator is created for the first item to be considered in the container and the last. Both iterators are associated with the same container class. In the STL iterator classes are defined as nested classes. This makes for complicated notation, but reduces the problems of access. To avoid a complete shift of paradigm for this simple introduction, I have just modified my iterators.
You should also have noticed by now that these functions will work on any properly defined iterator. This means they are not associated with any container class. Some of the functions needed are
template < class Type>
class ArrayIterator :public Iterator< Type>
{
public:
ArrayIterator(Array &t):array(t){init();}
void init(){_loc = 0;}
ArrayIterator< Type> operator ++(){ _loc++; return *this;}
ArrayIterator< Type> operator ++(int){ ArrayIterator< Type> tmp = *this; _loc++; return tmp;}
Type operator * ()const {return array[_loc];}
Type& operator *(){return array[_loc];}
Type operator ()()const{return array[_loc];}
Type& operator()(){return array[_loc];}
ArrayIterator< Type> operator = (ArrayIterator< Type> x){_loc = x._loc; return *this;}
int operator == (const ArrayIterator< Type> &i)const{return (array == i.array) && (_loc == i._loc);}
int operator != (const ArrayIterator< Type> &i)const{return (array != i.array) || (_loc != i._loc);}
int operator != (const Type &i)const {return i != array[_loc];}
int operator == (const Type &i)const {return i==array[_loc];}
int loc(){return _loc;} // Just used to demonstrate where items were found
ArrayIterator endOfArray(){ArrayIterator< Type> result(array); result._loc = array.numberInArray(); return result;}
void traverse(ArrayProcess< Type> *);//for simple traversal operations such as print
private:
Array &array;
int _loc;
};
The stream iterator proved to be a real challenge with the requirement that the default constructor create an end of stream marked file. I never did get that to work, so my != is faked here.
template <class Type>
class IstreamIterator :public Iterator< Type>
{
public:
IstreamIterator( istream &);
IstreamIterator(); //creates an end of stream marker
Type operator * ()const {return _val;}
Type& operator *(){return _val;}
IstreamIterator operator ++();
IstreamIterator operator ++(int);
Type operator ()();
int operator != (const IstreamIterator &test){return _eof != test._eof;}
operator int(){return !_in.eof();}
private:
Type _val;
istream &_in;
int _eof;
};
template <class Type>
IstreamIterator< Type>::IstreamIterator(istream &i)
:_in(i)
{
_in>>_val;
_eof = 0;
}
template <class Type>
IstreamIterator< Type>::IstreamIterator()
:_in(cin)
{
_eof = 1;
}
template <class Type>
IstreamIterator< Type> IstreamIterator< Type>::operator ++()
{
if (!_in.eof())
_in>>_val;
else
_eof = 1;
return *this;
}
template <class Type>
IstreamIterator< Type> IstreamIterator< Type>::operator ++(int)
{
IstreamIterator< Type> tmp = *this;
if (!_in.eof())
_in>>_val;
else
_eof = 1;
return tmp;
}
The reason for returning the iterator from the ++ operator is clear when you look at the find and copy functions. These functions require all iterators used with user defined containers to conform to the style used in the STL if the generic functions are used.
The copy function makes a copy of an existing structure into another structure starting at the first location in the iterator. In the first bit of code the copy function copies a file into an array starting after the first three items in the array.
ifstream i("temp.dat"); // initialize the input stream
IstreamIterator< string> iIter(i); // create the input stream iterator
Array< string> names; // create an array of strings - empty
ArrayIterator< string> next(names); // create an array iterator
IstreamIterator< string> eos; // create an end of file stream iterator
// insert three items into names using next directly
*next++ = "Big";
*next++ = "Little";
*next++ = "fifth";
// increment past the end of the array
copy(iIter, eos,next.endOfArray()); // append the file at the end of the array.
This section of code copies the array names into copy1.
Array< string> copy1; ArrayIterator< string> newList(copy1); next.init(); // This makes a true copy of names in copy1 changes // to copy1 farther down do not affect names or next. copy(next,next.endOfArray(),newList);
The following code segment creates the iterators with current location corresponding to the string "first" and "fifth" respectively. This allows us to find the location of the string "Little" between "first" and "fifth" where we will insert "Middle" in place of "Little".
newList.init(); // start at the beginning of the list ArrayIterator< string> first(copy1); ArrayIterator< string> last(copy1); first = find(newList,newList.endOfArray(),"first"); // mark the beginning of the search range last = find(newList,newList.endOfArray(),"fifth"); // mark the end of the search range, first occurence of "fifth" after "first" ArrayIterator< string> where(copy1); // create the iterator to mark the find location where = find(first,last,"Little"); // find "Little" between "first" and "fifth" where = "Middle"; // replace "Little" by "Middle"
For those of you who purchased Borland c++ 5.?, you will notice the headers algorith.h, iterator.h and vector.h. The first gives the definition of all of the generic algorithm functions. Iterator.h contains a generic defintion of iterator that acts as a pattern for user created iterators, and vector.h shows the implementation of a real array iterator in the STL. For a complete tutorial on the STL check out http://www.infosys.tuwien.ac.at/Research/Component/tutorial/main.htm. Home page for the STL http://www.cs.rpi.edu/~musser/stl.html The following link is a home page of development problems and sample code for STL. Get a zipped copy of the library by clicking here.