C++映射，找到第一个小于键的元素

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找到第一项“更大”（但确实更少，因为你倒置谓词）比请求的项目。如果您需要按升序进行迭代，则必须使用反向迭代器，这可能会对维护人员（包括您自己）产生一些困惑。仔细考虑您对这个可能的解决方案的需求。