c++ lower_bound for std::map

Question

I'm writing a test program to learn these two func: lower_bound and upper_bound. I previously found on the wiki that this function returns the first iterator that is no less than the parameter. But when I test with numbers not in the map, strange things happened, when the minimum key in the map is 1, I use lower_bound (0) and feel like I should return an iterator with key 1. But it returned mp.end().

The test program is:

// C++ function for illustration
// map::lower_bound() function
#include <bits/stdc++.h>
using namespace std;

int main()
{

  // initialize container
  map<int, int, greater<int>> mp;

  // insert elements in random order
  mp.insert({2, 30});
  mp.insert({1, 10});
  mp.insert({5, 50});
  mp.insert({4, 40});
  for (auto it = mp.begin(); it != mp.end(); it++)
  {
    cout << (*it).first << " " << (*it).second << endl;
  }

  // when 2 is present
  auto it = mp.lower_bound(3);
  cout << "The lower bound of key 3 is ";
  cout << (*it).first << " " << (*it).second << endl;

  // when 3 is not present
  // points to next greater after 3
  it = mp.lower_bound(0);
  if (it == mp.end())
  {
    cout << "The lower bound of key 0 is ";
  }
  cout << (*it).first << " " << (*it).second << endl;

  // when 6 exceeds
  it = mp.lower_bound(6);
  if (it == mp.end())
  {
    cout << "The lower bound of key 6 is ";
  }
  cout << (*it).first << " " << (*it).second << endl;

  it = mp.lower_bound(1);
  auto next = std::next(it);
  cout << "The lower bound of key 1 is ";
  cout << (*it).first << " " << (*it).second << endl;
  cout << "The next of key 1 is ";
  cout << (*next).first << " " << (*next).second << endl;

  return 0;
}

and this is what I got as output:

5 50

4 40

2 30

1 10

The lower bound of key 3 is 2 30

The lower bound of key 0 is 4 0

5 50

The lower bound of key 1 is 1 10

The next of key 1 is 4 0

I have no idea why lower bound of 0 is 4 0, shouldn't it be 1 10?

Answer 1

First, your code has undefined behavior:

it = mp.lower_bound(0);

if (it == mp.end())
  cout << "The lower bound of key 0 is ";

cout << (*it).first << " " << (*it).second << endl;

When it equals to mp.end(), then you cannot dereference it. Change this to:

if (it != mp.end()) 
  cout << "The lower bound of key 0 is "
       << (*it).first << " " << (*it).second << endl;

and you will see that nothing is printed, since mp.lower_bound(0) actually returns end().

Live demo (minimalized): https://godbolt.org/z/hdsK9j6aj

---

shouldn't it be 1 10?

No, it shouldn't. lower_bound(key):

Returns iterator pointing to the first element that is not less than key.

But this less than relationship is evaluated with respect to the provided comparator, which is std::greater in your case. Then, you can logically transform this sentence into:

Returns iterator pointing to the first element that is not mathematically greater than key.

And, since the map does not contain any key mathematically-not-greater-than zero, the end iterator is returned.