Why std::distance and std::advance?

Why use STL advance and distance given in <iterator> rather than hand crafting that code? The simple answers are:

• Why hand craft it when its already given to you?
• It can be more bug free than an average programmer's code.
• Why get into the nitty-gritties? You may rather want to concentrate on the problem at hand.

If all these aren't reason enough for you, here is the clincher: EFFICIENCY!

Let's look at each of them one by one.

std::distance()

Let's assume you are writing a generic function that takes in two iterators as the parameter and works on the range between them. If you are a beginner, your function would look something like this:

template <typename Iterator> foo(Iterator begin_, Iteraror end_)
{
      size_t dist = 0;

      while(begin_ !=   end_)
      {
            ++dist;
            ++begin_;
      }

      //Use dist in the rest of the code
      ...............
}

The time complexity of such an operation is O(n) for all categories of iterators passed to you.

If you are an advanced programmer and want to make a decision based on the iterator category, you will have to write helper functions overloaded on the different iterator categories and do a random access subtraction between the two iterators if it is a random access iterator. If not, you will iterate linearly through the range until the end. Something like...

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, random_access_iterator_tag)
{
        return end_ - begin_;
}

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, bidirectional_iterator_tag)
{
        typename iterator_traits<Iterator>::difference_type dist = 0;
        while(begin_ != end_)
        {
                ++begin_;
                ++dist;
        }

        return dist;
}


template <typename Iterator>
typename iterator_traits<Iterator>::difference_type mydistance(Iterator begin_, Iterator end_)
{

        return  __mydistance(begin_, end_, iterator_traits<Iterator>::iterator_category);

}


If your code looks something like the above, this is what std::distance gives you already.

If you go down to where the function is defined:
/usr/include/c++/4.4.2/bits/stl_iterator_base_funcs.h

It looks as follows:


template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last)
    {
      // concept requirements -- taken care of in __distance
      return std::__distance(__first, __last,
                             std::__iterator_category(__first));
    }
If you observe, it calls std::__distance, a function for internal use, and passes the iterator category as the last parameter. This is called tagged dispatch. If you scroll around that file, you will notice multiple overloaded  __distance functions for different iterator categories.


The __distance function accepting random_access_iterator_tag is implemented as:
return __last - __first;

The __distance function accepting input_iterator_tag is implemented as:
      while (__first != __last)
        {
          ++__first;
          ++__n;
        }
      return __n;