   finding the nearest days in a map?
  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 thisIf the map is empty return 0If the requested day is in the map, return the associated ratingOtherwise,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 dayIf the requested day is later then all days in the map, return the rating from the latest dayHowever, 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 playerstd::map<day, TimePoint> history;TimePoint is a struct containing the rating   
  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...   ;  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.   ;  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...   ;  From what I've read,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 codedouble 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];  Why are you using the non-member version of lower_bound() instead of std::map::lower_bound()?   ;  Ok it's working now. Thanks for the help.   