std::map::iterator decrement on single element

Question

What should std::map iterator decrement return, if there's only single element in the map? Here's the sample code

#include <map>
#include <stdio.h>
int main()
{
    std::map<int, int> m;
    m.insert(std::make_pair(1, 1));
    //std::map<int, int>::iterator it = m.begin();
    std::map<int, int>::iterator it = m.upper_bound(0);
    printf("isbegin: %d\n", it == m.begin());
    --it;
    bool isend = it == m.end();
    printf("isend: %d\n", isend);
}

On Windows it will print isend: 1, on Linux with g++ 4.6 it will print isend: 0.

The question: is the decrement above really a case of UB? and if not then what result is correct - Windows or Linux one?

UPDATE: modified code to show that upper_bound is called

See http://stackoverflow.com/questions/8533875/substraction-or-decrement-random-access-iterator-pointing-to-begin — Nick, May 02 '13 at 09:51
Well, in real app the iterator is returned from upper_bound(), does the related Q still apply? — queen3, May 02 '13 at 09:53

score 7 · Accepted Answer · answered May 02 '13 at 09:53

7

Decrementing something to the element before begin() doesn't make sense. This is undefined behavior and there is no correct or incorrect answer.

answered May 02 '13 at 09:53

olevegard

5,294
1
25
29

In real app the iterator is returned from upper_bound, so decrementing "some iterator" is illegal until we check that it's not equal to begin()? – queen3 May 02 '13 at 09:54
It is not "illegal", but undefined. But yes, you should always be sure you're not decrementing a pointer that points to begin(). If you do so, you have no guarantee for what happens, even if you increment it back to begin() – olevegard May 02 '13 at 09:58

score 2 · Answer 2 · answered May 02 '13 at 10:09

for an iterator r the operation --r is valid if before the operation is done there exists s such that r == ++s and after the operation is done r is dereferenceable. (§24.2.6 Bidirectional.iterators )

Since begin() returns an iterator to the first element of the container there is no element s which can be incremented to get to r so this is undefined.

std::map::iterator decrement on single element

2 Answers2