3

是否有一种有效的方法可以找到向量中最接近参考值的值的索引？

4

2 回答 2

10

在计算上，如果向量没有排序，你不能期望任何小于 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()，它具有对数复杂度。

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

于 2013-04-06T18:41:44.123 回答
1

  1. 看起来线性搜索是您的选择（至少对于未排序的向量。看起来排序向量只是为了搜索没有意义。

  2. 一般来说，一切都取决于你在“最近”下的意思。这个“最接近”可能应该作为一元谓词来实现。如果元素相等，谓词应该返回类似 0 的值，并且某个值越大，元素与引用的距离越小。

  3. 正如我从 <algorithm> 中看到的那样，最接近您需要的算法是std::min_element但您不仅需要范围参数，还需要参考元素（或确定要引用的元素“多近”的谓词。

  4. 可能您可以通过检查元素是否相等以及如果相等则打破循环获得一些好处。

于 2013-04-06T19:05:19.130 回答