Length between iterators in size_type

Question

I am writing custom algorithm and at some point it needs to get distance between two iterators. If I assume that it1 < it2 I can get positive distance (it2 - it1) between them. This is okay, but std::distance and operator- returns difference_type that (in my case) is an alias to long long. What if the distance is too big to fit in long long but will fit inside unsigned long long (in my case its size_type alias)? For this example I also assume long long is int64_t and unsigned long long is uint64_t:

std::string container = ...; // assume enourmous number of characters, like 2^64 - 1024
std::cout << (container.begin() - container.end());

Since operator- returns difference_type, that cannot fit 2^64 - 1024 it should print negative number (in fact anything - it is UB) due to overflow. Of course I can cast it back to std::string::size_type but I can't be sure whether previous undefined behaviour worked as I assumed. How can I deal with such issue?

Answer 1

This will never be an issue. We know this because of max_size which is expressed in as a size_t. The return of max_size represents:

The maximum number of elements the string is able to hold due to system or library implementation limitations, i.e. ​std::distance(begin(), end())​ for the largest string

Thus iterators to a string separated by greater than size_t is not possible.

Answer 2

[..] What if the distance is too big to fit in [distance_type] but will fit inside [some other type] [..]

How can I deal with such issue?

You cannot. It's the job of whoever implemented the container as well as the corresponding iterator.

If the type they used for the distance cannot fit all values that could occur with the container then that's a bug in the container.

Clarification: difference_type actually depends on the iterators used.

Answer 3

A possible implementation on how I would have tackled the problem.

Let's leave it to the type-deduction system to make the right call.

Pre C++11 implementation -

template<typename It>
void distance_algo_impl(It const & begin, It const & end)
{
    typename std::iterator_traits<It>::difference_type distance
        = std::distance(begin, end);

    std::cout << "\ndistance :" << distance << "\n";
    // ... do your distance based algorithm here
}

template<typename T>
void distance_algo(T const & container)
{
    distance_algo_impl(container.begin(), container.end());
}

Post C++11 Implementation -

template<typename T>
void distance_algo(T const & container)
{
    auto distance = std::distance(container.begin(), container.end());
    std::cout << "\ndistance :" << distance << "\n";
    // ... do your distance based algorithm here
}