C ++ STL Range Container

Question

I am looking for a container that maps to a double pointer to an object. However, each key is simply a doubling range that matches this object.

For example, there may be a pair of keys / values ​​that are <(0,0 3,0), ptr> or <(3,5 10,0), ptr2>

container [1.0] should return ptr, container [3.0] should also return ptr, and container [-1.0] should be undefined.

Is there any object with similar default behavior or should I implement it myself?

Edit

Here's the real code I wrote, it may be easier to debug / offer advice on it.

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

Now I have a problem with the fact that the card accepts a double key, even if comparison operators are defined.

Here is some code that I use to check if it will work:

 std::map<dblRange, int> map; map[dblRange(0,1)] = 1; map[dblRange(1,4)] = 2; map[dblRange(4,5)] = 3; map[3.0] = 4; 

Answer 1

Create a DoubleRange class to hold the double range and implement comparison operators on it. That way, std::map does the rest for you, with the DoubleRange class as the key.

Answer 2

I basically agree with Earwicker that you can define a range. Now I am in favor of implementing operators with a real value (do what the basic types do: two ranges are compared the same if both ranges are equal). Then you can use the third parameter of the map to pass it a comparison functor (or function) that solves your specific problem with that map.

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

You must be careful with equality and comparison between double values. Different ways to get the same value (in the real world) can give slightly different floating point results.

Answer 3

It is better to use the interval tree data structure. Boost has an implementation in the Interval Container Library

Answer 4

One approach would be to calculate the “break points” in front of the hand:

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

Answer 5

Another suggestion: use a mathematical transformation to map an index from REAL to INT, which can be directly compared.

If these ranges are multiple and dense, a structure known as the "spanning tree" can also be created there.

Answer 6

Are the intervals open or closed or half open? I will consider it closed. Please note that intervals cannot overlap by map definition. You will also need splitting rules when one inserts an additional snap interval. the rules should decide where the separation occurs, and should take into account the floating point epsilon.

this implementation uses map :: lower_bound and DOES NOT use the class as a map area

map :: lower_bound returns an iterator to the first element on the map with a key value that is equal to or greater than the specified key. (i.e., the smallest key greater than or equal to K. An unfortunate choice of STL method names since it is the smallest upper bound of 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))); } }; 

Answer 7

If your intervals should be non-overlapping, you must add additional code to verify this property during insertion. In particular, the property you want to assert is that your new interval lies entirely within the range that was previously empty. An easy way to do this is to allow two types of ranges: busy and empty. You should start by creating a single “empty” entry that spans the entire range of usage. Inserting a new "busy" range requires:

(1) find some value in the new range.
(2) make sure the return range is empty and fully cover your new range. (This was the required statement, above)
(3) change the returned empty range so that its end is at the beginning of your new range. (4) insert a new empty range that starts at the end of your new range and ends at the old end of the returned range.
(5) insert a new range, sure that it is surrounded by an empty range.
(6) When inserting a new occupied range, there may be additional angular scales that do not have an empty space separating it from other occupied ranges.