3

我正在尝试使用一个std::set我将放入一堆边缘的地方，并且只保留独特的边缘。

AnEdge是两个（整数索引）节点之间的一条线。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();
  }
}
4

4 回答 4

5

C++ set 并不像关心你的==运算符那样关心你的<运算符。是您的<运营商提出了问题：如果您想确保(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

于 2012-12-21T20:49:22.313 回答
3

我相信你operator<是错的，两者e3<e2都是e2<e3错误的。

也许你想要类似的东西：

return A < o.A || ((A == o.A) && (B < o.B)) ;
于 2012-12-21T20:48:24.770 回答
2

我建议您更改 Edge() 构造函数以确保始终初始化 A 和 B 以便A<=B（如果边缘可以指向其原始节点）或A<B（如果不是），并放弃在 operator== 实现中使用额外的逻辑. 这对我来说似乎不那么“前卫”。

于 2012-12-21T20:48:32.017 回答
-1

你的比较应该是

return (A == o.A && B == o.B) || (B == o.A && A == o.B);
于 2012-12-21T20:51:38.547 回答