8

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

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

所以我在std::mapxyz 上键入 aVector

class Vector
{ 
  float x,y,z
} ;

，我正在制作一个std::map<Vector, std::vector<Object*> >. 所以请注意这里的关键不是a 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) 例如）。

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

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

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

4

5 回答 5

6

您可以为地图提供自定义比较器，而不是operator<为您的键类定义。这是一个函数对象，它接受两个参数，true如果第一个在第二个之前就返回。像这样的东西：

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 是一个可以比较两个 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这正是你所需要的。不需要严格的弱排序。GCC 在命名空间中也有类似的东西tr1。或者去Boost.Unordered。

比较行人的无序对应物map或set给你两个好处：

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

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

因此，请继续使用：

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

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

PS：这些> >东西将在即将到来的标准以及未来的编译器版本中得到修复。

于 2010-08-18T18:36:29.937 回答
1

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

定义这种运算符的正常方法是通过（可能是朋友）自由函数。

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

现在，如果我需要从 aVector到 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 )
{
    ...
}

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

于 2010-08-18T18:32:21.260 回答