1

指定された equal_to 関数 int unordered_set を使用したい サンプル コードは次のようになります。

struct myEqual
{       //string with one different character is considered equal
    bool operator()(const string &s1, const string &s2)const
    {

        if(s1.length() != s2.length()) return false;
        int dis = 0;
        for(unsigned int i = 0; i<s1.size(); i++)
        {
            if(s1[i] != s2[i])
            {
                dis++;
                if(dis >= 2) return false;
            }               
        }
        return true;
    }
};

int main()
{
    unordered_set<string, std::tr1::hash<string>, myEqual> myDict;
    myDict.insert("a");
    myDict.insert("b");
    myDict.insert("c");

    unordered_set<string, std::tr1::hash<string>, myEqual>::iterator it = myDict.find("k");
    if(it == myDict.end())
    {
        cout<<"myequal not work"<<endl;
    }
    else
    {
        cout<<*it<<endl;
    }
    return 0;
}

myEqual 関数によると、「k」と「等しい」「a」、「b」、「c」の 3 つの値がありますが、検索ではイテレータが 1 つしか返されません。とにかくすべての等しい値を見つけることはありますか?

4

2 に答える 2

4

ここには 2 つの問題がありますが、どちらも要素の検索には関係ありません。

  1. "a"、"b"および"c"すべてが互いに等しいため、 にはそのうちの 1 つしか保持できませんunordered_set。
  2. 等しいと比較される要素がありますが、ハッシュ コードが異なる可能性があります。これは、順序付けられていないセットが正しく機能するために満たさなければならない契約に違反しています。

心に留めておくべきより一般的な問題は、等価関係が推移的ではないということです: "aa"equals"ab"と"ab"equals "bb"。まだ"aa"等しくない"bb".

于 2013-02-13T16:35:51.993 に答える
0

最善の方法は、次の 4 つの点を修正することです。

  1. std:unordered_multisetas コンテナを使用する

  2. 相互に一貫性のあるハッシュ関数とキー比較関数を使用します。特に、ハッシュ関数は等しい要素を等しいキーにマップする必要があります。

  3. 同値関係にある比較関数を使用します。特に、これは ifA==BとB==C、 then A==C、 whereが your に==対応することを意味しますmyEqual。

  4. equal_range反復子のペアを返すメンバー関数を使用します。最初の反復子がコンテナーの末尾に等しくない場合は、ループできます。

コード：

auto res = myDict.equal_range("k");
if(res.first == myDict.end())
{
    cout<<"myequal not work"<<endl;
}
else
{
    for (auto it = res.first; it != res.second; ++it) 
        cout<<*it<<endl;
}

現在、ハッシュ関数と比較演算子の両方が C++ 標準ライブラリのコンテナー要件に違反しています。myEqualあなたのハッシュコードは、等しい（あなたの意味で）文字列を等しいハッシュキーにマップしません。比較演算子は推移的ではありません (@NPE の例を参照してください)。std::unordered_setこれは、またはを使用できないことを意味しますstd::unordered_multiset。これを行うと、コードで未定義の動作が発生します。

于 2013-02-13T17:22:24.293 に答える