在 std::map 中使用（数学）向量

Question

相关：我可以使用什么作为std::map键？

我需要创建一个映射，将空间中的特定键位置映射到对象列表。 std::map 似乎是这样做的方法。

因此，我在 xyz Vector 上键入 std::map

class Vector
{ 
  float x,y,z
} ;

，并且我正在制作 std::map >。所以请注意这里的键不是一个std::vector，它是一个类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)。

我的问题是这确实是人为的，虽然我已经对其进行了编码并且它有效，但我发现它用这种非常奇怪的、人为的、非基于数学的“小于”概念“污染”了我的 Vector 类（数学上）为一个向量。

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

建议？欢迎开箱即用的解决方案！

Answer 1

您可以为映射提供自定义比较器，而不是为键类定义operator<。这是一个函数对象，它接受两个参数，如果第一个参数出现在第二个参数之前，则返回 true。像这样的事情：

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

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

Answer 2

您可以将其与班级分开。然后将其指定为 std::map 的比较运算符。

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

其中 Compare 是一个可以比较两个 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;
}

Answer 3

我认为 std::tr1::unordered_map 正是您所需要的。不需要严格的弱排序。 GCC 在 tr1 命名空间中也有类似的东西。或者选择 Boost.Unordered。

更简单的 map 或 set 的无序对应项为您提供了两个优点：

• 您不需要定义一个没有意义的小于运算符

• 哈希表的性能可能比平衡二叉树更好，后者是实现有序map 的首选方法或集合结构。但这取决于您的数据访问模式/要求。

因此，只需继续使用：

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

这将使用默认的哈希函数来处理地图的插入/搜索。

PS：> > 事情将在即将推出的标准以及未来的编译器版本中得到修复。

Answer 4

你发现你的班级被这个污染了，这是正常的。从CS的角度来看，它也受到了污染。

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

然而，要问自己的第一个问题是：这是否有意义。问题是您为您的类定义了一个方法，该方法仅在有限的上下文中有意义，但在任何地方都可以访问。这就是为什么“污染”的感觉开始出现。

现在，如果我需要从 Vector 到 Object 集合的映射，以下是我会问的问题我自己：

• 我需要订购 Vector 吗？是：std::map，否：std::unordered_map 或 std::tr1::unodered_map 或 std::hash_map 或 boost::unordered_map。
• 该集合是否拥有 Object ？是：boost::ptr_vector

现在，在这两种情况下（map 和 unordered_map），我需要一些东西来改变我的钥匙。该集合提供了一个采用 Functor 类型的补充模板参数。

请注意：正如另一个答案中提到的，浮点表示在计算机中很尴尬，因此您可能需要放宽相等的含义并忽略低位数字（多少取决于您的计算）。

Answer 5

我认为你的方法很好。如果您担心污染 Vector 类，那么我相信独立函数也能正常工作：

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

但请注意：您在这里所做的事情相当危险。浮点计算经常会出现错误。假设您在地图中插入一些点。然后计算一个点并检查地图以查看它是否在那里。即使从严格的数学角度来看，第二个点与第一个点相同，也不能保证您会在地图中找到它。