std :: mapに最も近い範囲の入力番号を見つけるのに最も効率的なstdアルゴリズムは何ですか？

Question

私のデータは値がend_range

例えばあるキーは、任意の数 のstart_range整数および整数 のマップに格納されますマイマップは、次のようになります。私の入力数が150である場合

std::map<int,int> mymap; 
    mymap[100]=200; 
    mymap[1000]=2000; 
    mymap[2000]=2500; 
    mymap[3000]=4000; 
    mymap[5000]=5100; 

さて、このアルゴリズムは、[100]をMYMAPするイテレータを返す必要があります。 しかし、出力値（すなわちイテレータ→秒）の範囲チェックロジックは、それが正しい範囲内にあるかどうかを検証するために別々に実行されなければなりません。

入力番号4500の場合、mymap [5000]が返される可能性がありますが、範囲チェックロジックは5000から5100のように失敗します。 マップに範囲のオーバーラップがないことに注意してください。

Answer 1

std::lower_boundあなたの検索値に合致しない最も低いアイテムを見つけるにはstd::lower_boundです。

auto it = mymap.lower_bound(value); 

UPPER_BOUND、同様のメンバ関数cplusplus map::lower_bound

から、マップをKキー同等持つ要素を含む場合を除き、LOWER_BOUNDと同じ挙動を有する：ここで、 lower_boundはその要素を指すイテレータを返し、upper_boundは次の要素を指すイテレータを返します。

したがってlower_boundは、検索より少なくない最初の値を返します。これは、前回値のために、あなたがlower_bound - 1が必要になることを意味するが、唯一のlower_bound != begin()

auto it = mymap.lower_bound(value); 
if(it->first != value && it != mymap.begin()) { 
    it --; 
} 

またはupper_bound

auto it = mymap.upper_bound(value); 
if(it != mymap.begin()) { 
    it --; 
} 

Answer 2

を使用する場合には（がよりキー大きい探しUPPER_BOUND >）がキーを提供するか、地図の最後に停止します。キー以上等しい探し

LOWER_BOUND（> =）はキー提供またはマップの終わりに下記

入力の最も近い範囲を見つけるためのコードであり、停止します番号：Demo

typedef std::map<int,int>::iterator Iter; 

Iter getIterator(std::map<int,int> &m, int val) { 
    Iter lb = m.upper_bound(val); 
    if(lb == m.begin()) { 
     return m.end(); 
    } 
    Iter it = std::prev(lb); 
    if(it->first <= val && val <= it->second) { 
     return it; 
    } 
    else{ 
     return m.end(); 
    } 
} 
int main() { 
    // your code goes here 
    std::map<int,int> mymap; 
    mymap[100]=200; 
    mymap[1000]=2000; 
    mymap[2000]=2500; 
    mymap[3000]=4000; 
    mymap[5000]=5100; 

    int a[4]{4500, 4000, 150, 0}; 
    for(int x : a){ 
     Iter it = getIterator(mymap, x); 
     if(it != mymap.end()){ 
      cout << "Value " << x << " : Found in range: " << it->first << ", " << it->second <<endl; 
     }else{ 
      cout << "Value " << x << " : NOT FOUND!" <<endl; 
     } 
    } 
    return 0; 
}