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: 
If you consider a map, always consider a vector, too. For values that aren't changed much (or even not at all) during the application running, a pre-sorted `std::vector< std::pair<Key,Value> >` (with `O(N)` lookup) more often than never performs faster for lookups than a `std::map<key,Value>` (with `O(log N)` lookup) - despite all the theory. 

You need to try and measure.
Refer : <http://www.cplusplus.com/reference/stl/map/>

You can use Map ,

```
typedef std::map<int,const double> mapType;

```

Performance of maps are like :

**map:: find**
Complexity
Logarithmic in size.

**Beware of Operator [ ] in map** 

If x matches the key of an element in the container, the function returns a reference to its mapped value.

If x does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the map size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).