在 std::map 中，获取一个指向不大于 key 的最后一个元素的迭代器

Question

在问题之前：我理解std::map::lower_bound和std::map::upper_bound的含义

问题：如何获得一个指向不大于 key 的最后一个元素的迭代器。

以下示例显示了 lower_bound/upper_bound 的当前行为。

但是，我想要：

• 传入“20”，返回20
• 传入“25”，返回20

我怎样才能实现这个目标？

#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;
}

这是上面代码的执行结果。

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

Answer 1

该荣誉属于@rlbond。

• 使用 upper_bound ，然后将迭代器减一；

• 如果从 upper_bound 返回的迭代器指向map.begin()，则意味着映射中没有小于参数的元素。

再次感谢

#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;
}

结果给出：

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

解释：

如果没有找到这样的元素，就会返回map.end()，但是只要不是指向map.begin()，指向map.end()的迭代器仍然可以递减，然后指向所需的元素。

两个测试用例：

• 将 nValue 更改为 60 并运行代码（在本例中，upper_bound 将返回 map.end()），您将得到“50 => e”，这是正确的。
• 注释掉5个map set语句，留下一个空map进行测试，那么map.end()和map.begin()是一样的，upper_bound会返回map.end()，会打印“没有元素小于XX”。还是正确的。