Geek asks and answers

<hash_set> equality operator does not work in VS2010

Code example:

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 store items in some order defined by a hash function ... why? Note that this code works in VS2008 using stdext :: hash_set.

+4
source share
3 answers

It seems that in Visual C ++ 2010, comparison comparisons were broken in layers hash_setand unordered_set.

I implemented a naive equality function for unordered containers using the language from the standard quoted by Matthieu to make sure this is a mistake (just make 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;
}

, hs1 hs2 . (- , , ...)

Microsoft Connect.

+4

, 23.2.5, 11:

a b , a.size() == b.size(), [Ea1,Ea2), a.equal_range(Ea1), [Eb1,Eb2), b.equal_range(Ea1), distance(Ea1, Ea2) == distance(Eb1, Eb2) is_permutation(Ea1, Ea2, Eb1) true.

, hash_set unordered_set ( ), , .

- O (N) , O (N 2) - .

+2

I ask this question here , but I do not answer =) thanks for your feedback.

I also create a simple console test (just to make 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 the vs2008 command line:

cl.exe HashSetTest.cpp /oHashSetTest2008.exe

using vs2010 command line:

cl.exe HashSetTest.cpp /oHashSetTest2010.exe

I really see different results =)

+1
source

More articles:


All Articles