Map of bucket key values?

Question

I need a structure in which I can press key values ​​when the keys are ordered in ascending order. If I request a value for a key, I would like to get the value of the nearest larger (but not equal) key inside the map.

So, for example, I press 100, 500 and 1000. If I ask for 750, I get a value of 1000. If I ask for 450, I get 500 Value. If I ask for 500, I get the value 1000. These keys are dynamic, the switch is not possible here.

My approach would be to push a class with a key and a value to a vector, but that would last in O (n).

Is there a better way / faster way to implement this instead of iterating ahead the key vector and comparing?

Answer 1

I think you should use std::mapas a container. and use std::map::upper_boundto find the nearest larger key.

In case of equality, it is permissible to use std::map::lower_bound.

std::map::upper_boundand std::map::lower_boundcomplexity is guaranteed as O (log (n)).

By the way, if you still want to use std::vector, std::upper_boundand std::lower_boundwill have complexity like O (log (n)) forstd::vector

Answer 2

Use std::mapand std::map::upper_bound(). std::mapis implemented as a tree, so std::map::upper_bound()O (log (n)) is guaranteed to be.

std::mapsorted by key using this comparison function (default:) std::less. It includes everything you need.

Answer 3

you can use heap (min-heap or max-heap). insert delete or find is O (log (n)) and is easy to implement. it actually looks like a map, but you can program your idea.