C++ map question

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 1

A std::map sounds reasonable for memoization here provided your values are guaranteed not to be contiguous.

#include <map>

// ...

std::map<int, double> memo;
memo.insert(std::make_pair(5, 0.5));
double x = memo[5]; // x == 0.5

Answer 2

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.

Answer 3

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.

Answer 4

The HASH_MAP is the best STL algoirthim for fast lookup than any other algorithims. But, filling takes little bit more time than map or vector and also it is not sorted. It takes constant time for any value search.

std::hash_map<int, double,> memo;
memo.insert(std::make_pair(5, 0.5));
memo.insert(std::make_pair(7,0.8));
.
.
.
hash_map<int,double>::iterator cur  = memo.find(5);
hash_map<int,double>::iterator prev = cur;
hash_map<int,double>::iterator next = cur;    
  ++next;
  --prev;

Interpolate current value with (next).second(), (prev).second() values..

Answer 5

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).

Answer 6

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);
}