Контейнер диапазона C++ STL

Создайте класс DoubleRange для хранения двойного диапазона и реализуйте в нем операторы сравнения. Таким образом, std::map сделает все остальное за вас, используя класс DoubleRange в качестве ключа.

Я в основном согласен с Эрвикером в том, что вы можете определить диапазон. Теперь я за реализацию операторов с реальным значением (делайте то, что делают базовые типы: два диапазона сравниваются равными, если оба диапазона равны). Затем вы можете использовать третий параметр карты, чтобы передать ему функтор сравнения (или функцию), который решает вашу конкретную проблему с этой картой.

// Generic range, can be parametrized for any type (double, float, int...)
template< typename T >
class range
{
public:
    typedef T value_type;

    range( T const & center ) : min_( center ), max_( center ) {}
    range( T const & min, T const & max )
        : min_( min ), max_( max ) {}
    T min() const { return min_; }
    T max() const { return max_; }
private:
    T min_;
    T max_;
};

// Detection of outside of range to the left (smaller values):
//
// a range lhs is left (smaller) of another range if both lhs.min() and lhs.max() 
// are smaller than rhs.min().
template <typename T>
struct left_of_range : public std::binary_function< range<T>, range<T>, bool >
{
    bool operator()( range<T> const & lhs, range<T> const & rhs ) const
    {
        return lhs.min() < rhs.min()
            && lhs.max() <= rhs.min();
    }
};
int main()
{
    typedef std::map< range<double>, std::string, left_of_range<double> > map_type;

    map_type integer; // integer part of a decimal number:

    integer[ range<double>( 0.0, 1.0 ) ] = "zero";
    integer[ range<double>( 1.0, 2.0 ) ] = "one";
    integer[ range<double>( 2.0, 3.0 ) ] = "two";
    // ...

    std::cout << integer[ range<double>( 0.5 ) ] << std::endl; // zero
    std::cout << integer[ range<double>( 1.0 ) ] << std::endl; // one
    std::cout << integer[ 1.5 ] << std::endl; // one, again, implicit conversion kicks in
}

Вы должны быть осторожны с равенством и сравнениями между двойными значениями. Различные способы получения одного и того же значения (в реальном мире) могут давать несколько разные результаты с плавающей запятой.

Лучше использовать структуру данных Интервальное дерево. Boost имеет реализацию в Interval Container Library

Один из подходов состоит в том, чтобы заранее рассчитать «точки останова»:

typedef vector< tuple<double, double, foo*> > collisionlist_t;
const collisionlist_t vec;
vec.push_back(make_tuple(0.0, 3.0, ptr));
vec.push_back(make_tuple(3.5, 10.0, ptr2));
// sort 
std::map<double, foo*> range_lower_bounds;
for(collisionlist_t::const_iterator curr(vec.begin()), end(vec.end()); curr!=end; ++curr)
{
    /* if ranges are potentially overlapping, put some code here to handle it */
    range_lower_bounds[curr->get<0>()] = curr->get<2>();
    range_lower_bounds[curr->get<1>()] = NULL;
}

double x = // ...
std::map<double, foo*>::const_iterator citer = range_lower_bounds.lower_bound(x);

Еще одно предложение: используйте математическое преобразование для отображения индекса из REAL в INT, который можно сравнивать напрямую.

Если эти диапазоны многочисленны и плотны, существует также структура, известная как «дерево интервалов», которая может помочь.

Интервалы открытые, закрытые или полуоткрытые? Я буду считать закрытым. Обратите внимание, что интервалы не могут перекрываться по определению карты. Вам также понадобятся правила разделения, когда вставляется перекрывающийся интервал. правила должны решить, где происходит разделение, и должны учитывать эпсилон с плавающей запятой.

эта реализация использует map::lower_bound и НЕ использует класс в качестве домена карты

map::lower_bound возвращает итератор к первому элементу на карте со значением ключа, равным или превышающим значение указанного ключа. (т.е. наименьший ключ больше или равен K. Неудачный выбор имен методов STL, поскольку это наименьшая верхняя граница K.)

template <class codomain>
class RangeMap : private std::map<double,std::pair<double,codomain>{
public:
    typedef double domain;
    typedef std::map<double,std::pair<double,codomain>:: super;
    typename super::value_type value_type;
protected:
    static domain& lower(const value_type& v){
        return v.first;
    }

    static domain& upper(const value_type& v){
        return v.second.first;
    }

    static codomain& v(const value_type& v){
        return v.second.second;
    }

public:

    static const domain& lower(const value_type& v){
        return v.first;
    }
    static const domain& upper(const value_type& v){
        return v.second.first;
    }
    static const codomain& v(const value_type& v){
        return v.second.second;
    }


    static bool is_point(const value_type& vf) {
        return lower(v) == upper(v);
    }

    static bool is_in(const domain& d,const value_type& vf) {
        return (lower(v) <= d) && (d <= upper(v));
    }


    const_iterator greatest_lower_bound(const domain& d)const {
        const_iterator j = super::lower_bound(d);
        if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
                                             //remember j->first >= d because it was lower but its the first
        if(j==begin()) return end();//d < all intervals
        --j;                        //back up
        return j;
    }
    const_iterator find(domain& d) {
        const_iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }
    iterator greatest_lower_bound(const domain& d) {
        iterator j = super::lower_bound(d);
        if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
                                             //remember j->first >= d because it was lower but its the first
        if(j==begin()) return end();//d < all intervals
        --j;                        //back up
        return j;
    }
    const_iterator find(domain& d) const{
        iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }  //so much for find(d) 
    iterator find(domain& d){
        iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }  //so much for find(d) 

     struct overlap: public std::exception{
     };
     bool erase(const double lhep,const double rhep);
     //you have a lot of work regarding splitting intervals erasing when overlapped
     //but that can all be done with erase, and insert below. 
     //erase may need to split too
     std::pair<iterator,bool>
     split_and_or_erase_intervals(const double lhep,
                                  const double rhep, 
                                  const codomain& cd);
     //the insert method - note the addition of the overwrtite 
     std::pair<iterator,bool>
     insert(const double lhep,const double rhep,const codomain& cd,bool overwrite_ok){
          if( find(lhep)!=end() || find(rhep)!=end() ) {
              if(overwrite_ok){
                 return split_and_or_erase_intervals(const double lhep,
                                                     const double rhep, 
                                                     const codomain& cd);
              }
              throw overlap();
          }
          return insert(value_type(lhep,pair<double,codomain>(rhep,cd)));
     }
 };

Если ваши интервалы не должны перекрываться, вы должны добавить дополнительный код для проверки этого свойства во время вставки. В частности, свойство, которое вы хотите подтвердить, заключается в том, что ваш новый интервал полностью лежит в пределах диапазона, который ранее был пустым. Самый простой способ сделать это — разрешить два типа диапазонов: "занято" и "пусто". Вы должны начать с создания одной «пустой» записи, которая охватывает весь используемый диапазон. Вставка нового «занятого» диапазона требует:

(1) найти какое-либо значение в новом диапазоне.
(2) убедиться, что возвращаемый диапазон пуст и полностью охватывает ваш новый диапазон. (Это было обязательным утверждением выше)
(3) изменить возвращенный пустой диапазон так, чтобы его конец находился в начале вашего нового диапазона. (4) вставьте новый пустой диапазон, который начинается с конца нового диапазона и заканчивается старым концом возвращаемого диапазона.
(5) вставляете новый диапазон, будучи уверенным, что он окружен пустыми диапазонами.
(6) При вставке нового занятого диапазона, который не имеет пустого пространства, отделяющего его от других занятых диапазонов, могут возникнуть дополнительные угловые случаи.