c++ how to find the key of a map that has the closest value of a given value

Question

I want to find the key of the closest value to a sorted map. For example:

#include <iostream>
#include <map>

int main ()
{
    std::map<int,int> mymap;

    mymap[1]=10;
    mymap[2]=40;
    mymap[3]=100;
    mymap[4]=200;
    mymap[5]=500;

    int wantedvalue=50;
    int wantedindex=mymap.whatshouldIdohere(wantedvalue);

    std::cout<<"The closest value of "<<wantedvalue<<" in the map is located";
    std::cout<<" on "<<wantedindex<<" and is "<<mymap[wantedindex]<<std::endl;
    //Should be:
    //The closest value of 50 in the map is located on 2 and is 40

    return 0;
}

The code as mentioned in the comments should return the index to, as the wanted value 50 is closer to the 2nd position than any other.

Is there a method that I can do this?

PS: I know I could have a "for", search the whole map and stop when I find a value larger than given value, but the worst execution time for this is searching the whole table. Also I need to run this many times so I'm looking for something better than this.

Answer 1

Using this container you can use only a linear search. For example you can use standard algorithm std::min_element. Otherwise you should use another container.

Here you are

#include <iostream>
#include <map>

int main()
{
    std::map<int, int> mymap;

    mymap[1] = 10;
    mymap[2] = 40;
    mymap[3] = 100;
    mymap[4] = 200;
    mymap[5] = 500;

    int wantedvalue = 50;


    auto it = std::min_element( mymap.begin(), mymap.end(),
        [&](const auto &p1, const auto &p2)
        {
        return
            std::abs(( long )p1.second - wantedvalue) < 
            std::abs(( long )p2.second - wantedvalue);
        });

    std::cout << "The closest value of " << wantedvalue << " in the map is located";
    std::cout << " on " << it->first << " and is " << it->second << std::endl;

    return 0;
}

The program output is

The closest value of 50 in the map is located on 2 and is 40