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 函数，“a”、“b”、“c”三个值“等于”“k”，但是 find 只返回一个迭代器。反正有没有找到所有相等的价值？

4

2 回答 2

4

这里有两个问题，都与查找元素无关：

  1. 由于"a","b"并且"c"所有比较彼此相等，因此您只能将其中一个保留在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==对应于您的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_setor std::unordered_multiset。如果这样做，您的代码会产生未定义的行为。

于 2013-02-13T17:22:24.293 回答