2

Note that, contrary to the many questions on the subject (and probably why I can not find a satisfactory answer to this question neither on google nor on stackoverflow), I never dereference *(begin() - 1)


My requirements are to:

  • iterate backwards
  • use functions that do not take reverse iterators, in this example vector::erase()
  • try to keep the code clean, so try to avoid the mental juggling of:

    vector.erase(rev_it.base() - 1)

    (What should the reverse iterator be now to get the the next element in the iteration ? The iterator returned by erase() ? + 1, probably ? - 1 , unlikely ?)

What I’ve come up with is:

for (auto it = vector.end(); it-- != vector.begin(); ) {
    if (condition(*it)) {
        it = vector.erase(it);
    }
}

This seems to work, as it-- returns the iterator’s value and then only decrements it, meaning the iterator is always decremented after the check but before entering the loop body.

In particular:

When entering the loop

  • if vector.end() == vector.begin() the vector is empty and we exit the loop immediately
  • if vector.end() != vector.begin() then we enter the loop, with the first loop body execution with it == vector.end() - 1

When erasing elements

vector.erase(it) returns the following element in the vector, so decrementing the iterator at every iteration gets us to consider exactly once every element in the vector.

When exiting the loop

At the last execution of the loop’s body, it == vector.begin(), so the next time we try the loop condition:

  • the condition returns false
  • it is decremented one last time
  • we exit the loop

That is, my code does seem to compute the iterator position begin() - 1 but never accesses it, nor uses it for comparisons or anything like that.

Is this undefined behaviour?

Do I risk a segfault or something? Or just accessing uninitialized data maybe? Nothing at all because the iterator is discarded before being used in anyway? Is there no way of knowing?

7
  • 3
    It is undefined by omission. In any event, why not use reverse iterators?
    – Peter
    Nov 25, 2019 at 22:14
  • "meaning the iterator is always decremented after the check but before entering the loop body" - that's simply not true. The iterator is copied to a temp, then decremented, then the temp copy is returned by value. That's the only (and proper) way a post-decrement operator on an iterator class can be implemented. The iterator is in UB land before the check; it's just not the iterator participating in the check to begin with; the copy is.
    – WhozCraig
    Nov 25, 2019 at 22:33
  • @WhozCraig It only appears that way, it’s not what happens in practice, you’re absolutely right. Let me edit that in. That doesn’t change my question’s bottom line: does this decremented undefined iterator matter?
    – Cimbali
    Nov 25, 2019 at 22:39
  • Ultimately your question is, is it legal to apply decrement operations on a bidirectional iterator already at sequence start (i.e. begin()). To my knowledge the only container iterator that supports that is std::forward_list, which supports construct of a before_begin() iterator. You're not the first to ask this question, btw. See here. And the advice was the same as it is here: reverse iterator.
    – WhozCraig
    Nov 25, 2019 at 22:43
  • @WhozCraig Actually I might have moved the goalposts a little here, I’ll revert that. Your first comment was what I’m looking or really. Care to post that with maybe a word or two on why UB is bad even if I don’t seem to rely on its current behaviour?
    – Cimbali
    Nov 25, 2019 at 22:54

1 Answer 1

3

How about

for (auto it = vector.end(); it != vector.begin(); ) {
    --it;
    ... rest of the loop body

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.