Introduction
The purpose of this article is to demonstrate the basic concepts of template programming (such as: tags and traits classes). In this article, I will implement some functionality of the "distance" STL function. By dealing with the various problems emerging, the basic concepts can become clearer.
Background
Iterator is an object allowing one to sequence through all of the elements contained in another object.
Iterators are central to generic programming because they are an interface between containers and algorithms: algorithms typically take iterators as arguments, so a container need only provide a way to access its elements using iterators. This makes it possible to write a generic algorithm that operates on many different kinds of containers (more information available in the STL documentation).
Given two iterators on the same container, we wish to create a generic function that returns the number of elements between them, or the distance between them. Without the demand that it will be performed in the fastest way possible, this sounds simple. By saying "in the fastest way possible", I mean that if this is a Random Access Iterator, it will be done in a constant running time, and if it is only a Forward Iterator, it will be done in a linear running time (more information available in the STL documentation).
Details
Without any knowledge in generic programming, the basic implementation should look something like this:
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd)
{
int dist = 0;
if( isRandomAccessIterator(itBegin) )
{
return itEnd - itBegin;
}
else
{
while( itBegin!=itEnd ) { ++itBegin; ++dist; }
}
}
There are several problems with this code:
- How do we implement the
isRandomAccessIterator? This function checks whether this is a random access iterator or a forward access iterator.
- This example will never compile with forward iterators. The reason is that we use the minus operator for random access iterators, and forward iterators don't have this operator (the fact that the code is not executed in the forward iterator case does not matter).
- We prefer that the decision of which code should run (flow control), the minus or the
while loop, will be accepted at compile-time. This will make the code run faster, and because of (2) we have no real choice.
All of these problems have solutions:
Tags
Well, we won't exactly implement the isRandomAccessIterator method. The main reason is that, from definition, functions return values at run-time and we want flow control at compile-time. Instead, we will use tags to identify the category of the iterator.
Tags are empty structs that are used to identify types and properties of types at compile-time. Here are the tag definitions for forward access and random access iterator categories (taken from STL), and an example of how we define the category of MyIterator to be random access:
struct forward_iterator_tag
: public input_iterator_tag
{
};
struct bidirectional_iterator_tag
: public forward_iterator_tag
{
};
struct random_access_iterator_tag
: public bidirectional_iterator_tag
{
};
class MyIterator
{
typedef random_access_iterator_tag iterator_category;
}
random_access_iterator_tag inherits from bidirectional_iterator_tag because a random access iterator is also a bidirectional iterator. Every iterator in STL has an iterator_category type defined in its class declaration as in MyIterator (this is not exactly true - read on). The answer for how we use tags to get compile-time flow control is available in the next section.
Function overloading
If tags are "attributes" used to identify certain properties of certain types, function overloading is the tool we use to control the flow, given those attributes (tags). Function overloading is our if/switch statements in compile-time.
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd,
forward_iterator_tag tag)
{
cout << "Forward iterator" << endl;
int dist=0;
while( itBegin!=itEnd ) { ++itBegin; ++dist; }
return dist;
}
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd,
random_access_iterator_tag tag)
{
cout << "Random access iterator" << endl;
return itEnd - itBegin;
}
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd)
{
typedef typename Iterator::iterator_category
iterator_category;
return my_distance(itBegin, itEnd,
iterator_category());
}
On the my_distance function, we simply instantiate the iterator_category (empty struct) of the given iterator, and send it to another function (the typename keyword is needed so that the compiler will know that iterator_category is a type in the typedef). Because every iterator contains its correct iterator_category, the compiler chooses the right overloaded function (the one that expects random_access_iterator_tag or the one that expects forward_iterator_tag). In compile-time, we've succeeded to run the code depending on iterator_category!
There is one big problem with the code above. If you try to use it with vector<int>::iterator then you'll get a compile error. The reason is that vector<int>::iterator is really int*, and int* does not have an iterator_category type and it is not even a class. The solution to this problem is using the traits class.
Traits classes
Traits classes allow us to associate tags (and also constants and other attributes) with types that aren�t classes and to classes that aren�t ours. For STL iterators, there is a traits class called iterator_traits. Its default behavior is to obtain the tags (and const fields) from the templated class:
template<class Iterator>
struct iterator_traits
{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
};
template<typename T>
struct iterator_traits<T *>
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
};
We use partial specialization to define different tags for pointer types. We can use specialization to associate tags to classes that we can�t modify and therefore can�t add tags to (we just need to specialize the traits class for that specific class).
Now our code will look something like this:
int my_distance(Iterator itBegin, Iterator itEnd)
{
typedef typename
iterator_traits<Iterator>::iterator_category
iterator_category;
return my_distance(itBegin, itEnd, iterator_category());
}
Conclusion
Tags are a very strong tool. They can be used with function overloading to create compile-time flow control.
Using trait classes can make the code more usable and adaptable.
