下午好,我正在尝试使用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/