std :: map lower_bound не возвращает правильное значение

Question

Добрый день, я пытаюсь использовать функцию-член 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;
}

Answer 1

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

Answer 2

IIUC, вы имеете дело с диапазонами, и у вас есть инвариант на карте, диапазоны которого не перекрываются.Если это так, вы должны определить свой оператор <так, чтобы он работал с диапазонами и делал что-то радикальное (ошибка утверждения или исключение) в случае наложения, чтобы предотвратить вставку таких диапазонов.Принимая наполовину открытый диапазон [low, high) и утверждение, что high> = low в конструкторе 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 и Inteval, IFF нет перекрывающихся интервалов и отношение эквивалентности, так что все n в интервале [i, j) эквивалентны этому диапазону идруг другу.(Опять же, если есть перекрывающиеся интервалы, отношения эквивалентности не существует, и поведение не определено.)

Answer 3

Определение lower_bound состоит в том, что он возвращает местоположение, в которое вы можете вставить элемент и при этом сохранить контейнер отсортированным.Ваша функция сравнения работает только с членом low;Ваш контейнер имеет содержимое 0,10,20,30 для минимумов.Единственная точка вставки для 36, которая сохраняет отсортированный контейнер, находится в самом конце.

Answer 4

lower_bound должен вернуть позицию перед первым элементом, который равен или больше.Самый большой элемент на вашей карте на самом деле меньше, поэтому end возвращается.

У вашего оператора <вы проверяете mLow.Если вы хотите проверить, что 36 находится в диапазоне от 30 до 40, исправьте ваш оператор <. </p>