c++ - 寻找下限最近的点......但数据未排序

Question

我有一个向量存储到沿线的某个参考点的距离。因此，例如，我想要距离为 700 米或最接近该距离的值的索引。

我假设向量已排序，并成功使用了 lower_bound。

问题是在现实生活中会发生错误，所以我不能保证我总是有一个排序的向量，因为在存储数据时，例如用户可能没有遵循这条线。

如果数据未排序，我如何找到最接近的值？

Answer 1

你不能，因为std::vector它是一个序列容器。您必须使用排序算法对数据进行排序。

Answer 2

您可以使用std::min_element它的三参数形式。传递一个比较器，true如果第一个参数比第二个参数更接近您的目标距离（700m），则返回该比较器。然后返回的结果min_element将是离目标最近的点。

当然，这比 渐近慢lower_bound，但它比对向量排序的最坏情况渐近快。如果您可以对向量进行一次排序，然后在搜索多个不同距离处的最近点时依靠它保持排序，那么您可能应该使用std::sortand std::lower_bound。如果找到最近的点是一次性操作，那么最好以“慢”的方式使用min_element.

Answer 3

将您复制vector到 stlset中，然后使用与 vector 相同的逻辑来查找元素。