Map a range of values to a single value

Question

I need to map values ranging between lowerBound and upperBound to a certain value.

Illustrative Example:

For example, imagine I have GPS system which has users subscribed to it. This system is able to provide me the distance of the user from a certain point. Based on the distance of the user I want to assign them an ID.

Thus users in distance from

• 1 to 100 get ID: 8.4
• 101 to 200 get ID: 7.2
• 201 to 300 get ID: 3.6
• 401 to 600 get ID: 4.1

and so on...

My approach:

So what I did, I created an std::map by initializing it as follows:

   std::map<int, double> distanceToIdMap; 

   distanceToIdMap =
    {
            {100, 8.4},
            {200, 7.2},
            {300, 3.6},
    };

Then I use this code to get the ID for the given distance:

double roundUpToHundred = std::ceil(realDistance / 100.0) * 100;
double powerForDistance = distanceToIdMap.at(roundUpToHundred);

However my approach breaks down for the 401 to 600 distance, because by ceiling to the nearest hundred for a distance of 400+ I get the value 500 for which I don't have an entry in the map. Of course the trivial solution would be to add an entry for 500 to the distanceToIdMap but that is not how I want to handle this problem.

I would like to have a map with {(lowerbound, upperbound) , correspondingID} structure so I can address cases where an ID covers distance spanning more than 100m. And a given can check if the lowerBound < realDistance < upperBound and then provide the ID.

Answer 1

It sounds like a use case for std::lower_bound. Note that lower_bound is the correct implementation, not upper_bound. This code compiles and works. The map does not need to be sorted, as it is already sorted. This should run in O(log(N)).

You'll need to catch the exception...

#include <iostream>
#include <algorithm>
#include <map>
#include <stdexcept>

using namespace std;

std::map<int, double> distanceToIdMap =
    {
            {100, 8.4},
            {200, 7.2},
            {300, 3.6},
            {600, 4.1}
    };   

double Distance(int user)
{
    auto x = std::lower_bound(distanceToIdMap.begin(), distanceToIdMap.end(), std::pair<const int,double>(user,0));
    if (x == distanceToIdMap.end()) throw std::runtime_error("can't find");
    return x->second;
}

int main()
{
    for(int user=25;user < 650;user+=25)
    {
        cout << user << " " << Distance(user) << std::endl;
    }
   return 0;
}

Output:

sh-4.3# g++ -o main *.cpp -std=c++11                                                                                                                                                                                                                    
main                                                                                                                                                                                                                                                    
sh-4.3# main                                                                                                                                                                                                                                            
25 8.4                                                                                                                                                                                                                                                  
50 8.4                                                                                                                                                                                                                                                  
75 8.4                                                                                                                                                                                                                                                  
100 8.4                                                                                                                                                                                                                                                 
125 7.2                                                                                                                                                                                                                                                 
150 7.2                                                                                                                                                                                                                                                 
175 7.2                                                                                                                                                                                                                                                 
200 7.2                                                                                                                                                                                                                                                 
225 3.6                                                                                                                                                                                                                                                 
250 3.6                                                                                                                                                                                                                                                 
275 3.6                                                                                                                                                                                                                                                 
300 3.6                                                                                                                                                                                                                                                 
325 4.1                                                                                                                                                                                                                                                 
350 4.1                                                                                                                                                                                                                                                 
375 4.1                                                                                                                                                                                                                                                 
400 4.1                                                                                                                                                                                                                                                 
425 4.1                                                                                                                                                                                                                                                 
450 4.1                                                                                                                                                                                                                                                 
475 4.1                                                                                                                                                                                                                                                 
500 4.1                                                                                                                                                                                                                                                 
525 4.1                                                                                                                                                                                                                                                 
550 4.1                                                                                                                                                                                                                                                 
575 4.1                                                                                                                                                                                                                                                 
600 4.1                                                                                                                                                                                                                                                 
terminate called after throwing an instance of 'std::runtime_error'                                                                                                                                                                                     
  what():  can't find                                                                                                                                                                                                                                   
Aborted (core dumped)                                                                                                                                                                                                                                   
sh-4.3# main                                                                                                                                                                                                                                            

Answer 2

Try upper_bound :

 auto upper  = distanceToIdMap.upper_bound( 50 );
 std::cout << "value:" << upper->second << std::endl;

http://www.cplusplus.com/reference/map/map/upper_bound/

Answer 3

with std::map::lower_bound and boost::optional, you may do something like:

const std::map<int, boost::optional<double>> distanceToIdMap =
{
    {0, boost::none},
    {100, 8.4},
    {200, 7.2},
    {300, 3.6},
    {400, boost::none},
    {600, 4.1}
};

for (auto v : {-10, 50, 99, 100, 101, 250, 350, 500, 601})
{
    auto it = distanceToIdMap.lower_bound(v);

    if (it != distanceToIdMap.end() && it->second) {
        std::cout << v << " " << *it->second << std::endl;
    } else {
        std::cout << v << " None" << std::endl;
    }
}

Live example

Answer 4

What about avoiding maps at all?

std::vector<std::pair<double, double>> table =
{
    {0, 0},
    {94.5, 2.1},
    {314.4, 4.7}
} ;

double distance = ...
double value = std::upper_bound(table.begin(), table.end(), std::pair(distance, 0)) ;

Drawback: table must be properly ordered.

Answer 5

Here is a simple solution:

int mapdistance[] = {100,200,300};
double mapid[] = {8.4,7.2,3.6};
double dist=0;
for(int i=0;i<sizeof(mapdistance)/sizeof(int);i++) {
   dist += mapdistance[i];
   if (realdistance<=dist) return mapid[i];
}