8

関連:キーとして何を使用できますか?std::map

空間内の特定の主要な位置がオブジェクトのリストにマッピングされるマッピングを作成する必要がありました。 std::mapやり方だったようです。

だから私はstd::mapxyzにキーを打っていますVector

class Vector
{ 
  float x,y,z
} ;

、そして私は を作っていstd::map<Vector, std::vector<Object*> >ます。したがって、ここでのキーは ではなく、std::vectorそのオブジェクトはclass Vector、私自身が作成した数学 xyz ベクトルであることに注意してください。

「厳密に弱い順序付け」を生成するために、次のオーバーロードを に記述しましたoperator<。

  bool Vector::operator<( const Vector & b ) const {
    // z trumps, then y, then x
    if( z < b.z )
    {
      return true ;
    }
    else if( z == b.z )
    {
      if( y < b.y )
      {
        // z == b.z and y < b.y
        return true ;
      }
      else if( y == b.y )
      {
        if( x < b.x )
        {
          return true ;
        }
        else if( x == b.x )
        {
          // completely equal
          return false ;
        }
        else
        {
          return false ;
        }
      }
      else
      {
        // z==b.z and y >= b.y
        return false ;
      }
    }
    else
    {
      // z >= b.z
      return false ;
    }
  }

少し長いですが、基本的には、どのベクトルも一貫して他のどのベクトルよりも小さいと言えるようになっています ((-1, -1, -1) < (-1,-1,1), and (-1, - 1, 1) > (-1,-1,-1) など)。

私の問題は、これは本当に人為的であり、コード化して機能しますが、この本当に奇妙で人為的な非数学ベースの「未満」の概念で、Vector クラスを (数学的に) 「汚染」していることに気付きました。ベクトルの場合。

しかし、空間内の特定のキー位置が特定のオブジェクトにマップされるマッピングを作成する必要があり、std::map がそれを行う方法のようです。

提案？すぐに使えるソリューションを歓迎します!!

4

5 に答える 5

6

operator<キー クラスを定義する代わりに、マップにカスタム コンパレータを指定できます。trueこれは、2 つの引数を取り、最初の引数が 2 番目の引数の前にある場合に戻る関数オブジェクトです。このようなもの：

struct CompareVectors
{
    bool operator()(const Vector& a, const Vector& b)
    {
        // insert comparison code from question
    }
};

typedef std::map<Vector, Value, CompareVectors> VectorValueMap;
于 2010-08-18T18:35:01.877 に答える
4

クラスから切り離すことができます。次に、それを std::map の比較演算子として指定します。

std::map<Vector,std::vector<Object*>,Compare>  data;

Compare は、2 つの Vector オブジェクトを比較できる関数 (またはファンクター) です。
また、比較操作を簡素化できると思います。

bool Compare<( const Vector& lhs, const Vector& rhs)
{
   // z trumps, then y, then x
   if( lhs.z < rhs.z )
   {    return true ;
   }
   else if (lhs.z > rhs.z)
   {    return false;
   }
   // Otherwise z is equal
   if( lhs.y < rhs.y )
   {    return true ;
   }
   else if( lhs.y > rhs.y )
   {    return false;
   }
   // Otherwise z and y are equal
   if ( lhs.x < rhs.x )
   {    return true;
   }
   /* Simple optimization Do not need this test
      If this fails or succeeded the result is false.
   else if( lhs.x > rhs.x )
   {    return false;
   }*/
   // Otherwise z and y and x are all equal
   return false;
}

小さいか大きいかをテストしてから、等しいかどうかをテストしていることに注意してください。個人的にはこのスタイルのシンプルさが好きです。しかし、これが次のように圧縮されているのをよく見かけます。

bool Compare<( const Vector& lhs, const Vector& rhs)
{
    // Note I use three separate if statements here for clarity.
    // Combining them into a single statement is trivial/
    //
    if ((lhs.z < rhs.z)                                        ) {return true;}
    if ((lhs.z == rhs.z) && (lhs.y < rhs.y)                    ) {return true;}
    if ((lhs.z == rhs.z) && (lhs.y == rhs.y) && (lhs.x < rhs.x)) {return true;}

    return false;
}
于 2010-08-18T18:53:47.620 に答える
1

std::tr1::unordered_map必要なものだけだと思います。厳密な弱い順序付けは必要ありません。tr1GCC には名前空間にも似たようなものがあります。またはBoost.Unorderedに行きます。

mapより歩行者のorの順序付けられていない対応物には、次のset2 つの利点があります。

  • 意味をなさない小なり演算子を定義する必要はありません

  • mapハッシュ テーブルは、バランスの取れたバイナリ ツリーよりも優れたパフォーマンスを発揮する可能性がありますset。ただし、それはデータアクセスのパターン/要件によって異なります。

だから、先に進んで使用してください：

typedef std::tr1::unordered_map<Vector, std::vector<Object *> > VectorMap;

これにより、マップの挿入/検索を処理するデフォルトのハッシュ関数が使用されます。

PS: この> >問題は、今後の標準で修正されるため、将来のコンパイラ バージョンで修正される予定です。

于 2010-08-18T18:36:29.937 に答える
1

クラスがこれによって汚染されていることに気付くのは普通のことです。CSの観点からも汚染されています。

そのような演算子を定義する通常の方法は、(潜在的にフレンド) フリー関数を使用することです。

しかし、自問する最初の質問は次のとおりです。それは理にかなっていますか。問題は、限られたコンテキストでのみ意味を持ち、どこからでもアクセスできるクラスのメソッドを定義したことです。だから「汚染」感が出る。

Vectorここで、aから s のコレクションへのそのようなマッピングが必要な場合Object、次の質問を自問します。

  • Vectorを注文する必要がありますか? はい: std::map、いいえ:std::unordered_mapまたはstd::tr1::unodered_mapまたはstd::hash_mapまたはboost::unordered_map.
  • このコレクションは を所有しObjectますか? はい:boost::ptr_vector<Object>またはstd::vector< std::unique_ptr<Object> >、いいえ:std::vector<Object*>

さて、どちらの場合でも (mapとunordered_map)、キーを変換するために何かが必要になります。コレクションは、Functor 型を取る補足テンプレート引数を提供します。

注意：別の回答で述べたように、浮動小数点表現はコンピューターでは扱いにくいため、おそらく等値の意味を緩和し、下位桁を無視する必要があります（計算に応じて数が異なります）。

于 2010-08-19T06:42:31.163 に答える
0

あなたのアプローチはいいと思います。Vector クラスの汚染が心配な場合は、スタンドアロン関数も同様に機能すると思います。

bool operator<( const Vector& lhs, const Vector& rhs )
{
    ...
}

ただし、ここで行っていることはかなり危険です。浮動小数点の計算にはしばしばエラーがあります。マップにポイントを挿入するとします。次に、ポイントを計算し、マップをチェックして、そこにあるかどうかを確認します。厳密に数学的な観点から、2 番目のポイントが最初のポイントと同じであったとしても、それがマップ内で見つかるという保証はありません。

于 2010-08-18T18:32:21.260 に答える