Feb 032009

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…

  1. Singly/doubly linked lists
  2. Stack
  3. Queue
  4. DQueue
  5. Vector – used by almost everyone
  6. Map
  7. Hashed maps
  8. 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.

Jul 302008

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…

  1. For doing some kind of operation on two vectors of same type and storing the result in a third vector.
  2. 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 ints 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();

   void 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&#91;Index&#93; = 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> );

Jul 252008

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();&#91;/sourcecode&#93;

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...

&#91;sourcecode language="cpp"&#93;// 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;

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 🙁