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?

Solution 1

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.

Solution 2

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).

Solution 3

By "walk the iterator off the front" I presume you are decrementing a forward iterator something like this:

// don't do this:
for(it = mymap.end(); --it >= mymap.begin(); ) { ... }

Instead, increment a reverse iterator like this:

// this is better:
for(it = mymap.rbegin(); it != mymap.rend(); ++it) { ... }

-Jesse

Comments

[George Hilliard]

If I use a reverse iterator, I have the same problem with another function, but with the end of the map and moving the iterator forward.

[Jesse Chisholm]

Out of curiosity, why do you need to move an iterator opposite to its natural direction? What about do { ... } while (it != mymap.begin();

[George Hilliard]

I'm implementing another iterator that must iterate around a tree of maps I'm writing. ForwardIterator works fine; now I'm going for BidirectionalIterator.

[Jesse Chisholm]

I suspect you are right that begin()-1 is undefined. You may be stuck with checking after incrementing but before action if you are already at end() and checking after action but before decrementing if you just handled begin().

[George Hilliard]

Iterator wrappers seem clean at first glance, then I think about how I would have to use them and it gets very nasty, very quickly.

[Jesse Chisholm]

Interesting question, that standard BiDirectionalIterators must handle somehow. last() and end() are well defined, but it seems that first() isn't related to begin() in the same way.

[Yakk - Adam Nevraumont]

@thirtythreeforty yep, which is why I included it, but only as a remote "oh my god, nothing else will work" option. With a boost iterator fascade help it would only be moderately nasty. Or write it by hand. Or lazy-concatinating two boost-type-erased iterator ranges. (Again, in order of recommendation). If you take the last one of the last one, you'll get what you deserve: it works in theory, but gah the smell. In short, just fix the function, it shouldn't be decrementing an iterator that it doesn't have a valid range for.

[Jesse Chisholm]

If you implement RandomAccessIterator, then obj[-1] would be the position before begin(), and obj[N] would be the same as end(). Then your BiDirectionalIterator is a restricted interface on your RandomAccessIterator.

[George Hilliard]

Interesting. maps don't implement that, do they? And I'm not going for RandomAccessIterator; it makes little sense for my structure.

[TemplateRex]

ahem, std::forward_list does have a before_begin() member

[TemplateRex]

@thirtythreeforty use regular iterators when moving forward, and reverse iterators when moving backwards. Alternatively, if you want to use regular iterators for backward iteration, make sure never to decrement begin() because that entails UB. See my answer for the 4 ways to iterate.

[TemplateRex]

@JesseChisholm obj[-1] is UB.

[MSalters]

@TemplateRex: And that's the one container in the standard library where you can't "walk an iterator off the front". I don't think that's a coincidence.

[TemplateRex]

@MSalters of course, but the point is that walking of the front is best avoided by checking against rend(), not by UB decrementing begin() and doing a Wyle E. Coyote, see my answer below

[aaronman]

So thanks for downvoting the crap out of my answer, I would just like to say that I stated in the answer that it is UB and that UB is not the devil, if you only need to have your code compile in one place and have it documented that it is UB what's the problem. That being said obviously he should be able to use reverse iterators but I was just answering his question

[TemplateRex]

@aaronman I'm sorry to hear you are upset about the downvote. To be fair, I was the only one out of 3 donwvoters to explain my reasons for doing so. Please don't take it personally, I didn't say your answer was crap, but SO answers should also be useful to future readers. UB really is the devil because it can silently break your code.

[aaronman]

I personally would avoid UB in any code I write but if someone is explicitly asking to not do things the correct way (with reverse iterators) and I give him an answer that mentions that the answer is UB ID see what the big deal is. Also respect for actually commenting on my answer so I can berate you unlike the other DV'rs :)

[sehe]

@aaronman UB is "the devil" (if you insist on the phrasing). What you (rightly) think is sometimes okay is "Implementation Defined Behaviour" (it's still unspecified, but not undefined!). Because that's a promise that your vendor makes. A language that doesn't promise to do what you coded is a language I'd never again use for anything.

[Lightness Races in Orbit]

@aaronman: UB is always to be avoided. Implementation-defined and unspecified behaviour less so, I concede. But UB really is awful - it sits at a machine-level of uncertainty and you can't ask your vendor or compiler to guarantee any results, not even on consecutive runs of your program with the same input.

[George Hilliard]

Could someone define the abbreviation UB for me?

[TemplateRex]

@thirtythreeforty Undefined Behavior

[TemplateRex]

@thirtythreeforty the C++ Standard Committee has installed a study group on this subject, see also this Q&A.

[George Hilliard]

Ah, thanks. I figured it was Undefined something.

[Jesse Chisholm]

@TemplateRex - agreed, you would have to check for and catch obj[-1] in the indexer and deal with it properly to avoid an invalid index exception. I was saying that the concept of obj[-1] in a RandomAccessIterator is equivalent to the concept of obj.begin()-1 in more typical iterators.

[Spencer]

This answer would be strengthened with a mention of whether rend() can be dereferenced or not.