寻找std :: map中输入数字的最接近范围的最有效的std算法是什么？

我的数据将被存储在地图上的整数和整数的关键是任何数量值的start_range是end_range寻找std :: map中输入数字的最接近范围的最有效的std算法是什么？

例如我的地图看起来就像这样：现在

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

，如果我输入的号码是150，该算法应返回一个迭代器mymap中[100]。但是，带有输出值（即迭代器 - >秒）的范围检查逻辑应单独完成，以验证它是否落在正确的范围内。

对于输入数字4500，它可以返回mymap [5000]，但范围检查逻辑应该失败，因为它是从5000到5100. 请注意，地图中没有范围的OVERLAP。

来源

2016-08-16 Sitesh

您有std::lower_bound找到不符合您的搜索值的最低项目。

auto it = mymap.lower_bound(value);

从cplusplus map::lower_bound

类似的成员函数，UPPER_BOUND，具有相同的行为LOWER_BOUND，除了在该映射包含具有键等效的元素为k的情况下：在这种情况下， 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 --; 
}

来源

2016-08-16 07:57:34 mksteve

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

来源

2016-08-16 11:54:53

寻找std :: map中输入数字的最接近范围的最有效的std算法是什么？

回答

相关问题