3

以下に定義されているように、非常に単純な構造のマッピングを使用しています。

struct mapping{
    int code;
    string label;

    bool operator<(const mapping& map) const {
        return code < map.code;
    }

    bool operator==(const mapping& map) const {
        return label.compare(map.label) == 0 ;
    }
};

コードで並べ替えられた一連のマッピングを作成したいと思います。そのために、< 演算子をオーバーロードしました。それは正常に動作します。問題なく、ラベルの異なるいくつかのマッピングを挿入できます。

同じコードでラベルが異なるマッピングを挿入しようとすると、問題が発生します。実際、プロセスの 2 番目のステップでは、同じラベルのマッピングが以前に挿入されたかどうかはわかりません。そのため、find() 関数を呼び出して、該当するかどうかを判断する必要があります。同じラベルのマッピングが挿入されていない場合は、問題ありません。この新しいマッピングを挿入するだけです (ただし、そのコードは一時的に他のマッピングと同じになります)。同じラベルのマッピングが 1 つ存在する場合は、そのコードを更新するだけです。私が行ったように == 演算子をオーバーロードするだけで十分だと思いますが、次のコードに示すようにそうではありません。

mapping m = {1,"xxx"};
mapping m2 ={1, "yyy"};

this->fn[0].insert(m);

set<mapping>::iterator itTmp;
itTmp = this->fn[0].find(m2);
if (itTmp != this->fn[0].end() ) {
    cout << "m2 exists "<<endl;

    if ( !(*itTmp == m2) ){
        cout << "But it is different according to the definition of the == operator "<<endl;
    }
}

関連する出力は次のとおりです。

m2 exists
But it is different according to the definition of the == operator

この問題を解決し、演算子 < と == を非常に異なるセマンティクスで処理するにはどうすればよいですか? 理想的には、セット全体を反復して同じラベルのマッピングを探すことは避けたいと思います。このような戦略の複雑さは O(n) であり、n は私のアプリケーションでは非常に大きくなる可能性があります。find() の複雑さと同様に、私は O(log n) での解決策を好みます。

ありがとう、

ヨアン

4

5 に答える 5

1

@PiotrNyczが指摘したように、std::set使用も気にもせずoperator==、operator<. これにはstd::set<X>::findメンバーが含まれます。したがって、find呼び出しは、同じラベルを持つ要素ではなく、同じコードを持つ要素を見つけています。

ただし、名前空間スコープ関数は を使用し、std::findは使用operator==しませんoperator<。

itTmp = std::find(this->fn[0].begin(), this->fn[0].end(), m2);

ラベルではなくコードで順序付けされてsetいるため、要素の数が多い場合、特定のラベルを持つ要素を見つけることは、特定のコードを持つ要素を見つけるほど効率的ではありません。これが重要な場合は、他の回答で、コンテナーの種類を変更して役立つ方法について提案されています。

于 2012-06-21T12:10:21.003 に答える
1

クラスが複数のフィールドで合理的にソートできる場合は、関係演算子 (operator==とを除くoperator!=) をまったく使用しないでください。

はい、std::mapデフォルトstd::setでstd::lessはコンパレータとして使用されます（内部で使用されます）が、これは便利なので、operator<を作成するためだけに関数オブジェクトを記述する必要はありません。 ) ) )。set<double>doubleoperator<

また、コンパレーター テンプレート引数も提供します。これを使用して、そのコンテナー (リレーショナル データベースなど) に必要なインデックスを正確に提供することができます。要素のセットに対して複数のインデックスを維持するコンテナー (boost 内) もあります。

point2d例として、クラスを考えてみましょう:

struct point2d { int x, y; };

またはのいずれかでpoint2ds のコンテナーにインデックスを付けたいと考えるのは合理的かもしれません。クラスのすべてのユーザーが独自の並べ替え関数オブジェクトを発明することを避けるために、それらを一緒に提供することができます:xypoint2doperator<point2d

struct less_point2d_by_x {
    typedef bool result_value;
    // the mixed overloads are for use in std::lower_bound and similar
    bool operator()( int lhs, int rhs ) const { return lhs < rhs; }
    bool operator()( int lhs, point2d rhs ) const { return lhs < rhs.x; }
    bool operator()( point2d lhs, int rhs ) const { return lhs.x < rhs; }
    bool operator()( point2d lhs, point2d rhs ) const { return lhs.x < rhs.x; }
};
// same for _y

使用法：

std::vector<point2d> v = ...;
std::sort(v.begin(), v.end(), less_point2d_by_x()); // sort by x
std::sort(v.begin(), v.end(), less_point2d_by_y()); // sort by y

std::set<point2d, less_point2d_by_x> orderedByX;
std::set<point2d, less_point2d_by_y> orderedByY;

テンプレートを恐れていない場合は、次のように関係演算子をテンプレート化することもできます。

template <template <typename T> class Op=std::less>
struct point2d_by_x {
    typedef bool result_value;
    // the mixed overloads are for use in std::lower_bound and similar
    bool operator()( int lhs, int rhs )         const { return Op<int>()(lhs, rhs); }
    bool operator()( int lhs, point2d rhs )     const { return Op<int>()(lhs, rhs.x); }
    bool operator()( point2d lhs, int rhs )     const { return Op<int>()(lhs.x, rhs); }
    bool operator()( point2d lhs, point2d rhs ) const { return Op<int>()(lhs.x, rhs.x); }
};
// same for _y

使用法：

std::vector<point2d> v = ...;
std::sort(v.begin(), v.end(), point2d_by_x<std::less>()); // sort ascending by x
std::sort(v.begin(), v.end(), point2d_by_x<>()); // same
std::sort(v.begin(), v.end(), point2d_by_x<std::greater>()); // sort descending by x
// find the position where a `point2d` with `x = 14` would go in the ordering:
std::lower_bound(v.begin(), v.end(), 14, point2d_by_x<std::greater>());

std::set<point2d, point2d_by_x<std::less> > increasingXOrder;
std::set<point2d, point2d_by_y<std::less> > increasingYOrder;
于 2012-06-21T20:58:56.003 に答える
0

std::setを使用するため、のセマンティクスをに挿入operator<する必要があります。これを行うには、たとえば最初にをチェックし、それが等しい場合は、を比較します。operator==operator<codelabel

更新標準ライブラリ内の順序付けされたコンテナは、厳密な弱順序を意味するコンパレータを使用する必要があります。これはoperator<、厳密な順序を推測する必要があることを意味します（異なる要素は異なる順序を持ちます）が、不平等について何も知らないため、弱いです。

あなたの場合、コメントで指摘されているように、の比較が必要になりstring labelます。2つのオプション：

return code < map.code || (!(map.code < code) && label < map.label);

またはその逆で、最初にチェックlabelしてからcode。

の同等性のみをチェックlabelすると、「厳密な」順序付けの感覚が失われます。

于 2012-06-21T09:57:01.507 に答える
0

おそらく、複数のコンテナー (2 つまたは 3 つ) を作成する必要があります。例えば：

std::list<mapping> storage; // actual storage
std::multiset<mapping*, compare_by_code_functor> by_code; // sorted by code
std::set<mapping*, compare_by_label_functor> by_label; // sorted by label

また

std::list<mapping> storage; // actual storage
std::multiset<std::list<mapping>::iterator, compare_by_code_functor> by_code; // sorted by code
std::set<std::list<mapping>::iterator, compare_by_label_functor> by_label; // sorted by label
于 2012-06-21T10:51:47.260 に答える
0

コードまたはマップの検索で O(log n) が必要な場合、std::setこれは 1 つの順序でのみソートされるため、適切なコンテナーではありません。必要なのは、他のマップのエントリへのポインターを値として持つ二重マップです。このように、各メンバーはそのマップのキーであり、O(log n) で見つけることができます。

ブーストを使用できる場合は、boost.bimapを確認してください

于 2012-06-21T09:59:13.517 に答える