Is it safe to use std::prev(vector.begin()) or std::next(vector.begin(), -1) like some_container.rend() as reversed sentry?

Question

I wrote some code that takes iterators but have to do comparison in reversed order,

template<class ConstBiIter>
bool func(ConstBiIter seq_begin, ConstBiIter seq_end)
{
    ConstBiIter last = std::prev(seq_end);
    while (--last != std::prev(seq_begin)) // --> I need to compare the beginning data
    {
        ......
    }
    return true;
}

In VS2013, when running in Debug mode, --last != std::prev(seq_begin) will cause debugger assertion fail with the error message

Expression:string iterator + offset out of range.

but it is perfectly OK when running in Release mode and giving out correct result, because there's no boundary check in Released mode.

My questions are:

1. Is it safe to use std::prev(some_container.begin()) as sentry like some_container.rend()?

2. How can I directly compare a reverse_iterator with an iterator? If I write the code: std::cout << (std::prev(some_container.begin())==some_container.rend()) << std::endl; it won't compile, even if you reinterpret_cast them.

I am curious if prev(some_container.begin()) equals some_container.rend() physically?

Answer 1

No, it's not safe to try and decrement the begin iterator.

std::reverse_iterator (which is what is returned by std::rend) does not actually, underneath, contain an iterator before the begin iterator. It stores an underlying iterator to the next element from the one it conceptually points to. Therefore, when the reverse iterator is "one past the end" (i.e. "before the beginning") its underlying iterator (that you get by calling base()) is the begin iterator.

Answer 2

Undefined behavior is not safe, even if it works today in your test. In C++, "it worked when I tried it" is not good evidence that you are doing it correctly: one of the most common types of undefined behavior is "it seems to work".

The problem is that undefined behavior working is fundamentally fragile. It can break if you breathe on it hard.

The compiler is free to optimize branches and code reached only via undefined behavior away, and in many cases does just that. It is even free to do so after a service patch, compiler upgrade, seemingly irrelevant change in flags passed to compiler, or the length of the executable path name. It is free to work fine 99.9% of the time, then format your hard drive the other 0.1% of the time.

Some of these are more likely than others.

While iterators to std::string and std::vector elements are basically pointers in release, and the compiler can even typedef a pointer to be said iterators, even that assumption can fail when the next compiler version uses wrapped pointers.

Undefined behavior is left in the C++ standard to allow freedom for compiler writers to generate more optimal code. If you invoke it, you can step on their toes.

That being said, there are reasons to use behavior undefined by the C++ standard. When you do so, document it heavily, isolate it, and make sure the payoff (say, delegates twice as fast as std::function) is worth it.

The above is non-isolated and not worth doing undefined behavior, especially because you can solve it without the undefined behavior.

The easiest solution if you want to iterate backwards is to make some reverse iterators.

template<class ConstBiIter>
bool func(ConstBiIter seq_begin, ConstBiIter seq_end)
{
  std::reverse_iterator<ConstBiIter> const rend(seq_beg);
  for (std::reverse_iterator<ConstBiIter> rit(seq_end); rit != rend; ++rit)
  {
    ......
  }
  return true;
}

Now rfirst iterates over the range backwards.

If you need to get back to a forward iterator that refers to the same element for whatever reason, and you are not rend, you can std::prev(rit.base()). If rit == seq_end at that point, that is undefined behavior.