CODEWITHSUNDEEP
c++stlset
joepol
joepol

Reputation: 842

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

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?

Upvotes: 6

Views: 2015

Answers (3)

jfMR
jfMR

Reputation: 24788

The std::set container is suitable for finding adjacent elements, i.e., finding the element that succeeds or precedes a given element. Considering the problem that you are facing:

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.

There is still an approach you can follow without changing your logic: If the element – whose closest element you want to find – does not exist in the set, then you simply insert it in the set (it takes logarithmic time in the size of the set). Next, you find the closest element to this just added element. Finally, remove it from the set when you are done so that the set remains the same as before.

Of course, if the element was already in the set, nothing has to be inserted into or removed from the set. Therefore, you need to keep track of whether or not you added that element.

The following function is an example of the idea elaborated above:

#include <set>

unsigned int find_closest_element(std::set<unsigned int> s, unsigned int val) {
   bool remove_elem = false;
   auto it = s.find(val);

   // does val exist in the set?
   if (s.end() == it) {
      // element does not exist in the set, insert it
      s.insert(val); 
      it = s.find(val);
      remove_elem = true;
   }

   // find previous and next element
   auto prev_it = (it == s.begin()? s.end(): std::prev(it));
   auto next_it = std::next(it);

   // remove inserted element if applicable
   if (remove_elem)
      s.erase(it);

   unsigned int d1, d2;
   d1 = d2 = std::numeric_limits<unsigned int>::max();

   if (prev_it != s.end())
      d1 = val - *prev_it;

   if (next_it != s.end())
      d2 = *next_it - val;

   return d1 <= d2? *prev_it: *next_it;
}

Upvotes: 0

Evg
Evg

Reputation: 26342

I don't think there is a better solution than using .lower_bound. You can wrap your algorithm into a function template:

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

This function handles all corner cases (empty set, one element, first element, last element) correctly.

Example:

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

Note that std::abs in your code does (almost) nothing: its argument has unsigned type and is always non-negative. But we know that std::set elements are ordered, hence we know that *prev_it <= value <= *it, and no std::abs() is needed.

Upvotes: 10

Arne J
Arne J

Reputation: 415

You could use std::min_element() : as a comperator, give it a lambda that returns the absulute diff e.g.

std::min_element(mySet.begin(), mySet.end(), [searchedElement](const unsigned int a, const unsigned int b) {
  return std::abs(searchedElement - a) < std::abs(searchedElement - b);
});

However, I do think this will no longer apply a binary search...

EDIT : Also, as stated in comments below, std::abs(x - y) for unsigned int values may return an unexpectedly large integer when x < y.

Upvotes: 0

Related Questions