std::list sentinel node from standard point of view

Question

Code example:

    list<int> mylist{10, 20, 30, 40};
    auto p = mylist.end();
    while (true)
    {
        p++;
        if (p == mylist.end()) // skip sentinel
            continue;
        cout << *p << endl;
    }

I wonder, how much this code is legal from standard (C++17, n4810) point of view? I looking for bidirectional iterators requirements related to example above, but no luck.

My question is:

Ability to pass through end(), it is implementation details or it is standard requirements?

Answer 1

Quoting from the latest draft available online. [iterator.requirements.general]/7

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding sequence. These values are called past-the-end values. Values of an iterator i for which the expression *i is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable.

I believe that this applies not just to the end() but what comes after that as well. Note that the standard does not clearly state that end() should never be dereferenced.

And Cpp17Iterator requirements table states that for expression *r, r should be dereferenceable:

past-the-end iterator is considered a non-incrementable iterator and incrementing it (as you are doing at the beginning of the while loop) results in undefined behavior.

Something like what you are trying to do can also happen when using std::advance.

The book "The C++ Standard Library: A Tutorial and Reference" by Nicolai Josuttis has this quote:

Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined.

Answer 2

You code is illegal. You first initialized p to be the past-the-end iterator.

auto p = mylist.end();

Now you p++. Per Table 76, the operational semantics of r++ is:

{ X tmp = r;
++r;
return tmp; }

And per [Table 74], ++r

Expects: r is dereferenceable.

And per [iterator.requirements.general]/7,

The library never assumes that past-the-end values are dereferenceable.

In other words, incrementing a past-the-end iterator as you did is undefined behavior.