CODEWITHSUNDEEP
c++set
David Gomes
David Gomes

Reputation: 5825

C++ set find value smaller but closer to x

I looked at lower_bound and upper_bound in the C++ STL for <set>. I can't find a method, however, to get the value closest (from below) to another one in the set. Is there a simple way to get that or do I have to iterate the set?

As an example, say my set contains the following integers 3 4 7 9, then closest(6) = 4 and closest(4) = 4.

Upvotes: 4

Views: 5589

Answers (3)

Arsh
Arsh

Reputation: 1

//included all libraries

 auto find(int l, set<int>&s){

     auto it=s.lower_bound(l);  
   
     if(s.size() and *s.begin()<=l){ //check any smaller element present in set
        
        auto it=s.upper_bound(l);
             it=prev(it);
     }   
   return it;
}

Upvotes: -1

Kerrek SB
Kerrek SB

Reputation: 477110

Try this generic algorithm:

template <typename Set>
typename Set::const_iterator
find_closest(Set const & s, typename Set::value_type const & val)
{
    auto a = s.begin(), b = s.end(), it = s.lower_bound(val);

    if (it == b) 
    {
        if (it != a) --it;
        return it;
    }

    auto nt = std::next(it);

    if (nt == b) return it;
    return val - *it < *nt - val ? it : nt;
}

Upvotes: 3

Rakete1111
Rakete1111

Reputation: 48958

std::upper_bound returns an element greater than the given value, so in your case, your would have to decrement it to get the value before it.

//Returns value of element before 'num'
int closest = *--set.upper_bound(num);

I would have thought that closest(6) = 7, because 7 is closer to 6 than 4. If you want to get 7, you would have to calculate the difference between the adjacent values and compare them.

//Calculate closest value to 'num' in a std::set<int>
int closest(std::set<int>& set, int num)
{
    //Get iterator to element greater than 'num'
    auto it = set.upper_bound(num);

    //Check if 'it' is the 'end' iterator
    if (it == std::end(set))
        return 0;

    int valueLeft = *it--; //Get value of the greater element
    int valueRight = *it; //Get value of the element before (due to post-decrement)

    //Compare diffence between value less and num, and value greater and num
    if (valueLeft - num > num - valueRight)
        return valueRight;
    else
        return valueLeft;
}

std::set<int> set{ 3, 4, 7, 9 };

int a = closest(set, 6); //Returns '7'
int b = closest(set, 4); //Returns '4'

Upvotes: 6

Related Questions