C++ map，找到第一个小于key的元素

Question

我目前正在寻找一种类似于 C++ 映射的数据结构。

我正在寻找一个可以返回第一个元素的函数，该元素立即小于某个数字。例如：

map<int,int> m;
m[1] ++;
m[2] ++;
m[4] ++;
m[5] ++;

find_first_element_less_than(3) ----> return 2; 
m.upper_bound(3) ---> return 4; 

我看过lower_bound功能。但是，它说它返回不小于键的第一个元素。在这种情况下，lower_bound(3) 返回 4。这不是我想要的。

我想知道 C++ 中是否有任何数据结构可以为我做到这一点？

---

更新：

我可以auto it = m.lower_bound(3); if (it != m.begin()) it--;吗？？

Answer 1

如果它不指向地图的开头，您可以找到下限，然后将迭代器递减 1。

Answer 2

我认为您可以通过反转地图 ( map<int,int, std::greater<int> > m;)的顺序然后使用upper_bound来查找比请求的项目“更大”（但实际上更少，因为您反转谓词）的第一个项目来做到这一点。如果您需要按升序进行迭代，则必须使用反向迭代器，这可能会使维护者（包括您自己）稍微有些困惑。仔细考虑您对这种可能解决方案的需求。