从上面找到矢量中最接近的值的优雅方式

Question

我需要一个函数,它接受一个向量(假定为已排序)和一个值,并返回[edit] 大于小于或等于该数字的最接近的数字,最好使用STL中的算法.我已经提出了使用std :: lower_bound()的解决方案,但它看起来像kludgy和丑陋:

struct ClosestCmp {
    bool operator()(const int & x, const int & y) { return x > y; }
};

// vec is assumed to be sorted
int closest(const std::vector<int> & vec, int value)
{
    std::vector<int>::const_reverse_iterator cri =
        std::lower_bound(vec.rbegin(), vec.rend(), value, ClosestCmp());
    if (cri != vec.rend()) {
        return *cri;
    }
    return -1;
}

// ...
vec.push_back(1);
vec.push_back(2);
vec.push_back(4);
vec.push_back(5);
std::cout << closest(vec, 2) << "\n"; // Should ouput "2"
std::cout << closest(vec, 3) << "\n"; // Should ouput "2"
std::cout << closest(vec, 4) << "\n"; // Should ouput "4"

任何人都可以建议一种更优雅的方式,可能使用STL算法而不需要比较函数或反向迭代器？我查看了STL,但未能找到比这更好的解决方案.

Answer 1

提醒:

• std::lower_bound:返回不比较少的第一个值
• std::upper_bound:返回严格比较的第一个值

根据您的描述,std::lower_bound看起来已经完美契合,出现了什么问题:

int closest(std::vector<int> const& vec, int value) {
    auto const it = std::lower_bound(vec.begin(), vec.end(), value);
    if (it == vec.end()) { return -1; }

    return *it;
}

用作:

int main() {
    std::vector<int> vec;
    vec.push_back(2);
    vec.push_back(4);

    std::cout << closest(vec, 2) << "\n";
    std::cout << closest(vec, 3) << "\n";
    std::cout << closest(vec, 4) << "\n";
}

输出:

2
4
4

Answer 2

需要 C++11：

template<typename InputIterator, typename ValueType>
InputIterator closest(InputIterator first, InputIterator last, ValueType value)
{
    return std::min_element(first, last, [&](ValueType x, ValueType y)
    {   
        return std::abs(x - value) < std::abs(y - value);
    });
}

Answer 3

您只能使用std::lower_bound与std::upper_bound容器顺序匹配的二进制谓词.因此,您不能排序<,然后使用不同的二元谓词(比如说<=或>).所以你的"kludge"实际上是正确的事情.反向排序的向量是您要用于查找小于或等于该值的元素的排序条件.(否则,如果您实际上是在搜索大于或等于的值,则可以使用std::lower_bound.)