Re: What is a==b supposed to do for two hash_sets?

[Matt Austern <austern at apple dot com>]

On Feb 1, 2005, at 1:14 PM, Chris Jefferson wrote:

> Lorenz Minder wrote:
> > Hi,
> > I was reading through the code of hash_set, when I spotted something
> > which looks really odd to me: Comparison of two hash_sets is done by
> > comparing the buckets one by one. To give the simplest possible 
> > example,
> > doing
> > 	#include <iostream>
> > 	#include <ext/hash_set>
> > 	int main(void)
> > 	{
> > 		__gnu_cxx::hash_set<int> x(1000), y;
> > 		std::cout << "x empty ? " << x.empty() << '\n';
> > 		std::cout << "y empty ? " << y.empty() << '\n';
> > 		std::cout << "x == y  ? " << (x == y) << '\n';
> > 		return 0;
> > 	}
> > gives the output:
> > 	x empty ? 1
> > 	y empty ? 1
> > 	x == y  ? 0
> > I think this is wrong: My feeling is that two hash_sets should be
> > considered equal iff they contain the same elements. I can't find any
> > statement saying so though, neither in SGI's documentation nor
> > elsewhere.
> > Is this a bug? Should I file a PR?
>
> One interesting point to note is that the unordered_set and company in 
> TR1 don't have == defined on them because it is quite hard to 
> implement efficently, particularily on multisets, although that 
> doesn't help with this bug right now...

Actually, Howard Hinnant came up with a tolerably efficient algorithm.  
We left == out of unordered_set for TR1 mostly because we weren't sure 
we could specify what it meant in all corner cases, because we weren't 
sure it was useful, and because it's always easier to add features than 
to remove them.

Strictly speaking, what hash_set should do to conform to the container 
requirements is to define x == y as x.size() == y.size() && std::equal 
(x.begin(), x.end(), y.begin()).  This would give it different behavior 
than what hash_set currently does, but probably no more useful.  Just 
leaving operator== out for unordered associative containers was 
probably the right decision for TR1.

			--Matt