CODEWITHSUNDEEP
c++
milesma
milesma

Reputation: 1591

In std::map, get an iterator pointing to the LAST element that is NOT GREATER than key

Before the question: I understand the meaning of std::map::lower_bound and std::map::upper_bound

The Question: How can I get an iterator pointing to the LAST element that is NOT GREATER than key.

The following example shows the current behavior of lower_bound/upper_bound.

However, I want:

How can I achieve this?

#include <iostream>
#include <map>

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

  mymap[10]='a';
  mymap[20]='b';
  mymap[30]='c';
  mymap[40]='d';
  mymap[50]='e';

  itlow=mymap.lower_bound (20);  // itlow points to 'b'  
  std::cout << "lower_bound for 20:    " << itlow->first << " => " << itlow->second << '\n';

  itup=mymap.upper_bound (20);   // itup points to 'c'
  std::cout << "upper_bound for 20:    " << itup->first << " => " << itup->second << '\n';


  itlow=mymap.lower_bound (25);  // itlow points to 'c'  
  std::cout << "lower_bound for 25:    " << itlow->first << " => " << itlow->second << '\n';

  itup=mymap.upper_bound (25);   // itup points to 'c'
  std::cout << "upper_bound for 25:    " << itup->first << " => " << itup->second << '\n';


  return 0;
}

Here is the execution result from the above code.

lower_bound for 20:    20 => b
upper_bound for 20:    30 => c
lower_bound for 25:    30 => c
upper_bound for 25:    30 => c

Upvotes: 5

Views: 2290

Answers (2)

milesma
milesma

Reputation: 1591

The honor belongs to @rlbond.

  • use upper_bound and then decrement the iterator by one;

  • if the iterator returned from upper_bound is pointing to map.begin(), it means there is no element in the map that is less than the argument.

Thanks again

#include <iostream>
#include <map>

int main ()
{
  std::map<int,char> mymap;

  mymap[10]='a';
  mymap[20]='b';
  mymap[30]='c';
  mymap[40]='d';
  mymap[50]='e';

  int nValue = 25;

  std::map<int,char>::const_iterator it=mymap.upper_bound (nValue);
  if(it != mymap.begin())
  {
      it--;
      std::cout << "last element no greater than " << nValue << " is :    " << it->first << " => " << it->second << '\n';
  }
  else
  {
      std::cout << "no element is less than " << nValue << '\n';
  }

  return 0;
}

The result gives:

last element no greater than 25 is :    20 => b

Explain:

map.end() will be returned if no such element is found, however, iterator pointing to map.end() can still be decremented as long as it is not pointing to map.begin(), and then it will point to the desired element.

Two Test cases:

  • change nValue to 60 and run the code(in this case, upper_bound will return map.end()), you will get "50 => e", which is correct.
  • Comment out the 5 map set statement to leave an empty map for test, then the map.end() and map.begin() are the same, upper_bound will return map.end(), it will print "no element is less than XX". Still correct.

Upvotes: 6

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275976

template<class It>
std::optional<It> last(std::pair<It,It> range){
  if (range.first==range.second) return {};
  return std::prev(range.second);
}
template<class It>
std::optional<It> last(It b, It e){
  return last(std::make_pair(std::move(b),std::move(e)));
}
template<class C>
auto last(C& c){
  using std::begin; using std::end;
  return last(begin(c), end(c));
}

Then:

auto r=last(mymap.begin(), mymap.upper_bound(20));
if (r) std::cout <<**r;
else std::cout << "nothing";
std::cout <<'\n';

Upvotes: 1

Related Questions