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

dguan picture dguan · Aug 12, 2014 · Viewed 10.4k times · Source

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

Robert Allan Hennigan Leahy picture Robert Allan Hennigan Leahy · Aug 12, 2014

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.