C++与えられた値に最も近い値を持つマップのキーを見つける方法

Question

ソートされたマップに最も近い値のキーを探したい。たとえば、次の希望値50が他よりも第2の位置に近いほど、コメントで述べたよう

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

コードは、へのインデックスを返すべきです。

私はこれを行う方法がありますか？

PS： "for"があり、指定された値より大きな値を見つけたらマップ全体を検索して停止することができますが、この最悪の実行時間はテーブル全体を検索することです。また、これを何度も実行する必要があるので、私はこれよりも優れたものを探しています。

Answer 1

このコンテナを使用すると、線形検索のみを使用できます。たとえば、標準アルゴリズムstd::min_elementを使用することができます。それ以外の場合は別のコンテナを使用してください。フルスキャン -

ここでは、

#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 closest value of 50 in the map is located on 2 and is 40