c++ - 获取最接近 std::set 中给定元素的元素

Question

我有一组(排序的)未签名 int的。我需要找到最接近给定数字的元素。

我正在寻找使用标准库的解决方案 ,
我的第一个解决方案是使用二进制搜索，但 STL 的实现仅在元素存在时返回。
这篇文章，Find Closest Element in a Set ，很有帮助，我实现了一个基于 std::lower_bound 的解决方案方法，

(*假设集合有超过 2 个元素，则不进行空/边界检查):

#include <iostream>
#include<set>
#include<algorithm>
#include<cmath>

int main()
{
    std::set<unsigned int> mySet = {34, 256, 268, 500, 502, 444};
    unsigned int searchedElement = 260;
    unsigned int closestElement;

    auto lower_bound = mySet.lower_bound(searchedElement);
    if (lower_bound == mySet.end()){
        closestElement = *(--lower_bound);
    }

    std::set<unsigned int>::iterator prevElement = --lower_bound;
    bool isPrevClosest = std::abs(*prevElement - searchedElement) > std::abs(*lower_bound - searchedElement);
    closestElement = isPrevClosest ? *prevElement : *lower_bound;

    std::cout << closestElement << std::endl;

    return 0;
}

有没有更简单更标准的解决方案？

Answer 1

我认为没有比使用 .lower_bound 更好的解决方案了.您可以将算法包装到函数模板中:

template<typename Set>
auto closest_element(Set& set, const typename Set::value_type& value)
    -> decltype(set.begin())
{
    const auto it = set.lower_bound(value);
    if (it == set.begin())
        return it;

    const auto prev_it = std::prev(it);
    return (it == set.end() || value - *prev_it <= *it - value) ? prev_it : it;
}

此函数正确处理所有极端情况(空集、一个元素、第一个元素、最后一个元素)。

例子:

std::set<unsigned int> my_set{34, 256, 268, 500, 502, 444};

std::cout << *closest_element(my_set, 26);   // Output: 34
std::cout << *closest_element(my_set, 260);  // Output: 256
std::cout << *closest_element(my_set, 620);  // Output: 502

请注意 std::abs在您的代码中(几乎)什么都不做:它的参数具有无符号类型并且始终为非负数。但我们知道 std::set元素是有序的，因此我们知道 *prev_it <= value <= *it ，并且没有 std::abs()需要。