Контейнер диапазона STL C++
https://stackoverflow.com/questions/1089192
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я ищу контейнер, который отображает двойные указатели на объекты.Однако каждый ключ представляет собой просто диапазон двойников, соответствующих этому объекту.
Например, может существовать пара ключ/значение <(0.0 3.0), ptr> или <(3.5 10.0), ptr2>.
Контейнер[1.0] должен возвращать PTR, Контейнер[3.0] также должен возвращать PTR, а Контейнер[-1.0] должен быть неопределенным.
Есть ли какой-либо объект с подобным поведением по умолчанию или мне придется реализовать его самостоятельно?
Редактировать
Вот фактический код, который я написал, может быть, его будет проще отлаживать/давать советы по нему.
// Behavior: A range is defined mathematically as (min, max]
class dblRange
{
public:
double min;
double max;
dblRange(double min, double max)
{
this->min = min;
this->max = max;
};
dblRange(double val)
{
this->min = val;
this->max = val;
};
int compare(const dblRange rhs)
{
// 1 if this > rhs
// 0 if this == rhs
//-1 if this < rhs
if (rhs.min == rhs.max && min == max)
{
/*if (min > rhs.min)
return 1;
else if (min == rhs.min)
return 0;
else
return -1;*/
throw "You should not be comparing values like this. :(\n";
}
else if (rhs.max == rhs.min)
{
if (min > rhs.min)
return 1;
else if (min <= rhs.min && max > rhs.min)
return 0;
else // (max <= rhs.min)
return -1;
}
else if (min == max)
{
if (min >= rhs.max)
return 1;
else if (min < rhs.max && min >= rhs.min)
return 0;
else // if (min < rhs.min
return -1;
}
// Check if the two ranges are equal:
if (rhs.min == min && rhs.max == max)
{
return 0;
}
else if (rhs.min < min && rhs.max <= min)
{
// This is what happens if rhs is fully lower than this one.
return 1;
}
else if (rhs.min > min && rhs.min >= max)
{
return -1;
}
else
{
// This means there's an undefined case. Ranges are overlapping,
// so comparisons don't work quite nicely.
throw "Ranges are overlapping weirdly. :(\n";
}
};
int compare(const dblRange rhs) const
{
// 1 if this > rhs
// 0 if this == rhs
//-1 if this < rhs
if (rhs.min == rhs.max && min == max)
{
/*if (min > rhs.min)
return 1;
else if (min == rhs.min)
return 0;
else
return -1;*/
throw "You should not be comparing values like this. :(\n";
}
else if (rhs.max == rhs.min)
{
if (min > rhs.min)
return 1;
else if (min <= rhs.min && max > rhs.min)
return 0;
else // (max <= rhs.min)
return -1;
}
else if (min == max)
{
if (min >= rhs.max)
return 1;
else if (min < rhs.max && min >= rhs.min)
return 0;
else // if (min < rhs.min
return -1;
}
// Check if the two ranges are equal:
if (rhs.min == min && rhs.max == max)
{
return 0;
}
else if (rhs.min < min && rhs.max <= min)
{
// This is what happens if rhs is fully lower than this one.
return 1;
}
else if (rhs.min > min && rhs.min >= max)
{
return -1;
}
else
{
// This means there's an undefined case. Ranges are overlapping,
// so comparisons don't work quite nicely.
throw "Ranges are overlapping weirdly. :(\n";
}
};
bool operator== (const dblRange rhs ) {return (*this).compare(rhs)==0;};
bool operator== (const dblRange rhs ) const {return (*this).compare(rhs)==0;};
bool operator!= (const dblRange rhs ) {return (*this).compare(rhs)!=0;};
bool operator!= (const dblRange rhs ) const {return (*this).compare(rhs)!=0;};
bool operator< (const dblRange rhs ) {return (*this).compare(rhs)<0;};
bool operator< (const dblRange rhs ) const {return (*this).compare(rhs)<0;};
bool operator> (const dblRange rhs ) {return (*this).compare(rhs)>0;};
bool operator> (const dblRange rhs ) const {return (*this).compare(rhs)>0;};
bool operator<= (const dblRange rhs ) {return (*this).compare(rhs)<=0;};
bool operator<= (const dblRange rhs ) const {return (*this).compare(rhs)<=0;};
bool operator>= (const dblRange rhs ) {return (*this).compare(rhs)>=0;};
bool operator>= (const dblRange rhs ) const {return (*this).compare(rhs)>=0;};
};
Прямо сейчас у меня возникли проблемы с тем, чтобы карта принимала двойной ключ в качестве ключа, хотя операторы сравнения определены.
Вот некоторый управляющий код, который я использую, чтобы проверить, будет ли он работать:
std::map<dblRange, int> map;
map[dblRange(0,1)] = 1;
map[dblRange(1,4)] = 2;
map[dblRange(4,5)] = 3;
map[3.0] = 4;
Решение
Создать класс 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 имеет реализацию в Библиотека интервальных контейнеров
Одним из подходов было бы заранее рассчитать «точки останова»:
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, который можно напрямую сравнивать.
Если эти диапазоны многочисленны и плотны, существует также структура, известная как «дерево интервалов», которая может помочь.
Являются ли интервалы открытыми, закрытыми или полуоткрытыми?Я буду считать закрытым.Обратите внимание, что интервалы не могут перекрываться по определению карты.Вам также понадобятся правила разделения на случай вставки перекрывающегося интервала.правила должны решить, где происходит разделение, и должны учитывать эпсилон с плавающей запятой.
эта реализация использует карту::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) При вставке нового занятого диапазона, в котором нет пустого пространства, отделяющего его от других занятых диапазонов, могут возникнуть дополнительные угловые случаи.
