C++ Wie finde ich den Schlüssel einer Karte, der den nächstliegenden Wert eines gegebenen Wertes hat?

Question

Ich möchte den Schlüssel des nächsten Wertes zu einer sortierten Karte finden. Zum Beispiel:

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

Der Code wie in den Kommentaren erwähnt sollte den Index, wie das gewünschte Wert zurück 50 ist näher an der zweiten Position als jeder andere.

Gibt es eine Methode, die ich tun kann?

PS: Ich weiß, ich könnte ein "für" haben, die gesamte Karte suchen und aufhören, wenn ich einen Wert größer als gegeben finden, aber die schlechteste Ausführungszeit dafür ist die gesamte Tabelle zu suchen. Auch ich muss das viele Male laufen, also suche ich nach etwas Besserem als das.

Answer 1

Mit diesem Container können Sie nur eine lineare Suche verwenden. Zum Beispiel können Sie den Standardalgorithmus std::min_element verwenden. Andernfalls sollten Sie einen anderen Container verwenden.

Hier sind Sie

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

Das Programm Ausgabe

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