Get the closest element to a given element in an std::set

Question

I have a (sorted) set of unsigned int's. I need to find the closest element to a given number.

I am looking for a solution using the standard library, my first solution was to use binary search, but STL's implementation only returns if the element exists. This post, Find Closest Element in a Set, was helpful and I implemented a solution based on std::lower_bound method,

(*Assuming the set has more than 2 elements, no empty/boundary checks are made):

#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;
}

Is there a simpler more standard solution?

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()不需要。