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


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