结构通过远程键

Question

我需要一个结构来保持基于具有范围中的键的值保存值。 我的实现是C++，所以任何STL或升压将是极好的。

我具有如范围密钥，其是双和值

• [0,2） - > VALUE1
• [2,5） - >数值2
• [5,10） - >值3
• 等

使得搜索的1.23应该返回值1，等等。

现在我正在使用一个包含所有三个部分（key1/key2/value）的矢量进行自定义搜索，但感觉应该有一个更清晰的结构。

编辑：谢谢大家。鉴于这种情况下的范围应该是连续的且不重叠的，使用upper_bound将可以很好地工作。感谢Range解决方案，他们被归档以备将来参考。

Answer 1

如果你的范围是连续的，不重叠的，你应该使用std ::地图和UPPER_BOUND成员函数。或者，您可以使用upper_bound算法的排序向量。无论哪种方式，您只需要记录范围的最低值，随着范围的上半部分由下一个更高的值来定义。

编辑：我认为措辞混淆的，所以我决定提供一个例子。在编写示例时，我意识到你需要upper_bound而不是lower_bound。我总是让这两个人感到困惑。

typedef std::map<double, double> MyMap; 
MyMap lookup; 
lookup.insert(std::make_pair(0.0, dummy_value)); 
lookup.insert(std::make_pair(2.0, value1)); 
lookup.insert(std::make_pair(5.0, value2)); 
lookup.insert(std::make_pair(10.0, value3)); 
MyMap::iterator p = lookup.upper_bound(1.23); 
if (p == lookup.begin() || p == lookup.end()) 
    ...; // out of bounds 
assert(p->second == value1); 

Answer 2

class Range 
{ 
public: 
    Range(double a, double b): 
     a_(a), b_(b){} 
    bool operator < (const Range& rhs) const 
    { 
     return a_ < rhs.a_ && b_ < rhs.b_; 
    } 
private: 
    double a_; 
    double b_; 
}; 
int main() 
{ 
    typedef std::map<Range, double> Ranges; 
    Ranges r; 

    r[ Range(0, 2) ] = 1; 
    r[ Range(2, 5) ] = 2; 
    r[ Range(5, 10) ] = 3; 

    Ranges::const_iterator it1 = r.find(Range(2, 2)); 
    std::cout << it1->second; 

    Ranges::const_iterator it2 = r.find(Range(2, 3)); 
    std::cout << it2->second; 

    Ranges::const_iterator it3 = r.find(Range(6, 6)); 
    std::cout << it3->second; 

    return 0; 
} 

Answer 3

如何沿着这些路线的东西：

#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <map> 
#include <algorithm> 
#include <sstream> 


class Range 
{ 
public: 
    Range(double lower, double upper) : lower_(lower), upper_(upper) {}; 
    Range(const Range& rhs) : lower_(rhs.lower_), upper_(rhs.upper_) {}; 
    explicit Range(const double & point) : lower_(point), upper_(point) {}; 
    Range& operator=(const Range& rhs) 
    { 
     lower_ = rhs.lower_; 
     upper_ = rhs.upper_; 
     return * this; 
    } 

    bool operator < (const Range& rhs) const 
    { 
     return upper_ <= rhs.lower_; 
    } 

    double lower_, upper_; 
}; 

typedef std::string Thing; 
typedef std::map<Range, Thing> Things; 


std::string dump(const std::pair<Range,Thing> & p) 
{ 
    stringstream ss; 
    ss << "[" << p.first.lower_ << ", " << p.first.upper_ << ") = '" << p.second << "'" << endl; 
    return ss.str(); 
} 

int main() 
{ 
    Things things; 
    things.insert(std::make_pair(Range(0.0, 5.0), "First")); 
    things.insert(std::make_pair(Range(5.0, 10.0), "Second")); 
    things.insert(std::make_pair(Range(10.0, 15.0), "Third")); 

    transform(things.begin(), things.end(), ostream_iterator<string> (cout,""), dump); 

    cout << "--------------------------------------" << endl; 

    things[Range(1.5)] = "Revised First"; 

    transform(things.begin(), things.end(), ostream_iterator<string> (cout,""), dump); 


    return 0; 
} 

...程序的输出：

[0, 5) = 'First' 
[5, 10) = 'Second' 
[10, 15) = 'Third' 
-------------------------------------- 
[0, 5) = 'Revised First' 
[5, 10) = 'Second' 
[10, 15) = 'Third'