How to adapt the map to find the nearest smaller object?
For example, if my map is from integers to doubles and contains:
- 2 → 3.4
- 3 → 87.3
- 5 → 0.0
- 12 → 43.4
When I search for 4, I should get 87.3, since 3 is the closest smaller key that is on the map. When I search for 11, I should get 0.0.
This can be done with a balanced tree. But I don't want to implement a balanced tree, maybe there is a way to do this directly using STL?
+3
source to share
1 answer
This can be done with std::map::lower_bound
. Depending on the exact state of the map, you may need to shrink the iterator (to get the element actually smaller).
The overall complexity is logarithmic anyway.
+5
source to share