0

一个类包含两个整数；这个类有两个实例。我想比较它们以确保两个实例包含相同的两个数字（它们的顺序无关紧要）。

我可以做这个：

bool operator==(const Edge &e, const Edge &f) {
    return ((e.p1 == f.p1) || (e.p1 == f.p2)) && ((e.p2 == f.p1) || (e.p2 == f.p2));
}

这是最好的方法吗？会有很多这样的比较，所以我想确保我做出最有效的选择。顺便说一句，该运算符将主要由std::unordered_set该类使用-以防此信息很重要。

4

4 回答 4

9

我认为你的逻辑有点混乱......如果我理解正确，给定对（a，b）和（x，y），你想检查（a，b）== s（x，y） , 对于一些排列 s?

bool operator==(const Edge &e, const Edge &f) {
    return ((e.p1 == f.p1) && (e.p2 == f.p2)) ||
           ((e.p2 == f.p1) && (e.p1 == f.p2));
}

至于性能......这里没有什么可以优化的。如果您的程序很慢，请去其他地方看看。

于 2013-05-17T04:27:11.233 回答
4

这可能不是最快的，它需要 C++11。但它又好又短：

bool operator==(const Edge& e, const Edge& f) {
  return std::minmax(e.p1, e.p2) == std::minmax(f.p1, f.p2);
}

它还建议了一种优化（我通常使用）：保持p1并按p2顺序排列，这样minmax就不需要每次都调用它。那么你确实有一个最佳解决方案。

于 2013-05-17T05:04:34.157 回答
2

这对两个人来说都可以。然而，再多一点，它显然很快就会变得非常难看。实际上，如果您以“幼稚”的方式执行此操作，则需要进行n!比较以检查何时有n变量。

一种更简单的方法如下所示：

static constexpr Edge::number()
{
    return <number_of_values>;
}

bool operator==(const Edge& e, const Edge& f)
{
    constexpr size = Edge::number();
    std::array<int, size> earr = {{e.p1, e.p2, ..., e.pn}};
    std::array<int, size> farr = {{f.p1, f.p2, ..., f.pn}};
    return std::is_permutation(earr.begin(), earr.end(), farr.begin());
}

如果它总是两个，你可以简单地写成：

bool operator==(const Edge& e, const Edge& f)
{
    std::array<int, 2> earr = {{e.p1, e.p2};
    std::array<int, 2> farr = {{f.p1, f.p2}};
    return std::is_permutation(earr.begin(), earr.end(), farr.begin());
}

测试无序相等与测试一个序列是否是另一个序列的排列相同。

编辑：这对我来说应该很明显，可以通过检查排序序列是否相等来进行测试。在上面替换std::is_permutation为std::sortand std::equal，这将O(n log n)代替O(n^2).

于 2013-05-17T04:30:56.547 回答
0

根据我对您问题的理解，我建议您采取以下解决方案：

只需在您的课程中添加功能，如下所示：

bool isExist(int point)
{
  if(this.p1==point || this.p2==point)
    return true;
  else
   return false;
}

您可以通过调用此函数来应用您的逻辑。

如果我错了，请纠正我...

于 2013-05-17T04:33:00.543 回答