std::map, linear interpolation

[Hicham Mouline]

hi,

I have a map<double,double> of data points (xi,yi), modelling a function to
interpolate.
Assuming the points are monotone increasing, such that, i>j, yi> yj if xi>xj
How do i get the inverse of a point y inside the range of yi?


typedef std::map<double, double>::const_iterator CCI;
CCI endi = f.end();
for (CCI iter=f.begin(); iter!=endi; ++iter)
if (iter->second > x)
break;
if (iter==endi)
return NaN;
CCI prev = iter;
--prev;
if (iter->second = prev->second) // shouldn't happen
return prev->first;
return prev->first + (x - prev->second)*(iter->first -
prev->first)/(iter->second - prev->second);


Comments re correctness and performance (if this were to be called inside a
tight loop) are appreciated,

rds,

 

[Alf P. Steinbach]

* Hicham Mouline:

I have a map<double,double> of data points (xi,yi), modelling a function to
interpolate.
Assuming the points are monotone increasing, such that, i>j, yi> yj if xi>xj
How do i get the inverse of a point y inside the range of yi?


typedef std::map<double, double>::const_iterator CCI;
CCI endi = f.end();
for (CCI iter=f.begin(); iter!=endi; ++iter)
if (iter->second > x)
break;
if (iter==endi)

At this point "iter" is no longer accessible.

Your compiler should ideally catch that error.

I suspect you're using Visual C++. If so add option
"/Zc:forScope,wchar_t", or the corresponding mouse-clicking in the IDE
you're using. Note that this is just part of what's needed for
standard-conformance, you'll also want to turn on exceptions (/GR), RTTI
(/GR) and up the warning level considerably (/W4), and similarly for
other compilers: reportedly, very few C++ compilers are C++ compilers by
default, they have to be cajoled and tricked into compiling C++...

return NaN;

C++ does not guarantee existence of a NaN value.

However, you can use a compile time assertion (e.g. the one in Boost) to
ensure that your C++ implementation supports NaN, by checking

CCI prev = iter;
--prev;
if (iter->second = prev->second) // shouldn't happen
return prev->first;
return prev->first + (x - prev->second)*(iter->first -
prev->first)/(iter->second - prev->second);


Comments re correctness and performance (if this were to be called inside a
tight loop) are appreciated,

Your main question re interpolation is off-topic in clc++ and is better
posted in e.g. [comp.programming].

For C++ aspects see above.


Cheers, & hth.,

- Alf

 

[Thomas J. Gritzan]

hi,

I have a map<double,double> of data points (xi,yi), modelling a function to
interpolate.
Assuming the points are monotone increasing, such that, i>j, yi> yj if xi>xj
How do i get the inverse of a point y inside the range of yi?


typedef std::map<double, double>::const_iterator CCI;
CCI endi = f.end();
for (CCI iter=f.begin(); iter!=endi; ++iter)
if (iter->second > x)
break;
if (iter==endi)
return NaN;

You should do a binary search here. Look up lower_bound, upper_bound and
equal_range in your favorite C++ documentation.