c++ - 我丢失的 Edge 在哪里？

Question

我正在尝试使用 std::set我将在其中放入一堆边，并且只保留唯一的边。

安Edge是两个(整数索引)节点之间的一条线。边(1,2)==(2,1) ，因为这些边是无向的。

不过，我遇到了一个令人费解的情况。在标记为 //?? 的部分在下面的代码中，行为与我预期的不同。

运行这段代码的结果是只保留 2 条边，(1,2) 和 (4,8)。 (2,1) 被集合丢弃，但它不应该除非我激活注释掉的 //|| ( A==o.B && B==o.A ) operator== 中的部分!这里发生了什么？

这set<Edge>实现让我感到……急躁。

#include <stdio.h>
#include <set>
using namespace std ;

struct Edge
{
  int A,B ;
  Edge( int iA, int iB ) : A(iA), B(iB) {}
  bool operator==( const Edge & o ) const {
    //??
    return ( A==o.A && B==o.B ) ;//|| ( A==o.B && B==o.A ) ;
  }
  bool operator<( const Edge& o ) const {//MUST BE CONST
    return A < o.A && B < o.B ;
  }
  void print() const { printf( "( %d, %d )", A,B ) ; }
  void compare( const Edge& o ) const {
    print() ;
    if( *this==o ) printf( "==" ) ;
    else printf( "!=" ) ;
    o.print() ;
    puts("");
  }
} ;

int main()
{
  Edge e1( 1, 2 ) ;
  Edge e2( 1, 2 ) ;
  Edge e3( 2, 1 ) ;
  Edge e4( 4, 8 ) ;

  e1.compare( e2 ) ;
  e1.compare( e3 ) ;
  e1.compare( e4 ) ;

  set<Edge> edges ;
  edges.insert( e1 ) ;
  edges.insert( e2 ) ;
  edges.insert( e3 ) ;
  edges.insert( e4 ) ;

  printf( "%d edges\n", edges.size() ) ;
  for( auto edge : edges )
  {
    edge.print();
  }
}

Answer 1

C++ 集不关心你的==运算符(operator)尽可能多地处理您的 <运算符(operator)。是你的<出现问题的运算符(operator):如果您想确保 (1,2)等于(2,1) , 你应该改变你的 < 的实现表现得像这样:

bool operator<( const Edge& o ) const {
    int myMin = min(A, B);
    int myMax = max(A, B);
    int hisMin = min(o.A, o.B);
    int hisMax = max(o.A, o.B);
    return myMin < hisMin || ( myMin == hisMin && myMax < hisMax );
}

此实现所做的是构建边的规范表示，其中较小的 {A,B}成为“规范A”，较大的成为“规范B”。当以规范形式比较边时，(1,2) 的相等性和 (2,1)可以从以下事实暗示 (1,2) < (2,1)和 (2,1) < (1,2)评估为 false .