Strange behavior of upper_bound() in Maps

Question

I wrote a below sample code to understand upper_bound() in Map, however I could not understand the behavior for the below:-

// Sample upper_bound()
#include <iostream>
#include <map>
#include <limits>

int main ()
{
  std::map<unsigned int,int> mymap;
  std::map<unsigned int,int>::iterator itup;

  mymap[0] = 5;
  mymap[5] = 5;
  mymap[10] = 5;
  mymap[15] = 5;
  mymap[20] = 5;
  mymap[25] = 5;
  mymap[30] = 5;

  // print content:
  for (std::map<unsigned int,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';


  itup=mymap.upper_bound (30);


  std::cout<<"First "<< itup->first<<": Second "<< itup->second<<"\n";

  return 0;
}

From http://en.cppreference.com/w/cpp/container/map/upper_bound,

"Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned."

Why does the past-the-end iterator return such values?

score 1 · Answer 1 · answered Jan 31 '16 at 14:24

1

Since there is no key strictly greater than 30, itup is the end iterator. You are not allowed to dereference the end iterator, so your program has undefined behaviour.

answered Jan 31 '16 at 14:24

Kerrek SB

464,522
92
875
1,084

Thanks for the reply. I was trying to understand your answer in another post http://stackoverflow.com/questions/8415718/c-function-to-insert-to-template-map. Is it possible for me contact you elsewhere, in I do not have chat option here in SO? – Phalgun Jan 31 '16 at 14:30

score 1 · Answer 2 · answered Jan 31 '16 at 14:27

The following line:

std::cout << std::boolalpha << (mymap.upper_bound(30) == mymap.end()) << std::endl;

indeed verifies that this is the iterator to end. You are not supposed to dereference this iterator. If you do - all bets are off, and you'll get some result that is unspecified.

Strange behavior of upper_bound() in Maps

2 Answers2