1

以下のコードを実行しようとしました。私が見つけたのは、出力に違いがあるということです。コンパレータ機能で使用される順序付けメカニズムに問題があることを理解しています。私が基本的に探しているのは次のとおりです。1）Setはどのようにデータを内部に保存しますか。2）この問題を解決するにはどうすればよいですか、またはデータを別のセットにコピーするための最良の方法です。3）注文がこの問題をどの程度正確に引き起こしているか。

#include <iostream>
#include <set>
using namespace std;
struct Comparator {
  bool operator()( const int& a, const int& b ) {
    if( a <= b ) 
      return true;
    else
      return false;
  }
};
int main()
{
  set< int, Comparator > customSet;
  for( unsigned k = 0, index = 2; k < 10; ++k ) {
    customSet.insert( index );
  }

  set< int, Comparator >::iterator iter = customSet.begin();
  for(; iter != customSet.end(); ++iter ) {
    cout<<*iter<<endl;
  }

  cout<<"---------------------------------"<<endl;
  set< int, Comparator > tempCustomSet ;//= customSet;
  tempCustomSet.insert( customSet.begin(), customSet.end() );

  iter = tempCustomSet.begin();
  for(; iter != tempCustomSet.end(); ++iter ) {
    cout<<*iter<<endl;
  }

  return 0;
}
4

4 に答える 4

2

1) Set はどのように内部的にデータを保存しますか

唯一の要件は、要素が次のとおりであることです。

  • セットを反復するときにifComp(a,b)が thenのa前に表示されるように、コンパレータに従って順序付けされます。b
  • Comp(a,b)一意であるため、との両方が成立する明確な要素はありませんComp(b,a)。

操作が特定の複雑さの要件を満たしていること。

実際には、それらは通常、二分探索ツリーに格納されます。しかし、それはユーザーにとって重要ではありません。

2) この問題を解決するにはどうすればよいですか、またはデータを別のセットにコピーする最善の方法は?

要件を満たすために、比較演算子は のような厳密で弱い順序付け<でなければならないため、 のようなComp(a,a)非厳密な順序付けではなく、常に false になり<=ます。がデフォルトであるため<、カスタム コンパレータはまったく必要ありません。

3) 注文がこの問題をどの程度正確に引き起こしているか

最初のループは値を210 回挿入していることに注意してください。それが意図されているかどうかはわかりません。

厳密な順序付けが必要な場合は、 falseでinsert(b)ある最初の要素を見つけることで挿入ポイントを探すaことができます。Comp(a,b)つまり、b後に来てはならない最初の要素です。次に、 をチェックして一意性をチェックしComp(b,a)ます。両方が false の場合、2 つの値が等しいことを示しているため、b挿入されません。

比較は厳密ではないため、この一意性テストは失敗する可能性があります。そのため、エントリが重複してしまう可能性があります。または、何か他のことが起こる可能性があります - 動作は未定義です。

于 2013-01-29T13:05:16.020 に答える
2

の詳細については、このリファレンスを参照してくださいstd::set。インターフェイスと複雑さの保証が標準にとって重要なすべてであるため、実装は気にする必要はありません (プラットフォームごとに異なる場合があります)。典型的な実装ではred-black-treesを使用しています。

ではなく、Comparator利用する必要があります。その理由は、が評価された場合に要素が同等であると見なされるためです(つまり、どちらも厳密には他方よりも小さいわけではありません)。operator<operator<=std::set!Comparator(a, b) && !Comparator(b, a)true

しかし、<=では とa <= a等しいtrueので、等しい要素が!(a<=a) && !(a<=a)得られます。false一方、<あなたはa < aと等しいfalseので、!(a<a) && !(a<a)を与えtrueます。

する権利は次のとおりです。

struct Comparator 
{
    bool operator()(int const& lhs, int const& rhs) const 
    {
        return lhs < rhs; 
    }
};

これにより、等しい要素が同等と見なされることが保証されます。これについては、Effective STLの「項目 19. 等価と等価の違いを理解する」で詳細に説明されていることに注意してください。

于 2013-01-29T12:42:46.350 に答える
2

この問題は、比較が厳密な弱い順序付けを実装していないために発生する可能性が最も高いです。セットの内部順序付けメカニズムはこれに依存しています。比較を未満に変更することで、SWO を取得できます。

struct Comparator {
  bool operator()( const int& a, const int& b ) const {
    return ( a < b ); 
  }
};

一方、std::setはデフォルトでこの比較基準を使用するため、指定する必要はありません。

この質問に対する私の回答には、関連する情報がいくつかあります（および他の無数のSOの質問）。

于 2013-01-29T12:46:12.423 に答える