Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C++
Article

Into the STL distance function

Rate me:
Please Sign up or sign in to vote.
4.43/5 (18 votes)
21 Feb 20064 min read 43.6K   232   13   6
Learning basic generic programming concepts from the STL distance function.

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:

//
// The my_distance function returns
// the distance between two iterators in a container
//
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:

  1. How do we implement the isRandomAccessIterator? This function checks whether this is a random access iterator or a forward access iterator.
  2. 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).
  3. 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
{
// identifying tag for forward iterators
};

struct bidirectional_iterator_tag 
       : public forward_iterator_tag
{
// identifying tag for bidirectional iterators
};
 
struct random_access_iterator_tag 
       : public bidirectional_iterator_tag
{
// identifying tag for random-access iterators
};
 
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.

// function for forward iterator.
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;
}
 
// function for random access iterator.
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd, 
                random_access_iterator_tag tag)
{
        cout << "Random access iterator" << endl;
 
        return itEnd - itBegin;
}
 
// the general distance function
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:

// default iterator traits
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;
};

// partial specialization for pointers
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:

// the general distance function
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Israel Israel
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralTraits are not required for vector. Pin
Arvind Bharti22-Feb-06 14:17
Arvind Bharti22-Feb-06 14:17 
GeneralRe: Traits are not required for vector. Pin
ophir.setter22-Feb-06 21:25
ophir.setter22-Feb-06 21:25 
GeneralRe: Traits are not required for vector. Pin
Arvind Bharti24-Feb-06 15:47
Arvind Bharti24-Feb-06 15:47 
GeneralRe: Traits are not required for vector. Pin
ophir.setter24-Feb-06 20:08
ophir.setter24-Feb-06 20:08 
Question"int"!? Pin
SimonTrew17-Feb-06 5:24
SimonTrew17-Feb-06 5:24 
AnswerRe: &amp;quot;int&amp;quot;!? Pin
ophir.setter18-Feb-06 0:32
ophir.setter18-Feb-06 0:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.