Overloading std::distance for a specific iterator type

[JohnW@Wessex]

I have a templated container that defines a forward iterator.

Calling std:istance on these iterators will generate code that will count the number of iterations it takes to get from the first parameter to the second, by repetitively incrementing.

Internally, the iterators can easily find the distance by a simple subtraction.

What I want to do is overload std:istance for these iterators so that it will take advantage of the simple calculation rather than repetitive increments.

The simple solution of course would be to make the iterators random access, but this would require that they support functionality that is not 'logical' for the container. Access to the container only makes logical sense when iterating one item at a time in the forward direction.

I haven't as yet discovered the correct syntax for this (and I'm beginning to think that it may not be possible).

#include <iterator>


template <typename T>
class Container
{
public:


  class iterator : public std::iterator<std::forward_iterator_tag, T>
  {
  public:


    friend long operator -(iterator lhs, iterator rhs)
    {
      return lhs.index - rhs.index;
    }


  private:
      
    size_t index;
  };
};


namespace std
{
  // This does not compile.

  template <typename T>
  long distance<T>(const typename Container<T>::iterator& begin,
                   const typename Container<T>::iterator& end)
  {
    return end - begin;
  }
}


int main()
{
  Container<int>::iterator ib;
  Container<int>::iterator ie;


  long d = std::distance(ib, ie); // Should call the specialised version.


  return 0;
}

[monarch_dodra]

The idea is not that you are supposed to *specialize* distance (which is a function, and partial specialization is illegal anyways). Rather, you are supposed to *overload* it, and the use Koenig lookup rules to let the compiler chose the "best" candidate.

Exactly like you'd do with swap. You don't specialize it, you overload it:

#include <iterator>


template <typename T>
class Container
{
public:


  class iterator : public std::iterator<std::forward_iterator_tag, T>
  {
  public:

    friend long operator -(iterator lhs, iterator rhs)
    {
      return lhs.index - rhs.index;
    }

    friend long distance(const iterator& begin,
                         const iterator& end)
    {
      return end.index - begin.index;
    }

  private:

    size_t index;
  };
};


int main()
{
  Container<int>::iterator ib;
  Container<int>::iterator ie;

  using std::distance;
  long d = distance(ib, ie); // calls the specialised version.


  return 0;
}

This works.

Unfortunately, just like swap, if the user an explicit "std::***(lhs, rhs)" directly, then you'll revert the default version.

I hope that helps.

[JohnW@Wessex]

Thanks, that makes sense.