CODEWITHSUNDEEP
c++stliterator-traitssgi
Edee
Edee

Reputation: 1826

How to understand the usage of this template in STL source code?

I am currently viewing the source code of SGI STL, specifically the algorithm of distance.

As I can see, to maximize the efficiency, SGI used a lot inline template to minimize the running time. But I do NOT really understand one thing.

For the algorithm distance, SGI define one template:

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&){
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

And then, it defined the public interface of the algorithm distance like

template <class Iterator>
inline iterator_traits<Iterator>::iterator_category
distance(InputIterator first, InputIterator last)
{
  typedef typename iterator_traits<InputIterator>::iterator_category category;
  return __distance(first, last, category());
}

Before you get all judgements on my knowledge, I want to say that I think understand the design pattern of STL and I understand the meaning of each line, I mean syntax.

But according to what I know, I just don't know why SGI did not implement algorithm distance like

template <class Iterator>
inline iterator_traits<Iterator>::iterator_category
distance(InputIterator first, InputIterator last)
{
  return __distance(first, last, iterator_category<InputIterator>(first));
}

Based on my knowledge, function call will consume certain amount of time, but here, iterator_category is inline function, which has the same effect like macro in most mainstream compilers.

The only shortage of using iterator_category() would potentially be the temporary object generated by compiler because of pass-by-const-reference.

Am I right? Or is there any genius design patter that I did not recognized yet, free to let me know!

Upvotes: 0

Views: 78

Answers (1)

Jarod42
Jarod42

Reputation: 217428

Using iterator_category<InputIterator>(first) in implementation might be hijacked with ADL for custom iterator.

namespace HiJack
{
class MyIter{/*..*/};

template <class T> // would be not templated with call like iterator_category(first)
auto iterator_category(const MyIer&){ /*..*/ }
}

You might think that is the same for __distance in __distance(first, last, category());, but names with __ are reserved and cannot be used by regular user.

But fully qualified the call would solve that (assuming namespace sgi):

template <class Iterator>
inline iterator_traits<Iterator>::iterator_category
distance(InputIterator first, InputIterator last)
{
  return __distance(first, last, ::sgi::iterator_category<InputIterator>(first));
}

Upvotes: 1

Related Questions