<hash_set> 在 VS2010 中的等号运算符无法正常工作

Question

示例代码：

std::hash_set<int> hs1; // also i try std::unordered_set<int> - same effect 
std::hash_set<int> hs2;

hs1.insert(15);
hs1.insert(20);

hs2.insert(20);
hs2.insert(15);

assert(hs1 == hs2);

为什么hash_set不按照哈希函数定义的顺序存储元素？请注意，此代码在使用stdext::hash_set的VS2008中有效。

- ProgramWriter

---

你是在说你期望 hs1 == hs2 为真，还是它们已经相等而你不理解为什么？ - jalf

我不明白为什么它们不相等 =) 这个断言失败了，这是一个问题。 - ProgramWriter

Answer 1

看起来在Visual C++ 2010中，对于hash_set和unordered_set的相等比较都存在问题。

我使用了标准中Matthieu引用的语言实现了一个天真的相等函数来验证这是一个bug（只是为了确保）：

template <typename UnorderedContainer>
bool are_equal(const UnorderedContainer& c1, const UnorderedContainer& c2)
{
    typedef typename UnorderedContainer::value_type Element;
    typedef typename UnorderedContainer::const_iterator Iterator;
    typedef std::pair<Iterator, Iterator> IteratorPair;

    if (c1.size() != c2.size())
        return false;

    for (Iterator it(c1.begin()); it != c1.end(); ++it)
    {
        IteratorPair er1(c1.equal_range(*it));
        IteratorPair er2(c2.equal_range(*it));

        if (std::distance(er1.first, er1.second) != 
            std::distance(er2.first, er2.second))
            return false;

        // A totally naive implementation of is_permutation:
        std::vector<Element> v1(er1.first, er1.second);
        std::vector<Element> v2(er2.first, er2.second);

        std::sort(v1.begin(), v1.end());
        std::sort(v2.begin(), v2.end());

        if (!std::equal(v1.begin(), v1.end(), v2.begin()))
            return false;
    }

    return true;
}

根据你的例子，返回结果表明hs1和hs2是相等的。（如果您在代码中发现错误，请告诉我；我没有进行过广泛的测试...）

我将在Microsoft Connect上提交一个缺陷报告。

- James McNellis

---

缺陷报告链接：https://connect.microsoft.com/VisualStudio/feedback/details/557117/std-unordered-set-equality-comparison-broken-in-visual-c-2010 - James McNellis

谢谢James :) 我不确定你的比较是否最优，但我也没有看到任何明显的错误。无论如何，即使没有代码，我从标准中了解到unordered_set的相等性等同于set的相等性，不应取决于插入的顺序或删除的可能性。 - Matthieu M.

Answer 2

最终在23.2.5注11中找到了参考：

如果两个无序容器 a 和 b 满足 a.size() == b.size()，并且对于从 a.equal_range(Ea1) 获得的每个等效键组 [Ea1,Ea2)，存在一个从 b.equal_range(Ea1) 获得的等效键组 [Eb1,Eb2)，使得 distance(Ea1, Ea2) == distance(Eb1, Eb2) 并且 is_permutation(Ea1, Ea2, Eb1) 返回 true，则两个无序容器 a 和 b 相等。

我敢打赌 hash_set 现在是基于 unordered_set 实现的，但我仍然不明白为什么在你的情况下它会失败。

平均情况下的复杂度要求是 O(N)，但由于线性链接实现要求，最坏情况下会退化为 O(N²)。

- Matthieu M.

---

作为解决方案，我发现了boost :: unordered_set..但我再次对Billy和他的团队感到失望。 - ProgramWriter

Answer 3

我在这里提出了这个问题，但没有得到回复=) 感谢您的反馈。

我还创建了一些简单的控制台测试（只是为了确保）：

#include <iostream>
#include <hash_set>
int main(int argc, char* argv[])
{   
  stdext::hash_set<int> hs1, hs2;
  hs1.insert(10);
  hs1.insert(15);
  hs2.insert(15);
  hs2.insert(10);
  std::cout << ((hs1 == hs2) ? "It works!" : "It NOT works") << std::endl;
  return EXIT_SUCCESS;
}

并编译它。 使用vs2008命令提示符：

cl.exe HashSetTest.cpp /oHashSetTest2008.exe 

使用 VS 2010 命令提示符：

cl.exe HashSetTest.cpp /oHashSetTest2010.exe

我真的看到了不同的结果=）

- ProgramWriter