## Working with the STL iterators

Almost every programmer some how gets involved with STL iterators while programming. I’m quite fond of these concepts. So what exactly is an iterator?

STL stands for the *Standard Template Library* which has different flavors or implementations floating around with different compilers but the concept and structure behind all of them is the same. It’s a bunch of c++ classes which makes the life of programmer’s easy by providing implementations for popular data structure algorithms like…

- Singly/doubly linked lists
- Stack
- Queue
- DQueue
- Vector – used by almost everyone
- Map
- Hashed maps
- And others

So our point of discussion is what the heck does an iterator do and what is it for? Well as the name suggests it’s a way to traverse a list of items which can be ordered or unordered, in a generic fashion. Let’s see some examples of iterators…

typedef std::vector<int> IntVector; // Represents a dynamic list of integers IntVector Ints; Ints.push_back( 10 ); // Add one int Ints.push_back( 20 ); // Add one more int

Now we have a vector of integers with two ints. So to get first integer in this list we use following function…

IntVector::iterator Itr = Ints.begin(); // First int

And to get to next integer we simply use ++Itr/Itr++. Every STL container has it’s own flavor of ++(pre and post) operator. For e.g. for a list it will be moving to next element, for an output stream iterator it will be moving to next field in a file etc. So by now you might have understood how powerful the concept of an iterator is. In STL for traversing a container according to standard we must always use an iterator.

Note that it’s not correct to directly do a ‘+1’ or ‘-1’ with an iterator. It’s dangerous when container for an iterator changes. It’s quite ok with a *vector* (only if the iterator is a pointer) but a big disaster with *lists*. So for this purpose STL provides us with two functions *std::advance* and *std::distance*. As you might have understood by now std::advance advances an iterator by a count and *std::distance* returns the number of elements between two iterators. This will work with both ordered and unordered containers. So a poor alternative to *Ints.size()* will be *std::distance(Ints.begin(), Ints.end())* ;). To increment our previous *Itr* by one we’ll do *std::advance(Itr, 1) *instead of *Itr + 1*. Also never check for *NULL *on an iterator, always check against corresponding container’s *end()* function since this is what represents an invalid case in STL containers.

If you’ve noticed a detail of iterators, it’s that they are very generic. For e.g. our previous *Itr* object represents an iterator for a *std::vector* but even if we change the container type to *std::list* still there won’t be any change in iterator part. That’s cool isn’t. I enjoy programming in STL these days. I’m trying to get into the details of this wonderful library. Will keep posting *bits and bytes* on whatever I find in this library.

## Using std transform function

So what does *std::transform* function do?

“Applies a specified function object to each element in a source range or to a pair of elements from two source ranges and copies the return values of the function object into a destination range.”

Some general applications of using transform is as follows…

- For doing some kind of operation on two vectors of same type and storing the result in a third
*vector*. - For doing some kind of in place operations on a vector.

So simplified prototypes of this function…

template<class InputIterator, class OutputIterator, class UnaryFunction> OutputIterator transform( InputIterator _First1, InputIterator _Last1, OutputIterator _Result, UnaryFunction _Func ); template</class><class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction> OutputIterator transform( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, OutputIterator _Result, BinaryFunction _Func );

So first prototype can take two different vectors or can be the same vector for inplace modification,while second one takes three, two source vectors (for e.g. two *vector* of *int*s and we add these two vectors and place the result in a third vector).

The applications of this function is powerful! Here are some demos

// Starts here int _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) { void Demo_Std_TransformInplace(); Demo_Std_TransformInplace(); void Demo_Std_Transform_Binary(); Demo_Std_Transform_Binary(); return 0; } #include <vector> // for std::vector #include <algorithm> // for std::transform // Callbacks used with std::transform, can also be functors but for ease of calling // // Unary operations. Note that I am alternating 'class' and 'typename' keywords just // to prevent code formatting errors in HTML. template<class T> T Square( const T Elem ) { return Elem * Elem; } template<typename T> T ReverseSign( const T Elem ) { return -Elem; } template<class T> T IncrementBy1( const T Elem ) { return Elem + 1; } template<typename T> T DecrementBy1( const T Elem ) { return Elem - 1; } // Binary operations template<class T> T Add( const T Elem1, const T Elem2 ) { return Elem1 + Elem2; } template<typename T> T Multiply( const T Elem1, const T Elem2 ) { return Elem1 * Elem2; } template<class T> T Divide( const T Elem1, const T Elem2 ) { return Elem1 / Elem2; } template<typename T> T Substract( const T Elem1, const T Elem2 ) { return Elem1 - Elem2; } // A typedef for ease of use typedef double VectorType; // Change this type and see the result typedef std::vector<vectortype> VTVector; // Vector typedef const VTVector::size_type Size = 1000; // Default size, increase to test performance // Randomly fills in a vector void FillInIntVector( VTVector& Vec ) { for( VTVector::size_type Index = 0; Index < Vec.size(); ++Index ) { Vec[Index] = static_cast<VectorType>( rand() ); } } // Functions for testing std::transform, Debug through and see the results // void Demo_Std_TransformInplace() { VTVector VTObj( Size ); FillInIntVector( VTObj ); // Do some in place operations std::transform( VTObj.begin(), VTObj.end(), VTObj.begin(), Square</vectortype><vectortype> ); std::transform( VTObj.begin(), VTObj.end(), VTObj.begin(), ReverseSign</vectortype><vectortype> ); std::transform( VTObj.begin(), VTObj.end(), VTObj.begin(), IncrementBy1</vectortype><vectortype> ); std::transform( VTObj.begin(), VTObj.end(), VTObj.begin(), DecrementBy1</vectortype><vectortype> ); } void Demo_Std_Transform_Binary() { // Randomly fill in first vector VTVector VTObj1( Size ); FillInIntVector( VTObj1 ); // Randomly fill in second vector VTVector VTObj2( Size ); FillInIntVector( VTObj2 ); // Added result will be placed in here VTVector Result( Size ); // Add "VTObj1" and "VTObj2" vector place the result in "Result" std::transform( VTObj1.begin(), VTObj1.end(), VTObj2.begin(), Result.begin(), Add</vectortype><vectortype> ); std::transform( VTObj1.begin(), VTObj1.end(), VTObj2.begin(), Result.begin(), Multiply</vectortype><vectortype> ); std::transform( VTObj1.begin(), VTObj1.end(), VTObj2.begin(), Result.begin(), Divide</vectortype><vectortype> ); std::transform( VTObj1.begin(), VTObj1.end(), VTObj2.begin(), Result.begin(), Substract</vectortype><vectortype> ); }

## How to convert iterator to corresponding data pointer?

Well it was quite easy in VC6 to work with iterators since iterators were actual pointers to internal data, so they could be used interchangeably.

For e.g.

typedef std::vector<int> IntVector; IntVector IntVecObj; // Push in a thousand ints for( int Index = 0; Index < 1000; ++Index ) { IntVecObj.push_back( Index + 1 ); } // Access internal pointer int *p = IntVecObj.begin();[/sourcecode] But above code gives error if compiled in VC8! Says cannot convert from vector::iterator type to int*. Mmm, so how can we get the internal pointer? This is what I've done... [sourcecode language="cpp"]// Following code snippet won't compile in VC6 hence the compilation guard #if _MSC_VER >= 1400 // VC8 onwards int* p = &(*IntVecObj.begin()); // Or // int* p = IntVecObj.begin()._Myptr; ++*p; #endif

You may ask why I had to take this approach? I am currently migrating a project from VC6 to VC8 hence plenty of code which directly uses pointers as iterators and iterators as pointers, so this helps. 🙂

I’ve got to say it’s a pain to work with new version of these stl classes, of course it could all turn out for good, sigh! anyway 😦