我需要一个结构,我可以按键升序排序键值.如果我向一个Key请求一个Value,我想得到Map中最接近的更大(但不相等)Key的值.
因此,例如,我确实推动100,500和1000.如果我请求750,我会得到1000值.如果我要求450,我会获得500 Value.如果我请求500,我得到1000值.这些键是动态的,这里不可能切换.
我的方法是将带有键和值的类推送到向量,但这将持续为O(n).
是否有更好的方法/更快的方法来实现它而不是通过Key向量迭代并进行比较？
我认为你应该std::map用作容器.并用于std::map::upper_bound找到最近的更大的键.
如果等于可以接受,请使用std::map::lower_bound.
std::map::upper_bound并std::map::lower_bound保证复杂度为O(log(n)).
顺便说一句,如果你仍然想要使用std::vector,std::upper_bound并std::lower_bound保证复杂性为O(log(n))std::vector