Public Group

# finding the nearest days in a map?

This topic is 3311 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a map that represents a player's ratings on certain days. I am trying to create a function to get the players rating on a specific day that behaves like this If the map is empty return 0 If the requested day is in the map, return the associated rating Otherwise, Find the two closest days in the map and return a value that is linearly interpolated between the two associated ratings. If the requested day is earlier then all days in the map, return the rating from the earliest day If the requested day is later then all days in the map, return the rating from the latest day However, I'm having trouble creating this function. Here is what I have come up with so far, but I'm not sure how to find the next highest day.
typedef boost::gregorian::date day;
double Player::GetInterpolatedRating( day d)
{
if (history.size() == 0)
{
return 0;
}

std::map<day, TimePoint>::iterator lower = lower_bound(history.begin(), history.end(), d);

if (lower == d)
{
return history[d].rating;
}

//???????????????

}


history is a member variable of player std::map<day, TimePoint> history; TimePoint is a struct containing the rating

##### Share on other sites
To do this computationally efficiently, you may need to use up some extra memory. Namely, an array and a map.

The first map is your standard "Date to Rank" map. The array is just a sorted list of the dates in your map (i.e. the key's of your map sorted in ascending order). First check the map to see if the date is in it. If it isn't, do a binary search of your array. Ultimately, you will land on two days that your date is between, and you can get their values in the map.

This is not a very pretty solution, however, if you will be adding dates willy nilly into the array. I am assuming that you will most likely be pushing new dates onto the end...

##### Share on other sites
Is it really worth it to add a sorted array here? How bad can a linear search be?
After all, even if a player plays a game every other day for over five years, that's still only 1000 odd entries.

That's like what? .01 seconds? It doesn't seem like it'd make a noticeable difference either way.

##### Share on other sites
Didn't check your code too well. Lower_bound performs a binary search on a sorted container anyway. If lower != d, can't you just increment the iterator to get the next highest element, which should be one above?

The issue is, lower_bound is supposed to take a sorted container anyway -- so you can either get the keys and sort them each time, or keep a pre-sorted vector and use lower_bound...

##### Share on other sites
Maps automatically sort everything anyway.
However, random access is impossible, so binary search takes linear time. Although as I mentioned, I don't think that's a problem.

I just realized that I had been forgetting that iterators can be incremented!

Ok here's my revised code

double Player::GetInterpolatedRating( day d) const{    if (history.size() == 0)    {        return 0;    }    std::map<day, TimePoint>::const_iterator lower = lower_bound(history.begin(), history.end(), d);    if (lower->first == d)    {        return lower->second.rating;    }    if (d <= history.begin()->first)    {        return history.begin()->second.rating;    }    if (d >= (--history.end())->first)    {        return (--history.end())->second.rating;    }    std::map<day, TimePoint>::const_iterator upper = lower;    upper++;    double r1 = lower->second.rating;    double r2 = upper->second.rating;    int numerator = (d - lower->first).days();    int denominator = (upper->first - lower->first).days();    return r1 + (r2-r1) * (double) (numerator/denominator);}

It's working except that lower_bound is complaining about some sort of missing operator.

C:\Program Files\CodeBlocks\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\include\c++\3.4.5\bits\stl_algo.h||In function `_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = std::_Rb_tree_const_iterator<std::pair<const day, TimePoint> >, _Tp = day]':|
C:\ActiveProjects\Expy\players.cpp|31|instantiated from here|
C:\Program Files\CodeBlocks\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\include\c++\3.4.5\bits\stl_algo.h|2634|error: no match for 'operator<' in '(&__middle)->std::_Rb_tree_const_iterator<_Tp>::operator* [with _Tp = std::pair<const day, TimePoint>]() < __val'|
K:\CodeBlocksI\Boost\boost\detail\shared_count.hpp|377|note: candidates are: bool boost::detail::operator<(const boost::detail::weak_count&, const boost::detail::weak_count&)|
K:\CodeBlocksI\Boost\boost\detail\shared_count.hpp|275|note: bool boost::detail::operator<(const boost::detail::shared_count&, const boost::detail::shared_count&)|
||=== Build finished: 1 errors, 0 warnings ===|

[Edited by - Storyyeller on June 22, 2009 4:11:09 PM]

##### Share on other sites
Why are you using the non-member version of lower_bound() instead of std::map::lower_bound()?

##### Share on other sites
Ok it's working now. Thanks for the help.

1. 1
Rutin
21
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 13
• 38
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631715
• Total Posts
3001868
×