3

をセットに追加しようとしてpair<int,int>います。ペアがセット内の別のペアと同じ 2 つの値を共有している場合は、挿入しないでください。

これが私の非動作コードです：

typedef  std::pair<int, int> PairInt;

template<>
bool std::operator==(const PairInt& l, const PairInt& r) 
{
    return (l.first == r.first && l.second == r.second) ||
           (l.first == r.second && l.second == r.first);
}

int main()
{
    std::set<PairInt> intSet;
    intSet.insert(PairInt(1,3));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(4,1));
}

現時点では、(1,4) ペアが既に存在するにもかかわらず、(4,1) ペアが追加されます。セットの最終的な内容は次のとおりです。

(1 3)
(1 4)
(4 1)

そしてそうであってほしい

(1 3)
(1 4)

オーバーロードされたメソッドにブレークポイントを設定しようとしましたが、到達することはありません。私は何を間違えましたか？

4

3 に答える 3

4

operator<セットは (等式関係) ではなく (順序付け/等値関係)に基づいてoperator==います。

やろうとしていることを行うには、カスタム コンパレータを使用します。

#include <set>
#include <utility>
#include <cassert>
typedef std::pair<int, int> PairInt;
PairInt normalize(const PairInt& p) {
    return p.second < p.first ? PairInt(p.second, p.first) : p;
}
struct Comparator {
    bool operator()(const PairInt& l, const PairInt& r) const {
        //Compare canonical forms of l and r.
        return normalize(l) < normalize(r);
    }
};

int main()
{
    std::set<PairInt, Comparator> intSet;
    intSet.insert(PairInt(1,3));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(4,1));
    assert(intSet.size() == 2);
}
于 2012-03-24T05:12:44.077 に答える
2

等しいかどうかを判断するためではなく、一方のアイテムが他方よりも小さいことを確認するための比較関数を提供する必要があります。完全な例を次に示します。

#include <utility>
#include <algorithm>
#include <set>
#include <iostream>

typedef  std::pair<int, int> PairInt;
typedef bool Compare(const PairInt &,const PairInt &);

bool compare(const PairInt &l,const PairInt &r)
{
  int lfirst = std::min(l.first,l.second);
  int rfirst = std::min(r.first,r.second);
  if (lfirst<rfirst) return true;
  if (rfirst<lfirst) return false;
  return std::max(l.first,l.second)<std::max(r.first,r.second);
}

int main()
{
  typedef std::set<PairInt,Compare*> IntSet;
  IntSet intSet(compare);
  intSet.insert(PairInt(1,3));
  intSet.insert(PairInt(1,4));
  intSet.insert(PairInt(1,4));
  intSet.insert(PairInt(4,1));
  for (IntSet::const_iterator i=intSet.begin(); i!=intSet.end(); ++i) { 
    std::cerr << i->first << "," << i->second << "\n";
  } 
}

出力：

1,3
1,4
于 2012-03-24T05:11:41.807 に答える
0

比較では、最初の項目が 2 番目の項目より小さいかどうかを判断する必要があります。したがって、次のようになります。

namspace std
{
  template<>
  bool operator < (const PairInt& l, const PairInt& r) 
  {
     //swap only if they're unequal to avoid infinite recursion
     if (l.first != l.second) 
     {
         //swap elements, considering your special case
          if (l.first == r.second && l.second == r.first)
             return l < PairInt(r.second, r.first); //call again!
     }

    //actual comparison is done here
    if ( l.first != r.first )
       return l.first < r.first;
    else 
       return l.second < r.second;
  }
}

これで、目的の出力が得られます。

1,3
1,4

オンラインデモをご覧ください。

比較機能が続くことに注意してください:厳密な弱い順序付け

于 2012-03-24T05:15:52.970 に答える