0

我正在编写一些代码，其中存储了许多我想根据设定标准取回的对象。所以对我来说，使用带有对象作为键的地图是有意义的。对象将包含“设置标准”的位置。

这是我正在处理的对象类型的简化示例：

    class key
    {
         int x,y,w,h;
    }
    class object
    {
       ...
    }
    std::map<key, object, KeyCompare> m_mapOfObjects;

很简单，首先想到的是创建一个这样的比较函数：

    struct KeyCompare
    {
       bool operator()(const key &a, const key &b)
       {
            return a.x < b.x || a.y < b.y || a.w < b.w || a.h < b.h;
       } 
    }

但后来我认为这回归真实的机会非常高。所以我认为这会导致树非常不平衡，因此搜索速度很慢。

我主要担心的是，据我了解，std::map 以这种方式使用该函数： if(keyCompare(a,b)) { //left side } else if (keyCompare(b,a)) { // right side } else { //equal } 所以我不能只使用 ax < bx，因为这样任何具有相同 x 的东西都会被认为是相等的，这不是我想要的。我不介意以这种方式订购它，但它的“相等”位我似乎无法在不使其不平衡的情况下解决。

我认为将它们全部相乘是不可以的，原因很明显。

所以我能想出的唯一解决方案是根据信息创建一个“UID”：

    typedef long unsigned int UIDType; 
    class key
    {           
        private:
        UIDType combine(const UIDType  a, const UIDType b) 
        {
            UIDType times = 1;
            while (times <= b)
            times *= 10;
            return (a*times) + b;
        } 

        void AddToUID(UIDType number)
        {
            if(number < m_UID)
            {
                m_UID = combine(number, m_UID);
            }
            else
            {
                m_UID = combine(m_UID, number);
            }
        }
        UIDType UID;
        public:
        int x,y,w,h;
        key()
        {
            AddToUID(x);
            AddToUID(y);
            AddToUID(w);
            AddToUID(h);
        }
    }
    struct KeyCompare
    {
       bool operator()(const key &a, const key &b)
       {
            return a.UID < b.UID;
       } 
    }

但这不仅让人觉得有点 hacky，“long unsigned int”还不足以容纳潜在的数字。我可以把它放在一个字符串中，但是速度在这里是一个问题，我认为 std::string < 很昂贵。总的来说，虽然我越小可以使这个对象越好。

我想知道是否有人对如何更好地做到这一点有任何建议。也许我需要使用 std::map 以外的东西，或者可能还有另一个重载。或者也许我在这里遗漏了一些明显的东西。我真的觉得我过于复杂了，也许我真的用地图在错误的树上吠叫。

当我写这篇文章时，我突然想到除法是获得“唯一”数字的另一种方式，但也可能等于非常大的数字

4

2 回答 2

2

您只需要实现一个严格的弱排序，您可以轻松地使用它来实现std::tie，它有一个小于比较operator<的执行字典比较：

#include <tuple>

struct KeyCompare
{
   bool operator()(const key& a, const key& b) const
   {
        return std::tie(a.x, a.y, a.w, a.h) < std::tie(b.x, b.y, b.w, b.h);
   } 
}

如果您没有所需的 C++11 支持，则可以使用std::tr1::tie来自<tr1/tuple>boost 库的或等效版本。

于 2013-04-24T16:44:55.847 回答
0

我觉得 juanchopanza 有一个非常好的解决方案，对于那些没有 C++11 支持或 boost 库的人来说

我找到了一个非常简单的解决方案： 为类元素定义字典比较的最简单方法是什么？

这个解决方案对我的特定问题的工作比元组好一点（因为我也有一个我想考虑的值数组）。但我强烈建议将来考虑元组，我也会。

    struct keyCompare
    {
          bool operator()(const key &a, const key&b)
          {   
            if(a.x != b.x) return a.x < b.x;
            if(a.y != b.y) return a.y < b.y;
            if(a.w != b.w) return a.w < b.w;
            if(a.h != b.h) return a.h < b.h;

            return false; //they must be equal 
          }   
    }

感谢 juanchopanza 的回答以及其他任何看过的人

于 2013-04-25T10:09:36.477 回答