CODEWITHSUNDEEP
c++visual-studio-2010
ProgramWriter
ProgramWriter

Reputation: 283

<hash_set> equality operator doesn't work in VS2010

Sample code:

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 doesn't stores elements in some order defined by hash function... why? Please note that this code works in VS2008 using stdext::hash_set.

Upvotes: 4

Views: 769

Answers (3)

ProgramWriter
ProgramWriter

Reputation: 283

i ask this question here but give no response =) thanks for your feedback.

i also create some simple console test (just to be sure):

#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;
}

and compile it. using vs2008 command prompt:

cl.exe HashSetTest.cpp /oHashSetTest2008.exe

using vs2010 command prompt:

cl.exe HashSetTest.cpp /oHashSetTest2010.exe

I really see different results =)

Upvotes: 1

James McNellis
James McNellis

Reputation: 355227

It looks like equality comparisons are broken for both hash_set and unordered_set in Visual C++ 2010.

I implemented a naive equality function for unordered containers using the language from the standard quoted by Matthieu to verify that it's a bug (just to be sure):

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;
}

It returns that hs1 and hs2 from your example are equal. (Somebody let me know if you spot a bug in that code; I didn't really test it extensively...)

I'll file a defect report on Microsoft Connect.

Upvotes: 4

Matthieu M.
Matthieu M.

Reputation: 300209

Finally found the reference in the final draft at 23.2.5, note 11:

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1,Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1,Eb2) obtained from b.equal_range(Ea1), such that distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1) returns true.

I would bet hash_set is now implemented in term of unordered_set (to begin with), but I still don't understand why in your case it would fail.

The complexity requirement is O(N) in the average case but degenerates to O(N2) in the worst case because of the linear-chaining implementation requirement.

Upvotes: 2

Related Questions