3

std::setたくさんのエッジを投入し、ユニークなものだけを残す場所を使用しようとしています。

AnEdgeは、2 つの (整数インデックス付き) ノード間の線です。(1,2)==(2,1)これらのエッジは無向であるため、Edge 。

しかし、これで不可解な状況に遭遇しています。//??以下のコードでマークされているセクションでは、動作が期待どおりではありません。

このコードを実行した結果、(1,2) と (4,8) の 2 つのエッジのみが保持されます。(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 に答える