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

[Bob Davis]

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:air<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:

/* 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:

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!

[jwbarton]

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

[Philip Nicoletti]

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)

#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.

[Bob Davis]

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.