1

std::mapコンテナのカスタムコンパレータを定義しようとしています。

問題は、==および！=演算子で中継できるか、それとも厳密な弱順序を破ることができるかということです。演算子<を使用する必要がありますか？

（1つと2つのクラスにはoperator！=とoperator ==が正しく定義されています）

typedef std::pair<One, Two> MapKey_t;
class cmp
{
    bool operator()(const MapKey_t& left, const MapKey_t& right) const
    { return left.first != right.first && right.first == right.second; }
}

typedef std::map<MapKey_t, Three*, cmp> MyMap_t;

左から右に切り替えてもコンパレータの戻り値は変わらないので、これは機能しますか？

アイテムがどのようにコンテナに分類されるかはあまり気にしませんが、重複をコンテナの一部にしたくありません。

更新：

メモリアドレスを使用して厳密な弱順序を取得できますか？

class cmp
{
    bool operator()(const MapKey_t& left, const MapKey_t& right) const
    { 
        if(left.first == right.first)
            if(left.second != right.second)
                return false; // This represents for me, functionally, a duplicate
            else
                // Can't use operator < there since left.second equals right.second but
                // functionally for me, this is not a duplicate and should be stored
                // what about memory address strict weak ordering ?
                return &left < &right;
        else
            return left.first < right.first; // There I can use operator <
}
4

3 に答える 3

5

これらは厳密な弱順序を確立しないため、自己整合性のある等しいまたは等しくないことに依存することはできません。左右の引数を切り替えると、コンパレータの戻り値が変わるはずです。マップには、2つの要素が等しいかどうかを区別できるだけでなく、要素の順序を確立できることが不可欠です。

A < Bが真であり、次にB < A偽であることが非常に重要です。さらに、A < BとB < Cが両方とも真である場合、それA < Cも真です。

タイプの厳密な弱順序を確立したくない、または確立できない場合は、それを必要としないマップを使用できます。1、これはハッシュマップです。ただし、これには、ハッシュ関数と等価比較を提供する必要があります。また、コンパイラがC++11をサポートしている必要があります。std::unordered_map

1 @JohnDiblingがコメントで指摘しているように、std::unordered_map残念ながら名前が付けられています。名前が他の図書館からstd::hash_map衝突した可能性があるのは明らかだったはずですが。hash_mapsいずれにせよ、その目的は、順序付けされていないマップを作成することではなく、一定の時間でルックアップを行うマップを作成することです。

于 2012-11-23T16:11:05.330 に答える
5

マップ内で物事がどのように順序付けられているかは気にしないかもしれませんが、マップは気にします。上記で提供したコードは、厳密な弱順序を正しく実装していないようです。左から右に切り替えてもすべての場合の結果が変わるわけではないことをすでに説明したようoperator()に、関数は厳密な弱順序を実装していません。

operator<必ずしも直接の観点からコンパレータを実装する必要はありませんが、がをoperator()(A,B)返す場合はtrue、operator()(B,A)も返さないようにする必要がありますtrue。

于 2012-11-23T16:12:57.433 に答える
0

これは受け入れられません。文字列の弱順序は、同時に真ではないことA < Bを意味します。キーの順序と同等性の両方を確立するためにこれに依存していますB < Astd::map

于 2012-11-23T16:11:00.167 に答える