具有结构体键的std :: map的高效比较器

Question

我有一个以下类型的结构体，我计划将其用作映射中的键。因此，我编写了以下比较器。我想知道是否有更优雅且高效的方法来实现这一点。
也许可以使用std::pair或其他方法。

struct T 
{
  int a, b, c, d;

  bool operator< (const T& r) {
    if (a < r.a)
       return true
    else if (a == r.a)
       if (b < r.b)
          return true;
       else if (b == r.b)
            if (c < r.c) 
                return true;
            else if (c == r.c)
                if (d < r.d)
                   return true;
    return false;
  }
}

- AMM

Answer 1

你能使用C++11吗？如果可以：

struct T {
    int a, b, c, d;

    bool operator<(const T& rhs) const {
        return tied() < rhs.tied();
    }

private:
    std::tuple<int, int, int, int> tied() const {
        return std::make_tuple(a, b, c, d);
    }
};

或者，我更喜欢在每个可能的机会上使用return来避免容易出错的嵌套写法:

bool operator<(const T& rhs) const {
    if (a != rhs.a) return a < rhs.a;
    if (b != rhs.b) return b < rhs.b;
    if (c != rhs.c) return c < rhs.c;
    return d < rhs.d;
}

- Barry

---

很遗憾，没有C++11。 - AMM

Answer 2

你可以使用...

bool operator<(const T& r)
{
    return a < r.a ||
           a == r.a && (b < r.b || 
                        b == r.b && (c < r.c || 
                                     c == r.c && d < r.d));
}

或者...

    return a != r.a ? a < r.a :
           b != r.b ? b < r.b :
           c != r.c ? c < r.c :
                      d < r.d;

---

你说过你不使用C++11，而Barry有一个很好的元组方法的例子，但是为了将来的参考和其他感兴趣的人，只需一些可重用的支持代码...

bool less_by_pairs()
{
    return false;
}

template <typename T, typename U, typename ...Args>
bool less_by_pairs(const T& v1, const U& v2, Args... args)
{
    return v1 != v2 ? v1 < v2 : less_by_pairs(args...);
}

...你可以更轻松地实现这样的运算符...

bool operator<(const T& r)
{
    return less_by_pairs(a, r.a, b, r.b, c, r.c, d, r.d);
}

你可以做类似的事情，提供一个成员列表进行比较，但是那种表示法实际上有点冗长。

- Tony Delroy

Answer 3

您可以使用另一个字段来存储一个键。该键值可以通过一个公式生成，该公式以 (a,b,c,d) 作为输入。

例如：

void hash()
{
    key = (a ^ b ^ c ^ d);
}

作为结果，您只需要比较此键即可知道内容是否相同。

- gibertoni

---

这是一个 std::map，我们需要按排序顺序放置值。这不会区分 (0,0,0,1) 和 (1,0,0,0)。 - Barry

@Barry 那是真的。我的错。 - gibertoni