c++ - 从上方找到 vector 中最接近值的优雅方法

Question

我需要一个函数，它接受一个 vector (假定已排序)和一个值，并返回 [edit] 大于 小于或等于该数字的最接近的数字，最好使用来自 STL 的算法。我想出了一个使用 std::lower_bound() 的解决方案，但它看起来很笨拙和丑陋:

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:返回第一个不比较less的值
• 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