Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does the standard require only input iterators for std::distance, rather than forward iterators?

I was perplexed to see that the template parameter requirement for std::distance is a LegacyInputIterator rather than a LegacyForwardIterator.

Since input-only iterators don't have the multi-pass guarantee, the idea of "distance" between them doesn't have a reliable or useful meaning.

So the following code has meaning (even if it'a a little inefficient):

#include<iostream>
#include <list>

int main()
{
    std::list <int> l{1, 2, 3, 4, 5};

    std::cout << std::distance(l.begin(), l.end()) << '\n';
    return 0;
}

But the following code does not:

#include<iostream>

int main()
{
    auto z = std::istreambuf_iterator<char>(std::cin.rdbuf());
    auto e = std::istreambuf_iterator<char>();
    std::cout << std::distance(z, e) << '\n';
}

std::distance may have counted the chars fed to it, but by the definition of istreambuf_iterator, those chars are gone, never to return.

This should be ill-formed or at least undefined behavior, but it is not.

(Rather than std::cin, I might open a file stream to a named pipe, which only gives me "sips" out of the firehose of data.)

Is there any committee-member discussion or proposal language for putting std::distance into the Standard that explains the choice of requirement?

like image 307
Spencer Avatar asked Sep 01 '25 23:09

Spencer


1 Answers

You should not treat argument types as requirements on the input. They are more about what function requires itself. In other words, if you see signature like:

void func(const std::string& x);

you do not think, that this function requires constant string. You think that whatever the function does, it will need to apply only reading operation on its argument.

Similarly here. The difference between, LegacyInputIterator and LegacyForwardIterator is that the later supports multi pass algorithms. But you do not need it in order to calculate distance. It is a single pass algorithm.

If you put LegacyForwardIterator as an input parameter for std::distance you will disallow LegacyInputIterators as an input. Indeed it does not make a lot of senses to support such functionality, but it is there for free. And who knows, maybe somewhere there is a use case for that

like image 154
Bohdan Lakatosh Avatar answered Sep 03 '25 12:09

Bohdan Lakatosh