4

double からオブジェクト ポインターにマップするコンテナーを探しています。ただし、各キーは、そのオブジェクトに対応する 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;
4

7 に答える 7

6

double 範囲を格納するクラスを作成し、DoubleRangeそれに比較演算子を実装します。そうstd::mapすれば、DoubleRangeクラスをキーにして残りの作業が行われます。

于 2009-07-06T21:01:55.670 に答える
2

インターバル ツリーデータ構造を使用することをお勧めします。Boost はInterval Container Libraryに実装されています

于 2013-12-06T13:35:05.407 に答える
0

間隔が重複しないようにする必要がある場合は、挿入時にこのプロパティを確認するためのコードを追加する必要があります。具体的には、アサートしたいプロパティは、新しい間隔が以前は空だった範囲内に完全にあることです。これを行う簡単な方法は、 「占有」と「空」の2種類の範囲を許可することです。使用可能な範囲全体をカバーする単一の「空の」エントリを作成することから始める必要があります。新しい「占有」範囲を挿入するには、次のものが必要です。

（1）新しい範囲内の値を検索します。
（2）返された範囲が空であり、新しい範囲を完全に網羅していることを確認します。（これは上記の必須のアサーションでした）
（3）返された空の範囲を変更して、その終わりが新しい範囲の先頭になるようにします。（4）新しい範囲の終わりで始まり、返された範囲の古い終わりで終わる新しい空の範囲を挿入します。
（5）空の範囲に囲まれていることを確認して、新しい範囲を挿入します。
（6）他の占有範囲から分離する空きスペースのない新しい占有範囲を挿入する場合、追加のコーナーケースが存在する可能性があります。

于 2012-08-09T15:21:50.130 に答える
0

別の提案: 数学的変換を使用して、インデックスを REAL から直接比較できる INT にマップします。

これらの範囲が複数で密集している場合は、「間隔ツリー」と呼ばれる構造が役立つ場合があります。

于 2009-07-08T05:35:30.973 に答える
0

間隔は開いているか、閉じているか、半分開いていますか? 閉店とさせていただきます。マップの定義により、間隔をオーバーラップできないことに注意してください。また、オーバーラップ間隔を挿入する場合の分割ルールも必要になります。ルールは、分割が行われる場所を決定する必要があり、浮動小数点イプシロンを考慮に入れる必要があります。

この実装は map::lower_bound を使用し、マップのドメインとしてクラスを使用しません

map::lower_bound は、指定されたキーの値以上のキー値を持つマップ内の最初の要素への反復子を返します。(つまり、K 以上の最小のキー。K の最小の上限であるため、STL メソッド名の残念な選択です。)

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)));
     }
 };
于 2009-08-25T09:00:53.367 に答える
0

1つのアプローチは、事前に「ブレークポイント」を計算することです。

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);
于 2009-07-06T22:17:38.903 に答える