Question: I have an integral position-based algorithm. (That is, the output of the algorithm is based on a curvilinear position, and each result is influenced by the values of the previous results).

To avoid recalculating each time, I would like to pre-calculate at a given sample rate, and subsequently perform a lookup and either return a pre-calculated result (if I land directly on one), or interpolate between two adjacent results.

This would be trivial for me in F# or C#, but my C++ is very rusty, (and wasn't even ever that good).

Is map the right construct to use? And could you be so kind as to give me an example of how I'd perform the lookup? (I'm thinking of precalculating in milimetres, which means the key could be an int, the value would be a double).

**UPDATE** OK, maybe what I need is a sorted dictionary. (Rolls up sleeves), pseudocode:

```
//Initialisation
fun MyFunction(int position, double previousresult) returns double {/*etc*/};
double lastresult = 0.0;
for(int s = startposition to endposition by sampledist)
{
    lastresult = MyFunction(s, lastresult);
    MapOrWhatever.Add(s, lastresult);
}
//Using for lookup
fun GetValueAtPosition(int position) returns double
{
    CheckPositionIsInRangeElseException(position);
    if(MapOrWhatever.ContainsKey(position)) 
        return MapOrWhatever[position];
    else
    {
        int i = 0;
        //or possibly something clever with position % sampledist...
        while(MapOrWhatever.Keys[i] < position) i+=sampledist;
        return Interpolate(MapOrWhatever, i, i+sampledist, position);
    }
}

```

Thinks... maybe if I keep a constant sampledist, I could just use an array and index it...

Answer: 
std::map is probably fine as long as speed is not too critical. If the speed of the lookup is critical you could try a vector as mentioned above where you go straight to the element you need (don't use a binary search since you can compute the index from the position). Something like:

```
vector<double> stored;

// store the values in the vector
double lastresult = 0.0;
for(int s = startposition, index = 0; s <= endposition; s+=sampledist, ++index)
{
    lastresult = MyFunction(s, lastresult);
    stored[index] = lastresult;
}

//then to lookup
double GetValueAtPosition(int position) returns double
{
 int index = (position - startposition) / sampledist;
 lower = stored[index];
 upper = stored[index+1];
 return interpolate(lower, upper, position);
}

```
please see my comment, but here is map documentation

<http://www.cplusplus.com/reference/stl/map/>

and important note than another poster did not mention is that if you use [] to search on a key that doesn't exist in the map, map will create an object so that there's something there.

edit: see docs here for this info <http://msdn.microsoft.com/en-us/library/fe72hft9%28VS.80%29.aspx>

instead, use find(), which returns an iterator. then test this iterator against map.end(), and if it is equal then there was no match.