STLのsetに自作クラスを重複なく格納する

[くりつ]

こんばんわ，

かなり困ってるので助けてもらえると助かります．
STLのsetは要素を重複なく格納できるのが特徴だと思っているのでそれを自作クラスに使おうとしました．
Edgeクラスはxy座標を格納するのですが，(1,2)，(2,1)は同じ要素として考えてどちらか一方のみ格納したいです．
入力で(1,2)->(1,2)->(2,1)->(3,2)->(2,3)->(5,2)までは，正しく重複なく格納できるのですが，最後に(1,2)を登録すると
1 2
5 2
3 2
1 2
このように格納されていることがわかりました．

なぜ最後の(1,2)が重複チェックをくぐりぬけて格納されるのでしょうか？

コード:

#include<iostream>
#include<set>

class Edge {

private:
  int u, v;

public:
  bool operator< (const Edge& e) const {
    bool result = true;
    if( (u == e.u && v == e.v) || (v == e.u && u == e.v) ) {
      result = false;
    }
    return result;
  }

  std::pair<int, int> pair() const {
    return std::pair<int, int>(u, v);
  }

  Edge(int u_, int v_) : u(u_), v(v_) {}
};

int main(void) {
  std::set<Edge> edge;
  std::set<Edge>::iterator eit;

  edge.insert(Edge(1,2)); // <-- (1,2) can be contained.
  edge.insert(Edge(1,2)); // <-- (1,2) doesn't have to be contained.
  edge.insert(Edge(2,1)); // <-- (2,2) doesn't have to be contained.

  edge.insert(Edge(3,2)); // <-- (3,2) can be contained.
  edge.insert(Edge(2,3)); // <-- (2,3) doesn't have to be contained.
  edge.insert(Edge(5,2)); // <-- (5,2) doesn't have to be contained.

  edge.insert(Edge(1,2)); // <-- (1,2) doesn't have to be contained. But edge contains this. Why?

  for(eit = edge.begin(); eit != edge.end(); eit++) {

    std::cout << (*eit).pair().first << " " << (*eit).pair().second << std::endl;
  }

  return 0;
}

[beatle]

operator<がまずいと思います。
a < b == trueの場合にb < aもtrueになってしまいます。

[a5ua]

問題点は、beatleさんが指摘したとおりですが、
std::setが使う比較関数は、strict weak ordering（日本語だと厳密弱順序？）という性質を満たす必要があります。
【参考】
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

修正案としては、
・リンク先のInvariantsを満たすようにoperator<を適切に実装する
・pairに対して定義されているoperator<を使う
・ただ単に、typedef std::pair<int, int> Edgeとして使う

などが考えられます。

以下実装例

コード:

class Edge
{
	int u, v;
public:
	Edge(int u_, int v_): u(u_), v(v_)
	{
	}

	bool operator<(const Edge& e) const
	{
		return (u < e.u) || (u == e.u && v < e.v);
	}
};

コード:

class Edge
{
	std::pair<int, int> uv;
public:
	Edge(int u_, int v_): uv(u_, v_)
	{
	}

	bool operator<(const Edge& e) const
	{
		return uv < e.uv;
	}
};

[くりつ]

ん〜，定義が難しいのでよくわかりません・・・
私のやろうとしていることは不可能なんですか？

[かずま]

私のやろうとしていることは不可能なんですか？

不可能ではありません。

コード:

  bool operator< (const Edge& e) const {
    return u < v ? e.u < e.v ? u < e.u || u == e.u && v < e.v
                             : u < e.v || u == e.v && v < e.u
                 : e.u < e.v ? v < e.u || v == e.u && u < e.v
                             : v < e.v || v == e.v && u < e.u;
  }

[かずま]

Edgeクラスはxy座標を格納するのですが，(1,2)，(2,1)は同じ要素として考えてどちらか一方のみ格納したいです．

コンストラクタで、u, v を昇順にしておけば、operator< は単純になります。

コード:

#include <iostream>
#include <set>
 
class Edge {
 
private:
  int u, v;
 
public:
  bool operator< (const Edge& e) const {
    return u < e.u || u == e.u && v < e.v;
  }
 
  std::pair<int, int> pair() const {
    return std::pair<int, int>(u, v);
  }
 
  Edge(int u_, int v_) {
    if (u_ < v_) u = u_, v = v_;
    else u = v_, v = u_;
  }
};
 
int main(void) {
  std::set<Edge> edge;
  std::set<Edge>::iterator eit;
 
  edge.insert(Edge(1,2)); // <-- (1,2) can be contained.
  edge.insert(Edge(1,2)); // <-- (1,2) doesn't have to be contained.
  edge.insert(Edge(2,1)); // <-- (2,1)  doesn't have to be contained.
 
  edge.insert(Edge(3,2)); // <-- (3,2) can be contained.
  edge.insert(Edge(2,3)); // <-- (2,3) doesn't have to be contained.
  edge.insert(Edge(5,2)); // <-- (5,2)  can be contained.
 
  edge.insert(Edge(1,2)); // <-- (1,2) doesn't have to be contained.
 
  for(eit = edge.begin(); eit != edge.end(); eit++) {
 
    std::cout << (*eit).pair().first << " " << (*eit).pair().second << std::endl;
  }
 
  return 0;
}