C++ STL 集合：我可以使用 upper_bound() 来查找数字与集合元素的最小差吗？

Question

我正在处理一个问题。我有一个数字 a 和一组元素（比如 myset）。我想在 myset 中找到数字 b，使得 |b-a| 最小。我正在使用 it=upper_bound(a) 然后检查 |*it-a| 和 |(*it-1)-a| 并取这两个中的最小值。这是正确的做法吗？

Answer 1

这是正确的，除了边缘情况：如果 upper_bound returns end() 和如果 returns begin() 会怎样？

// pre-conditions: contains at least 1 elem, is sorted

template <typename It, typename Value>
const Value& min_dist(It first, It last, const Value& a)
{
    It it = std::upper_bound(first, last, a);
    if (it == last) {
        return *(std::prev(last, 1));
    }
    else if (it == first) {
        return *it;
    }
    else {
        // somewhere in the middle, so both it and prev are valid
        It prev = std::prev(it, 1);
        return (*it - a) < (a - *prev)
            ? *it : *prev;
    }
}

C++ STL 集合：我可以使用 upper_bound() 来查找数字与集合元素的最小差吗？

C++ STL set: Can I use upper_bound() to find the minimum difference of a number with the elements of the set?

c++

stl

set