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.

Bosson

As values in map are not sorted, there is only one solution - full scan. – Tutty

" I'm looking for something better than this." use proper container. std::map is not suitable here – Tutty

if you find yourself needing to do this often, a plain map may not be the best data structure for your needs. You can give boost::bimap a go. – Walk

@Tutty I sort them before by other methods. Also I use the map elsewhere too. – Bosson

You sort what? Values? Are you serious? – Tutty

I have an kinda sorted index in the map. This whole thing is part of a larger algorithm that is not displayed in this example. I just need this part solved. – Bosson

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

Purvis

I think std::abs would be more readable than a ternary expression – Walk

@StoryTeller There is a problem with std::abs that can produce a negative number. – Purvis

Huh? You'll have to illustrate. That's contrary to the documentation. Not to mention a naive implementation is pretty much a ternary expression. – Walk

@StoryTeller Try to use for example INT_MIN. – Purvis

Oh, you are referring to the absolute value of INT_MIN in a 2's complement system? Yes negating it would be out of range. But for a wanted value of INT_MIN and a pair.second 0, your approach suffers just the same. So I'd opt for readability. – Walk

@StoryTeller I could add std::make_unsigned.:) – Purvis

One could also use std::abs<long>. I still advocate for clarity over premature edge case analysis. But it's your answer, and therefore your party. – Walk

@VladfromMoscow I encounter some problem by using "auto". Can you provide me the code without using "auto" please? – Bosson

@GiannisChristoforidis Instead of the auto you can use the explicit type const std::pair<const int, int> &. – Purvis

@VladfromMoscow Thank you very much, it works perfectly :) – Bosson