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

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 完成。根据地图的确切状态，您可能需要递减迭代器（以获得实际上更小的元素）。

在任何情况下，总体复杂度都是对数的。