CODEWITHSUNDEEP
c++iteratoriterationlanguage-lawyerstdlist
Hi - I love SO
Hi - I love SO

Reputation: 635

Does --list.begin() == list.end()?

Does the standard guarantee that

--list.begin() == list.end()

always holds and that it infact is a valid operation? (list is an instance of std::list).

It appears to be the case with at least MSVC 2019.

This would be useful for instance in the following case:

for ( auto i = list.begin(); i != list.end(); ++i )
{
  ...
  list.erase(i--);
  ...
}

, i.e. when deleting elements while iterating, since i may be the beginning of the list. This would also require ++list.end() == list.begin() to hold; what about that?

Upvotes: 0

Views: 766

Answers (2)

eerorika
eerorika

Reputation: 238351

Does the standard guarantee that

--list.begin() == list.end()

No, standard does not guarantee that for std::list (nor can such guarantee be assumed given a bidirectional iterator). In fact, the behaviour of --list.begin() is undefined.

This would also require ++list.end() == list.begin() to hold; what about that?

Also not guaranteed, and ++list.end() has undefined behaviour.

Standard quote for [language-lawyer]:

[bidirectional.iterators]

Expression | Operational   | Assertion/note
           | semantics     | pre-/post-condition
---------------------------------------------------------
--r        |               | Preconditions:
           |               |  there exists s such that r == ++s.
---------------------------------------------------------
r--        | { X tmp = r;  |
           | --r;          |
           | return tmp; } |

[input.iterators]

Expression | Operational   | Assertion/note
           | semantics     | pre-/post-condition
---------------------------------------------------------
++r        |               | Preconditions:
           |               |  r is dereferenceable.

Problem is that the pre-condition is not satisfied.

My suggestion for writing the concrete example. This is slightly different in that my_function will be called before elements are actually removed from the list:

list.remove_if([](int n) {
    if ( X + Y == W )
    {
        my_function( Y );
        return X || Y && Z;
    }
    return true;
});

If the exact behaviour is needed, then you can use following which isn't quite as pretty:

for (auto it = list.begin(), last = list.end(); it != last;)
{
    auto next = it;
    ++next;
    
    if ( X + Y == W )
    {
        if ( X || Y && Z )
        {
            list.erase( it );
        }
        my_function( Y );
    }
    else
    {
        list.erase( it );
    }
    
    it = next;
}

Upvotes: 8

Bathsheba
Bathsheba

Reputation: 234715

The current MSVC C++ standard library implements std::list as a circular doubly linked list, with an extra node acting as a coupler between the first and last element.

So --list.begin() == list.end() does hold true.

But note that the behaviour of --list.begin() is undefined, which is why this particular implementation is a possible choice.

Upvotes: 3

Related Questions