Making use of std::map<> ordered property: interpolation

The Map container of the C++ Standard template library is an ordered associative container. Often it is used simply for associative property, i.e., to look up a value based on a key. However, the ordered property can often be useful to and the classic example is in one-dimensional interpolation.

The algorithm for the simplest linear interpolation consists of finding the data points with the independent variable values that bracket the value to which we are trying to interpolating and then computing the mean of the dependent variable values weighted by the distance to the independent variables. If we take the input data to be an ordered sequence of pairs of independent and dependent variables then the two main tasks that are required are:

• Finding the position in the sequence which brackets the points which we are interpolating to
• Moving to the next/previous point in the sequence

The logarithmic time for searches in the std::map container makes the first task efficient while easy to use iterators which operate on the ordered sequence of keys make the second task also easy with std::map. Therefore the std::map container makes it very easy to write a simple linear interpolation routine. Here is a simple example:

// Bojan Nikolic <bojan@bnikolic.co.uk>
// Licensed under BSD-3: https://opensource.org/licenses/BSD-3-Clause
#include <map>
#include <vector>
#include <iostream>
#include <boost/assign/list_of.hpp>

double  interpolate(const std::map<double,double> &data,
                    double x)
{
  typedef std::map<double, double>::const_iterator i_t;

  i_t i=data.upper_bound(x);
  if(i==data.end())
  {
    return (--i)->second;
  }
  if (i==data.begin())
  {
    return i->second;
  }
  i_t l=i; --l;

  const double delta=(x- l->first)/(i->first - l->first);
  return delta*i->second +(1-delta)*l->second;
}

int main(void)
{
  std::map<double,double> data = boost::assign::map_list_of(1,1)(2,2)(3,2)(4,1)(5,0);
  std::vector<double> tp=boost::assign::list_of(-10.0)(1)(1.1)(1.5)(2)(2.5)(3)(10);
  for (size_t i=0; i<tp.size(); ++i)
  {
    std::cout<<"At "<<tp[i]<<" : " <<interpolate(data, tp[i])
             <<std::endl;
  }
}