STL iterator before std::map::begin()

Question

In C++11's std::map, is there some valid iterator x such that ++x is guaranteed to equal map::begin()? I would like to detect if a function I just called (mine) has walked an iterator off the front of a function. The function will move the iterator exactly one position backward.

Does the answer hold for the rest of the library?

Answer 1

It's very important to realize that Standard Library containers are semi-open ranges [begin, end), i.e. you can iterate one-past-the-end. For bidirectional (and random) iterators you can also do --end() and come back from the brink. Dereferencing one-past-the-end by *end() is undefined behavior, and so is decrementing the begin iterator by --begin() or begin() - 1. There is only one exception to this: std::forward_list which has a non-dereferenceable iterator before_begin() that satisfies ++before_begin() == begin() (but note that for a forward_list you cannot decrement begin() either).

This fundamental asymmetry for bidirectional iterators means that reverse iterators are thin wrappers around regular iterators. In most Standard Library implementations they simply contain a copy base_ of the underyling iterator. Incrementing a std::reverse_iterator calls something like --base_; return *this;, and dereferencing it does auto old = base_; return *--old;. At no point is the underlying iterator decremented to before begin(), and no dereferencing of end() is done that way.

Below are the four ways to iterate over a container supporting bidirectional or random iterators, and the relations between the various iterators (.base() converts a std::reverse_iterator back to its underlying iterator)

#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main()
{    
    auto c = std::map<int, std::string>{ {1, "hello"}, {2, "world"} };
    
    {   // 1) forward iteratation
        auto it = begin(c);
        for (; it != end(c); ++it){}
        std::cout << std::boolalpha << (it == c.rbegin().base()) << "\n";
    }

    {   // 2) meh, backward iteration
        auto it = end(c) - 1; //end return iterator after the last element.
        for (; it != begin(c); --it){}
        std::cout << std::boolalpha << (it == c.rend().base()) << "\n";
    }

    {   // 2') better: reverse iteration
        auto it = c.rbegin();
        for (; it != c.rend(); ++it){}
        std::cout << std::boolalpha << (it.base() == begin(c)) << "\n";
    }

    {   // 1') backward reverse, better avoid this
        auto it = c.rend();
        for (; it != c.rbegin(); --it){}
        std::cout << std::boolalpha << (it.base() == end(c)) << "\n";
    }
}

Live Example

If you have data structure that should support bidirectional iteration but there are no member iterators .rbegin() or rend(), you can easily define them yourself by std::reverse_iterator(end()) and std::reverse_iterator(begin()), respectively (this is also the way the Standard Library usually implements them).

Answer 2

No, iterators before the beginning in std containers are all UB (except for reverse iterators, which will probably not solve your problem).

You probably need to fix the function in question. Failing that, wrap it and catch the bad behavior before you call it. Failing that, you could insert a negative infinity element into the map key type ordering, and add a sentinal value. Failing that, you could write iterator adapters that wrap your map iterators with ones that can go one-before-beginning without UB.

These are ordered in my order of recommendation, roughly. Each has ways it could fail, and they get more error prone and dangerous as my recommendation gets more remote.