logo标签列表

C++ STL范围容器

c++stlrangecontainers
4
我正在寻找一个容器，它将double映射到对象指针。但是，每个键都只是对应于该对象的一系列双重范围。
例如，可能会有一个键/值对，即<(0.0 3.0)，ptr>，或<(3.5 10.0)，ptr2> container[1.0]应返回ptr，container[3.0]也应返回ptr，并且container[-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;};

};

现在我遇到了问题，即使比较运算符已经定义，地图仍然无法接受double作为键。

这是我用来测试是否可行的一些驾驶代码：

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

map[3.0] = 4;
你的比较成员函数都应该标记为const。 - Eric
我有两个集合，但是我选择其中一个，而不是在这里复制代码。 - Andrei Krotkov
我相信我的代码现在已经正确了 - 有人可以验证一下吗？ - Andrei Krotkov
1
一般意见，应该只有一个比较方法（const版本，因为它不改变内容）。 所有二元运算符都可以作为自由函数实现（这将使它们对编译器具有对称性），并以比较函数为参数（如果公共）。 比较应将“其他”参数作为引用接收。 避免使用==比较浮点数，因为它容易出错（相同的数字可能因计算方式而异）。 构造函数中优先使用初始化列表而不是赋值。 调试时，迭代地遍历map并按顺序打印所有值。 - David Rodríguez - dribeas
谢谢，dribeas。将其作为参考进行比较是一个好主意。在这种情况下，浮点数是从文件中加载的，从未明确计算，因此==应该没问题。我个人更喜欢赋值而不是初始化列表，并且调试由IDE处理。 - Andrei Krotkov
“prefer”不在其中。在许多情况下，初始化列表是正确的选择，而赋值则不然。所以要习惯这种方式。 :) - jalf
7个回答
14

我大部分同意Earwicker的观点，即你可以定义一个范围。现在，我支持使用真正含义实现运算符（做基本类型所做的事情：如果两个范围相等，则两个范围比较相等）。然后，您可以使用第三个映射参数将其传递给比较函数器（或函数），以解决此映射的特定问题。

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

在处理双精度值的相等性和比较时，您必须小心。在现实世界中使用不同的方式得到相同的值可能会产生略微不同的浮点结果。

6
创建一个名为DoubleRange的类来存储double类型范围，并在其上实现比较运算符。这样，使用DoubleRange类作为键，std::map就会自动处理其他操作。
更具体地说，每个比较会意味着什么？使用operator==和单个双重检查是否在范围内的double类型进行比较吗？ - Andrei Krotkov
2
你需要为DoubleRange提供一个构造函数，该函数接受一个double类型的参数，并将其分配给范围的两端。如果一个范围与另一个范围重叠（存储在映射中的键需要是非重叠的），则需要使==返回true。 - Daniel Earwicker
1
operator< 是 std::map 应该使用的全部 -- "a == b" 必须等同于 !(a<b) & !(b<a)。 - Alex Martelli
1
你应该小心使用这种方法，定义<可能会导致无限循环或意外覆盖，如果你的范围重叠（由于这些是浮点数，如果你的端点不能精确表示，即使你不希望它发生，你也可能有重叠的边界）。 - Todd Gardner
还可以直接使用boost::numeric::interval。 - Jepessen
显示剩余7条评论
2
0
一种方法是预先计算“断点”：
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);
我考虑过这种方法，但我想采用更直观的方式，就像我的驱动代码所展示的那样。如果我能让它正常工作，那我更喜欢这个方法。 - Andrei Krotkov
0

这些区间是开区间还是闭区间还是半开区间？我会假设是闭区间。请注意，根据映射的定义，这些区间不能重叠。当插入一个重叠的区间时，您还需要拆分规则。这些规则需要决定拆分发生的位置，并且必须考虑浮点数epsilon。

此实现使用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)));
     }
 };
0
另一个建议：使用数学变换将索引从 REAL 映射到 INT，以便可以直接进行比较。
如果这些范围是多个和密集的，则还有一种称为“区间树”的结构可能会有所帮助。
0
如果您的时间间隔必须是不重叠的，则必须添加一些额外的代码，在插入时间验证此属性。具体来说，您要断言的属性是新时间间隔完全位于以前为空的范围内。一种简单的方法是允许“占用”和“空闲”两种类型的范围。您应该首先创建一个覆盖整个可用范围的单个“空”条目。插入新的“占用”范围需要：
(1) 在新范围内查找某个值。 (2) 确保返回的范围为空，并完全包含您的新范围。(这是上述所需的断言) (3) 修改返回的空范围，使其结束时位于您的新范围的开头。 (4) 插入一个新的空范围，它从您的新范围的末尾开始，到返回范围的旧末尾结束。 (5) 插入您的新范围，确信它被空范围包围。 (6) 当插入一个与其他占用范围没有空白分隔的新占用范围时，可能还有其他角落情况。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接