Оператор равенства <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 не хранит элементы в некотором порядке, определенном хэш-функцией ... почему? Обратите внимание, что этот код работает в VS2008 с использованием stdext :: hash_set.

Answer 1

Похоже, что сравнения равенства нарушены для hash_set и unordered_set в Visual C ++ 2010.

Я реализовал наивную функцию равенства для неупорядоченных контейнеров, используя язык из стандартного , цитируемого Мэтью , чтобы убедиться, что это ошибка (просто чтобы убедиться):

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.

Answer 2

Наконец нашел ссылку в окончательном проекте на 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 ² ) из-за требования реализации линейной цепочки.

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 

с использованием командной строки vs2010:

cl.exe HashSetTest.cpp /oHashSetTest2010.exe

Я действительно вижу разные результаты =)