如何调整地图以找到最近的较小物体？

Question

例如,如果我的地图是从整数到双精度并且包含:

• 2 - > 3.4
• 3 - > 87.3
• 5 - > 0.0
• 12 - > 43.4

当我搜索4时,我必须得到87.3,因为3是地图中最近的小键.当我搜索11时,我必须获得0.0.

这可以通过平衡树来完成.但我不希望实现一个平衡的树,可能有一种方法直接使用STL吗？

Answer 1

这可以通过以下方式完成std::map::lower_bound.根据映射的确切状态,您可能需要递减迭代器(以实现更小的元素).

在任何情况下,总体复杂性都是对数的.