Searching a list for "closest" floating-point value using STL

This is a somewhat simple problem, but I'm looking for an elegant solution using the STL. Let's say that I have some STL container containing std::pair<unsigned char, float> objects. I want some function that will take a float as an argument and return the unsigned char associated with the float that is closest to the input argument in absolute value. For instance:

Code:

---

/* Assume pairList contains:
    (1, 0.5)
    (2, 1.0)
    (3, 2.0)
    (4, 4.0)
*/

unsigned char charValue = findClosestValue(pairList.begin(), pairList.end(), 2.5);
// For this call, charValue would now equal 3.

---

What I've thought of doing now is using std::min_element to find the "minimum" value in the list; I would then provide a predicate structure that would compare its two arguments against the input float value (in the above example, 2.5), like this:

Code:

---

whateverContainerTypeIUse<unsigned char, float>::iterator it = std::min_element(pairList.begin(), pairList.end(), AbsoluteValueDifferenceCompare(2.5));

---

What I'm hoping to avoid would be the linear search through the list of pairs that std::min_element would have to do. The list will be sorted ascendingly according to the floating point portion of the pair, so I was hoping to be able to leverage some sort of binary search algorithm to improve performance.

To anyone who is interested in what this is for: this would be written for an embedded system that contains a DAC. The DAC is controlled by writing a byte to an internal register; this changes the output voltage. However, the function mapping the voltage to the register value is nonlinear, so it is best to just use a lookup table to find the "best" register value for a particular voltage. I just want the user to be able to pass a specific voltage level to this function, and it will do the best it can to set the DAC to that level.

I would welcome any suggestions. Thanks!

If you use a sorted vector (or another container with a random access iterator), you should be able to use lower_bound to find an element close to the one that you are looking for. The search is done using a binary search, so it should be faster than min_element.

You will need to check the element before the insert location and the element at the insert location to see which is closer.

Best regards,
John

Well, jwbarton beat me to it, but here is sample code. As mentioned,
you need to check the element before it (if it exists).
I think I have all the needed checks so that you do not
access an element that does not exist ... (but this should be verified)

Code:

---

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

typedef std::pair<unsigned char,float> PAIR;

typedef std::pair<PAIR,bool> PAIR_FOUND;

struct ClosestTo
{
    bool operator () (const PAIR & lhs , const PAIR & rhs)
    {

        if (lhs.second < rhs.second)
            return true;
        else
            return false;
    }

};

int main()
{
    vector<PAIR> v;

    v.push_back( PAIR(1,0.5f) );
    v.push_back( PAIR(2,1.0f) );
    v.push_back( PAIR(3,2.0f) );
    v.push_back( PAIR(4,4.0f) );

    // sort if needed ... I assume that the vector is already sorted

    PAIR x(0,2.5f); // first number doesn't matter

    vector<PAIR>::iterator it = lower_bound( v.begin() , v.end() , x , ClosestTo() );

    if (it == v.end() ) // the last element is closest
    {
        if (!v.empty())
        {
            --it;  // goto last element
        }
    }
    else if (it != v.begin()) // NOTE: editted post .. previous logic was flawed
    {
        vector<PAIR>::iterator it1 = it;
        --it1;

        float dist1 = fabs(x.second - it1->second);
        float dist  = fabs(x.second - it->second);

        if (dist1 < dist) --it;
    }
    if (it != v.end())
    {
        cout << "closest is : (" << (int)it->first << "," << it->second << ")\n";
    }
    else
    {
        cout << "list must be empty\n";
    }


    return 0;
}

---

As noted. You need a random access iterator for std::lower_bound
(so no std::list). If you use a set/map those containers have a
lower_bound member function.

Great. That's exactly the type of thing I was looking for. It might be more appropriate for me to use a map in this case, so I could just use std::map::lower_bound to accomplish this. Thanks a lot to both of you guys.