design choice

Hello,
i am writing a curve class that is supposed to represent a mathematic
function from n tabbulated data (xi,yi) , 0<= i < n
the curve will be used internally to my library by its templated derived
classes only, these templated derived classes are user-visible though,
and so are the template argument types

template <typename Interpolator, typename Extrapolator, typename Integrator>
class Curve {
public:
 virtual ~Curve() {} //
protected:
  double& operator()(double x); // To set a
tabbulated point, might resize/sort the data container
  double operator()(double x) const; // To
interpolate a point
  double integral( double xmin, double xmax ) const; // returns the
integral based on the Integrator
private:
  // tabbulated private data container
};

1) I have 4 interpolators
 1.1 Constant => assumes the function is a stair-like function constant
discontinuous segments in [xi, xi+1]
 1.2 Linear => the function is continuous linear segments over [xi, xi+1]
 1.3 Polynomial => the interpolated function is a (n-1) order polynomial
that passes through the n data points,
                             or m-order polynomial that interpolates over
the m closest points to the desired x
 1.4 Cubic splines => a collection of local cubic polynomials over
individual intervals that provides f'' continuity

2) I have tested these data holders for performance
2.0 double xarr[], double yarr[]
2.1 double data[][2]
2.2 std::map<double, double>
2.3 std::vector<double> xarr std::vector<double> yarr
2.4 std::vector< std::pair<double, double> >
2.5 boost::multi_array<double, 2>

In most cases, calls to operator() const are have the highest performance
requirements, but in other cases,
calls to operator() (non-const) have that.

3) here are the various inter/extrapolators:
class Constant {
public:
 static interpolate( // <dataholder> , double x);
 ...
};

class Linear {
public:
 static interpolate( // <dataholder> , double x);
 ...
};

class Polynomial {
public:
 static interpolate( // <dataholder> , double x);
 ...
};

Unfortunately, where map works well for Constant /Linear, it doesn't for
Polynomial which requires random access to the container for the
interpolation. so 2.2 doesn't work for that. However, inserting data points
in the container doesn't work well for all the 2) that are not 2.2, as it
requires reallocation and resorting.

QUESTIONs
Should i write partial template spec of Curve to have an appropriate private
data container for the relevant interpolator?
The static function signatures in the various interpolators will be
different. Is there a way to use iterators in order to have an identical
signature.
How can I/should I hide the need to choose different containers for
performance reasons?

rds,