C++带任意比较器的集合

Question

C++带任意比较器的集合

4

我有以下的C++代码：

#include <set>
#include <string>
#include <iostream>
using namespace std;

class Pair {
  public:
    string lhs;
    string rhs;
    Pair();
    Pair( string l, string r ) {
      lhs=l;
      rhs=r;
    };
};

struct compare {
  bool operator()(const Pair& a, const Pair& b) const{
    if ( ( a.lhs == b.lhs && a.rhs == b.rhs ) || ( a.lhs == b.rhs && a.rhs == b.lhs ) ) {
      cout << "MATCH" << endl;
    }
    return ( a.lhs == b.lhs && a.rhs == b.rhs ) || ( a.lhs == b.rhs && a.rhs == b.lhs );
  }
};

int main () {
  set<Pair, compare > s;
  Pair p( string("Hello"), string("World") );
  s.insert(p);
  cout << s.size() << "\n";
  Pair q( string("World"), string("Hello") );
  s.insert(q);
  cout << s.size() << "\n";
  compare cmp;
  cout << cmp( p, q );

  return 0;
}

调用编译后的代码会产生以下结果：

1
MATCH
MATCH
2
MATCH

一些原因导致集合s最终包含了两个被比较器认为是相同的Pair p和q。为什么会这样呢？

非常感谢您的帮助！

更新：感谢大家的回答和专业的帮助。正如你们可能已经猜到的那样，我是一个相对新手的C++程序员。

不管怎样，我想知道Antoine的答案是否可以使用lambda表达式实现？

像这样：

std::set< …, [](){ my_comparator_code_here } > s;

????

- user3139868

我的答案有一个快速、简单且正确的解决方案，只需添加一个 "!" :) - user3125280

我的回答很快、简单，但是不正确——但我已经修正了它。 - user3125280

4个回答

3

一个用于set、map或任何需要排序的算法，如lower_bound或sort的比较器需要实现一个严格弱序（基本上表现得像<）。

这种排序需要满足三个属性：

- 非自反：永远为真的条件是not (a < a) - 非对称性：如果a < b，那么就应该排除b < a - 传递性：如果a < b和b <c ，则可以推断出a <c 你需要翻译的内容中并没有 < 操作符，所以没有排序效果。

这样的排序定义了等价类，即根据排序相等的元素组（即验证了not (a < b)和not (b < a)）。在set或map中，每个等价类只能插入一个元素，而multiset或multimap可以保持多个元素。

如果你查看你的比较器，你会发现你已经实现了==，它没有定义任何排序。你需要实现类似于<的东西。

一个简单但非常有效的技巧是使用元组，它们已经以字典顺序实现了<（和==和任何其他比较运算符）。因此，std :: tuple 正好具有您想要的顺序；更好的是，

std :: tuple 也具有该顺序，并且可以使用std :: tie方便地构建。
因此，一个直接的比较器的实现就像这样：
struct comparator {
    bool operator()(Pair const& left, Pair const& right) const {
        return std::tie( left.a,  left.b)
             < std::tie(right.a, right.b);
    }
};


注：虽然没有被广泛讨论，但比较器的排序在调用时是稳定的绝对必要的。因此，它通常只应该取决于元素的值，而不是任何外部或运行时相关的东西（例如它们在内存中的地址）。



编辑：如上所述，您的比较器稍微复杂一些。

在您的情况下，您还需要考虑到a和b具有对称角色。一般来说，建议在对象的构造函数中将表示唯一化；如果不可能，可以先进行唯一化，再进行比较：

struct comparator {
    bool operator()(Pair const& left, Pair const& right) const {
        auto uleft = left.a < left.b ? std::tie(left.a, left.b)
                                     : std::tie(left.b, left.a);
        auto uright = right.a < right.b ? std::tie(right.a, right.b)
                                        : std::tie(right.b, right.a);

        assert(get<0>(uleft) <= get<1>(uleft) and "Incorrect uleft");
        assert(get<0>(uright) <= get<1>(uright) and "Incorrect uright");

        return uleft < uright;
    }
}; // struct comparator

- Matthieu M.

{"hello" "world"}, {"world" "hello"} 仍应为 false。 - user3125280

如果lhs和rhs在其顺序上不是唯一的（如OPs原始运算符所示），那该怎么办？这个是否足够呢？-->

return (std::tie( left.a,  left.b) < std::tie(right.a, right.b)) || (std::tie( left.a,  right.b) < std::tie(right.a, left.b))

- woosah

@woosah 这将使得 ("a", "b") < ("a", "b")。 - user3125280

1

@woosah: 实际上你需要更加聪明一些，在比较项之前使表示唯一化。这需要写得多一点，但并不是那么多。 - Matthieu M.

2

如Mark B所说，compare表示的是一种排序而不是相等性，因此默认情况下是std::less。在你的情况下，你不希望比较依赖于你的配对顺序，但同时，你的operator<必须满足许多条件。

这里所有的答案都建议更改你的规范，并使比较依赖于顺序。但如果你不想这样做，这里是解决方案：

bool operator()(const Pair & a, const Pair & b) {
  const bool swapA = a.lhs < a.rhs;
  const std::string & al = swapA ? a.lhs : a.rhs;
  const std::string & ar = swapA ? a.rhs : a.lhs;
  const bool swapB = b.lhs < b.rhs;
  const std::string & bl = swapB ? b.lhs : b.rhs;
  const std::string & br = swapB ? b.rhs : b.lhs;
  return al < bl || (al == bl && ar < br);
}

至少，在您的示例中它是有效的，并且关系是自反和传递的。

它的工作原理如下：对于成对的字典顺序，它是al < bl || (al == bl && ar < br)，应用于排序后的成对。

事实上，您的数据结构是一个大小为N的集合，其中每个元素是大小为2的集合。在内部，std::set使用您的比较运算符对其进行排序。对于您的“大小为2的集合”Pair，您还需要将它们视为内部排序。

如果比较代码看起来太繁重，您可以将成对排序移到Pair类中，例如实现两个方法min()和max()。此外，您可以实现operator<，然后不需要compare类：

struct Pair {
  string lhs, rhs;
  Pair();
  Pair( string l, string r ) : lhs(l), rhs(r) {}
  const std::string & min() const { return lhs < rhs ? lhs : rhs; }
  const std::string & max() const { return lhs < rhs ? rhs : lhs; }
  bool operator<(const Pair& b) const {
    return min() < b.min() || (min() == b.min() && max() < b.max());
  }
};

- Antoine

这与我的答案完全相同，只是晚了四分钟。我不希望认为仅仅因为我指出了别人的错误，人们就会忽视我的答案，因为它包含了一个错误。- 为支持 OP 的无序选择加一分。 - user3125280

@user3125280：抱歉，我真的不认为我们的运算符具有相同的语义。我可能错了，但如果它是相同的，我的演示、代码和解释都是不同的。 - Antoine

@Anoine，你的代码规范了顺序并进行了字典比较，我的代码也进行了字典比较，除了那些反过来相同的情况。我的代码在可传递性方面失败了，但我不会去纠正它，因为已经被社区拒绝了。 - user3125280

@user3125280：冷静下来，这不是竞赛。我个人没有投票给你的答案，社区可以改变观点，只要我们都保持文明、理智并努力帮助彼此。 - Antoine

@Antoine同意了 - 我很久以前就为您的正确解决方案点赞了。 - user3125280

太棒了！感谢大家的高效和非常快速的帮助。我深深地印象深刻，因为这么多专业知识是免费提供的，并且有如此热情的支持。你们是最棒的！（Josef Schmitz） - user3139868

1

从这里开始

集合对象使用此表达式来确定元素在容器中遵循的顺序以及两个元素键是否等效（通过自反比较它们：如果!comp（a，b）&&！comp（b，a），则它们是等效的）。集合容器中没有两个元素可以是等效的。

抱歉，我因不喜欢另一个答案而过早地发表了评论。我将立即扩展和纠正。正如指出的那样，需要实现顺序。通常，这将是词典序。然而，重要的是，您仍然需要确保两对被认为相等的情况都返回false。

if (( a.lhs == b.lhs && a.rhs == b.rhs ) || ( a.lhs == b.rhs && a.rhs == b.lhs )) return false;
//ordinary lexicographical compare
if( a.lhs < b.lhs) return true;
else if( a.lhs == b.lhs && a.rhs < b.rhs) return true;
else return false;

注意"!"，很简单。你的代码是在说一对比另一对小，而这一对比那一对小。你需要让它表达出两者都不比另一者小。

免责声明在技术上仍有错误，安托万的是正确的。

- user3125280

2

很遗憾，这是不正确的，因为你没有实现一个顺序，仅仅是一个相等性测试。 - Matthieu M.

糟糕 - 我只是想在这种特定情况下返回false。 - user3125280

@MatthieuM请查看我的更正，如果满意请撤销点赞:)谢谢 - user3125280

@user3125280，放松一下，你回复得到处都是。他可能会接受的。 - woosah

@user3125280：谢谢您的通知，不幸的是，当一个被踩的答案被更正时，我们并不会自动收到通知 :/ - Matthieu M.

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark B · Accepted Answer

一个有序容器std::set的比较运算符需要识别一个严格弱序，而不是你想要的任意测试。通常，适当实现的operator<就能胜任这个工作。

如果你的比较运算符没有提供严格弱排序（如你所提供的），那么行为将是未定义的。没有办法绕过C++标准的这一要求。

请注意，在某些需要等式比较的情况下，它将使用两次operator<来进行比较。

另外，您是否考虑过使用std::pair<std::string, std::string>来代替自己编写？

我已经重新阅读了您的问题大约五次，现在开始怀疑您想要的是否是一组成对出现的集合，其中first和second字符串的顺序在比较时并不重要。如果是这样，@Antoine似乎为您提供了正确的解决方案。