下午好,我正在尝试使用std::map lower_found成员函数。但是,它总是返回错误的答案。这是我的测试代码的摘录。请向我解释如何使std::map下界功能正确。谢谢。

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

最佳答案

IIUC,您正在处理范围,并且对
范围不重叠的 map 。如果是这样,您有
定义您的运算符发生剧烈变化(断言失败或异常)
如果出现重叠,则应避免插入这样的范围。
假设[low,high)的半开范围和
在Interval的构造函数中,高> =低,例如
以下应该工作:

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,find等
一个简单的整数作为键(而不是一个区间);他们在一起
定义int和an之间的严格排序关系
整数,IFF没有重叠的间隔,并且
等价关系,使得区间[i,j)中的所有n为
等于该范围,并且彼此相等。 (再次,如果有
有重叠的区间,没有等价关系,
并且行为是不确定的。)

关于c++ - std::map lower_bound is not returning the correct value,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/5381117/

10-09 06:39
查看更多