std :: map lower_bound没有返回正确的值

下午好，我试图使用std :: map的lower_found成员函数。但是，它不断返回错误的答案。这是我的测试代码的摘录。请向我解释如何正确地制作std :: map下限功能。谢谢。std :: map lower_bound没有返回正确的值

class Interval { 
    public: 
     explicit Interval(int item){ 
      mLow = item; 
      mHigh = item; 
      mStamp = 0; 
     } 
     Interval(int low, int high, int stamp = 0){ 
      mLow = low; 
      mHigh = high; 
      mStamp = stamp; 

     } 
     Interval(void){ 
      mLow = 0; 
      mHigh = 0; 
      mStamp = 0; 

     } 

     Interval(const Interval& r): 
      mLow(r.mLow), 
      mHigh(r.mHigh), 
      mStamp(r.mStamp) 
     { 

     } 

     bool operator<(const Interval& rhs) const{  
      if (mLow < rhs.mLow){    
       return true;  
      }  
      return false; 
     } // operator<  
     int low() const { return mLow; } 
     int high() const { return mHigh; } 
     int getStamp() const { return mStamp; } 
     void setLow(int lower) { mLow = lower; } 
     void setHigh(int higher) { mHigh = higher; } 
     void setStamp(int stamp) { mStamp = stamp; } 
    private: 
     int mLow; 
     int mHigh; 
     int mStamp; 
}; // class Interval 


int main(int Argc_,char *Argv_[]) { 
    int n; 
    Interval r; 

    std::map<Interval, Interval> Intervals_type; 
    r.setLow(0); 
    r.setHigh(10); 
    r.setStamp(1); 
    std::pair< Interval, Interval > tmp(r,r); 
    Intervals_type.insert(tmp); 

    r.setLow(10); 
    r.setHigh(20); 
    r.setStamp(2); 
    std::pair< Interval, Interval > tmp2(r,r); 
    Intervals_type.insert(tmp2);  


    r.setLow(20); 
    r.setHigh(30); 
    r.setStamp(3); 
    std::pair< Interval, Interval > tmp3(r,r); 
    Intervals_type.insert(tmp3);  

    r.setLow(30); 
    r.setHigh(40); 
    r.setStamp(4); 
    std::pair< Interval, Interval > tmp4(r,r); 
    Intervals_type.insert(tmp4);  



    n = 36; 
    std::map<Interval, Interval>::const_iterator it = 
       Intervals_type.lower_bound(Interval(n)); 
    if (it == Intervals_type.end()){ 
     printf(" n = %d not found\n",n); 
    } 

    return 1; 
}

来源

2011-03-21 Frank

是什么让您认为它返回错误的结果？你能指望什么？它返回什么？ – ybungalobill 2011-03-21 17:15:02

你忘了告诉我们你期待什么结果，以及你实际得到了什么。我期望它打印“未找到”，因为36比地图中的所有键都大，所以lower_bound将返回end（）迭代器。 – 2011-03-21 17:17:14

你的程序打印什么，你期望打印什么？ – 2011-03-21 17:17:38

IIUC，你正在处理范围，并且你有一个范围不重叠的地图上的不变量。如果是这种情况，您可以使用来定义您的运营商<，以便它处理范围，并在重叠情况下确实会发生某种情况（断言失败或例外），以防止插入此类范围。假设一个半开范围[低，高）和断言高> =低间隔的构造，类似的以下应该工作：

struct CmpInterval 
{ 
    // For insertion... 
    bool operator<(Interval const& lhs, Interval const& rhs) const 
    { 
     assert(lhs.low >= rhs.high 
       || lhs.high <= rhs.low 
       || (lhs.low == rhs.low && lhs.high == rhs.high)); 
     return lhs.low < rhs.low; 
    } 
    // For find, lower_bound, etc. 
    bool operator<(Interval const& lhs, int target) const 
    { 
     return lhs.low < target; 
    } 

    bool operator<(int target, Interval const& rhs) const 
    { 
     return target <= rhs.high; 
    } 
};

最后两个用于LOWER_BOUND，找到等，当你通过一个简单的整数作为关键（而不是一个间隔）;在一起时，它们限定一个int和 Inteval之间的严格的排序关系，IFF没有重叠的时间间隔，以及等价关系，使得在一个间隔所有n [I，J）是等同于范围和对彼此。（同样，如果是重叠间隔，则不存在等价关系，且行为未定义。）

来源

2011-03-21 18:05:59

我刚接受你的回答。我现在会测试它，我记得在过去7年中阅读过你的C++职位。谢谢您的回复。 – Frank 2011-03-21 18:11:47

@Frank不客气。许多年前，我必须解决类似的问题（当C还在C级之前，它仍然是C）。我试图使我的解决方案适应std :: map接口，但我没有测试过任何东西，所以祝你好运。（另外，虽然它应该是显而易见的：该类型是映射的第三个模板参数。） – 2011-03-21 18:16:25

Kanze，是否可以使用STL类（除矢量以外）来处理重复间隔？我意识到，重复间隔或重叠间隔不存在等价关系？谢谢。 – Frank 2011-03-22 14:42:19

lower_bound应返回等于或大于第一项的位置之前的位置。地图中最大的项目实际上更小，因此返回结束。

在您的运营商<中，您只能检查mLow。如果您想检查36是否在30到40范围内，请更正您的运营商<。

来源

2011-03-21 17:19:01 Eelke

@Eelke，我接受了你的回答。我应该检查mHigh吗？我尝试过检查mHigh和mLow，但Microsoft STL implementationataion检查运算符<两次，一次使用原始参数，然后用此替换原始参数。谢谢。 – Frank 2011-03-21 17:34:10

@Eelke，我只是修复了操作符<以检查mLow和mHigh，现在程序运行正确。我想知道是否继续使用std :: map或者是否应该按照ybungabobill的建议切换到std :: multi_set。感谢您的回复。 – Frank 2011-03-21 18:08:08

@Frank，set或multi_set确实会更好地存储所有内容，两次没有任何用处。（set和map不允许重复，multi_map和multi_set） – Eelke 2011-03-21 19:35:05

std::map仅与operator <进行比较，因此它只知道Interval::mLow，有效地将所有间隔视为[mLow，∞）。你正在使用错误的容器。可以用地图来完成，但这很难。改为使用Boost.Icl。

编辑：你在STL中为此目的最好的东西是std :: multi_set。通过右端点订购你的时间间隔：

 bool operator<(const Interval& rhs) const{  
     return mHigh < rhs.mHigh; 
    }

现在你可以这样来做：

std::multi_set<Interval> cont; 
cont.insert(Interval(0,10,1)); 
cont.insert(Interval(10,20,2)); 
cont.insert(Interval(20,30,3)); 
cont.insert(Interval(30,40,4)); 

std::multi_set<Interval>::const_iterator iter = cont.lower_bound(Interval(36)); 
if(iter == cont.end() || iter->low() > 36) 
    // not found 
else 
    // found

来源

2011-03-21 17:22:12 ybungalobill

@ybungalobill，我接受了你的回答。什么是适当的STL容器使用？我相信STL在std :: set或std :: map中使用平衡二叉树。在获得最新的Solaris，IBM AIX和HPUX许可证之前，我无法使用Boost。谢谢。 – Frank 2011-03-21 17:29:38

不错，我不记得在Boost里有这样的东西。 – 2011-03-21 17:32:14

@Frank：见编辑。 – ybungalobill 2011-03-21 17:36:02

的lower_bound的定义是，它会返回在那里你可以插入项目，还是一个位置保持容器分类。您的比较功能仅适用于low会员;您的货柜的内容0,10,20,30为低点。保持容器排序的唯一插入点是36。

来源

2011-03-21 17:27:17

我刚接受你的回答。感谢您解释如何定义lower_bound。 – Frank 2011-03-21 17:50:36

std :: map lower_bound没有返回正确的值

回答

相关问题