在Vector中查找值的索引,最接近输入

Question

是否有一种有效的方法来查找Vector中最接近参考值的值的索引？

Answer 1

在计算上,如果向量没有排序,你不能指望任何小于O(n)的东西,这可能会或可能不符合你的期望.如果没有,则应更改数据结构.如果是这样,你可以这样使用std::min_element:

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    int refElem = 42;
    std::vector<int> v{1, 5, 36, 50};
    auto i = min_element(begin(v), end(v), [=] (int x, int y)
    {
        return abs(x - refElem) < abs(y - refElem);
    });

    std::cout << std::distance(begin(v), i); // Prints 2
}

如果向量进行排序,在另一方面,你可以用std::lower_bound()和std::upper_bound(),具有对数的复杂性.

如果您认为复杂性是性能问题,请在决定更改数据结构之前进行一些测量.由于向量将它们的元素存储在连续的存储区域中,因此导致高缓存命中率的线性搜索通常优于在数据结构上的计算上更有效的算法,该数据结构在存储器中在此处和那里分配其元素,导致频繁的高速缓存未命中.