代码之家 › 专栏 › 技术社区 › bobobobo

在std::map中使用(数学)向量

stdmap operator-overloading math c++

bobobobo · 技术社区 · 15 年前

相关: what can I use as std::map keys?

我需要创建一个映射,其中空间中的特定关键位置映射到对象列表。 STD::地图 似乎是这样做的。

所以我在坚持 STD::地图 在XYZ上 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)和(-1,-1,1)>(-1,-1,-1)。

我的问题是这真的是人造的,虽然我已经对它进行了编码,而且它确实有效,但我发现它“污染”了我的向量类(数学上),用这个非常奇怪的、人工的、非数学基础的向量“小于”的概念。

但我需要创建一个映射,在这个映射中,空间中的特定关键位置映射到某些对象,而std::map似乎是实现这一点的方法。

建议?欢迎使用现成的解决方案!!

5 回复 | 直到 15 年前

Mike Seymour 15 年前

而不是定义 operator< 对于您的键类,您可以为映射提供一个定制的比较器。这是一个函数对象,它接受两个参数并返回 true 如果第一个在第二个之前。像这样:

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

typedef std::map<Vector, Value, CompareVectors> VectorValueMap;

Loki Astari 15 年前

你可以把它和课堂分开。然后将其指定为std::map的比较运算符。

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

其中,compare是一个可以比较两个向量对象的函数(或函数)。
我还认为您可以简化比较操作。

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

dirkgently 15 年前

我想 std::tr1::unordered_map 正是你需要的。不需要严格的弱排序。GCC在 tr1 命名空间也一样。或去 Boost.Unordered .

更为行人的无序同行 map 或 set 有两个优点:

不需要在没有意义的地方定义小于运算符
哈希表可能比平衡二叉树执行得更好,后者是实现有序二叉树的首选方法 地图 或 设置 结构。但这取决于您的数据访问模式/需求。

所以,只要继续使用:

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

这将使用一个默认的哈希函数来处理对映射的插入/搜索。

PS: > > Thingy将在即将到来的标准中修复,从而在未来的编译器版本中修复。

Matthieu M. 15 年前

你发现你的班级被这种污染是很正常的。从CS的角度来看,它也被污染了。

定义此类运算符的正常方法是通过(可能是友元)自由函数。

然而,首先要问自己的问题是:这是否有意义?问题是,您已经为类定义了一个方法,该方法只在有限的上下文中有意义,但在任何地方都可以访问。这就是为什么会有“污染”的感觉。

现在,如果我需要从 Vector 到一个集合 Object S,以下是我要问自己的问题:

我需要 矢量 要订购吗?对: std::map ,不: std::unordered_map 或 std::tr1::unodered_map 或 std::hash_map 或 boost::unordered_map .
这个收藏品会拥有 对象 ?对: boost::ptr_vector<Object> 或 std::vector< std::unique_ptr<Object> > ,不: std::vector<Object*>

现在,在这两种情况下( map 和 unordered_map ,我需要一些东西来转换我的钥匙。集合提供一个采用函数类型的补充模板参数。

注意:正如在另一个答案中提到的,浮点表示在计算机中很难理解,因此您可能需要放松相等的含义,忽略低阶数字(多少取决于您的计算)。

Peter Ruderman 15 年前

我认为你的方法很好。如果您担心污染向量类,那么我相信独立函数也可以工作:

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

但只要一句警告:你在这里所做的是相当危险的。在浮点计算中经常会出现错误。假设您在地图中插入了一些点。然后你计算一个点,检查地图看它是否在那里。即使从严格的数学角度来看,第二个点与第一个点相同,也不能保证你能在地图上找到它。