Search code examples
c++iteratorc++17c++20stdlist

Why a second call of std::distance gives different results with std::list?


I met a strange behavior with std::distance(). It doesn't give the expected result, or I am not understanding it correctly. The standard doesn't give too much detail on this: https://en.cppreference.com/w/cpp/iterator/distance

Here is an example code, or run online:

#include <iostream>
#include <iterator>
#include <list>
 
int main() 
{
    std::list<int> v{1, 2, 1};
    
    auto it1 = v.begin();   // points to 1
    auto it2 = std::next(it1); // points to 2
    std::cout<<std::distance(it2, it1)<<std::endl;
    std::cout<<*it2<<std::endl;
    std::cout<<std::distance(it2, it1)<<std::endl;
}

If it is compiled with C++17, the output is:

1
2
3

But I expect it to be this instead:

-1
2
-1

So, why is std::distance() not giving negative values, and why is the second call of std::distance() giving a different result?


Solution

  • The 2 key details that explain the issue are:

    1. Cases where the behavior is undefined (from std::distance documentation):

    If InputIt is not LegacyRandomAccessIterator, the behavior is undefined if last is not reachable from first.

    (emphasis is mine)

    1. Regarding being reachable (from Iterator library documentation):

    An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j

    In your case a std::list iterator is not a random access one. And also no matter how many times you apply ++it2, you will never get to it1 which is before it in the list (i.e. it1 is not reachable from it2).

    Therefore the behavior is undefined. This means there is no guarantee whatsoever what the program will do.


    A side note:
    If you change v to be a std::vector, you will get the output you expect (see demo).
    This is because in this case the iterators will be random access ones and the documentation states that:

    If InputIt is LegacyRandomAccessIterator, the behavior is undefined if first and last are neither reachable from each other.

    I.e. in this case it is enough that it2 is reachable from it1, to avoid undefined behavior.