我正在寻找一个STL排序,如果容器中不存在确切的值,则返回与目标值"最接近"的元素.它需要很快,所以基本上我正在寻找一个略微修改的二进制搜索...我可以写它,但它似乎应该已经存在的东西......
你的意思是lower_bound/ upper_bound功能？这些执行二进制搜索并返回最接近您正在寻找的值的元素.
澄清:lower/upper_bound的全局版本仅在范围排序时才起作用,因为它们在内部使用某种二进制搜索.(显然,std :: map中的lower/upper_bound方法始终有效).你在你的问题中说你正在寻找某种二进制搜索,所以我假设范围是有序的.
此外,两者lower_bound都不upper_bound返回最近的成员.如果X您要查找的值不是范围的成员,则它们将返回大于第一个元素X.否则,lower_bound将返回第一个值等于X,upper_bound将返回最后一个值等于X.
所以要找到最接近的值,你必须这样做
lower_boundX.最后一个(即最高的)元素是最接近的元素X.第一个(即最低的)元素是最接近的元素X是您要查找的元素那么你正在寻找一个距离某个值最小的元素k？
使用std::transform每个变换x来x-k.使用std::min_element带有返回的比较函数abs(l) < abs(r).然后添加k回结果.
编辑:或者,您可以使用std::min_element比较功能abs(l-k) < abs(r-k),并消除std::transform.
EDIT2:这适用于未分类的容器.对于已分类的容器,您可能需要nikie的答案.