CODEWITHSUNDEEP
c++c++11
cross
cross

Reputation: 1068

Map a range of values to a single value

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

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.

Upvotes: 6

Views: 3041

Answers (5)

Mark Lakata
Mark Lakata

Reputation: 20903

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

Upvotes: 4

pascx64
pascx64

Reputation: 984

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/

Upvotes: 2

Jarod42
Jarod42

Reputation: 218323

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

Upvotes: 2

iplayfast
iplayfast

Reputation: 138

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

Upvotes: 0

marom
marom

Reputation: 5230

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.

Upvotes: 1

Related Questions