c++algorithmtemplatesiteratordependent-name

What does "typename iterator_traits<InputIt>::difference_type" mean?


This is the example-implementation of the count algorithm from https://devdocs.io/cpp/algorithm/count_if:

template<class InputIt, class T>
typename iterator_traits<InputIt>::difference_type
    count(InputIt first, InputIt last, const T& value)
{
    typename iterator_traits<InputIt>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (*first == value) {
            ret++;
        }
    }
    return ret;
}

My question is, what is the significance of typename iterator_traits<InputIt>::difference_type?
If I were implementing this, I would have simply used unsigned int to keep track of the count.


Solution

  • Well, you cannot know the best sufficiently-large type the difference between two iterators without knowing anything about the iterators.
    As an example, what if the iterator iterates the bytes in a file:
    The filesize is 64bit, but we are in a 32bit process. std::size_t won't work, likely unsigned won't either.

    Thus, ask std::iterator_traits to generically provide a suitable type.

    Now, we have to use typename there to assure the compiler that the dependent qualified name std::iterator_traits<InputIt>::difference_type will be a type. That is important to clarify for 2-phase lookup.