How can I improve my look-up table using std::map if TOLERANCE is introduced

let's say I have a system to let people query their "social points" according to personal annual income, also I have a look-up table implemented with std::map, where <key, value> indicates <annual income, social points> to avoid repeated Points generation, take a look at this:

#include <iostream>
#include <map>

using namespace std;
class SocialSystem {
public:
  int queryMyPoints(int income) {
    if (cache.find(income) != cache.end()) {
      return cache[income];
    } else {
      cache[income] = PointsGenerator(income);
      return cache[income];
    }
  }
private:
  map<int, int> cache;
  int PointsGenerator(int income);
}

OK, very naive and simple, look-up and query are both O(1), very efficiently! But now memory issue has taken place, we can no longer afford so much memory for recording each income, so we introduce "TOLERANCE mechanism", namely, if TOL = 1%, and at the any specific given time, I have

// TOL = 1 %
cache[1000] = 67.3;
cache[1200] = 69.8;

That is to say, from now on, for all the number within 1000+-1% will use 67.3 as their points without calling PointsGenerator(), on the other words, the income range [990, 1010] will now be 67.3 points, while [1188, 1212] will be 69.8 points.

So the problem is, how can I ELEGANTLY and with lowest computing complexity to achieve this new mechanism? The stupidest way I can think of right now is to for-loop every single entry in the cache:

// pseudo code
int queryMyPoints(int income) {
  for (auto& it: cache) {
    int lower_bound = cache.first*0.99;
    int upper_bound = cache.first*1.01;
    if (income >= lower_bound && income <= upper_bound) {
      return cache.second;
    }
  }
  // cache miss handling
}

Oh this is so stupid, any better ideas to help me improve this please? Thanks a lot!

Solution

You can use either the map's lower_bound or upper_bound methods which will work just like find(), if the key exists, or they will give you an iterator to either the previous or the next key in the map (with certain subtle details that I'll leave for you to discover on your own).

You'll just need to add a little bit more logic in order to inspect the iterator's key (or the previous one, or the next one), to see if it falls within your expectation. The end result's complexity would be still the same as find's.