cannot create a dense_hash_map of dense_hash_set

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Make a dense_hash_map<uint32_t, dense_hash_set<uint32_t> >
2. set_empty_key on the map
3. at the initial insertion of a set into the map, set_empty_key on the set
before inserting a copy into the map

What is the expected output? What do you see instead?
I expect it to work.  Instead there is an assertion that the empty key is
not yet set

What version of the product are you using? On what operating system?
I'm using 1.1 on ubuntu

Please provide any additional information below.

Original issue reported on code.google.com by brian.budge@gmail.com on 6 Apr 2009 at 4:22

[GoogleCodeExporter]

Interesting.  The problem is actually in the call to the dense_hash_map's
set_empty_key().  Due to an infelicity in the design of set_empty_key, it 
actually
stores a key/value pair internally.  When you call set_empty_key(0), or 
whatever, it
turns that into
   internal_struct.set_empty_key(pair(0, dense_hash_set())

It's that default dense_hash_set that causes problems, because it doesn't have 
an
empty key.

I think the right fix is to fix the internal API of set_empty_key.  I remember
there's a reason that was hard, but don't now remember what it was. :-(  
Hopefully
this won't be too bad to fix.

In the meantime, you can work around this in one of several ways:

1) Just remove the assert from your source code.

2) Write a subclass of dense_hash_set that sets the empty key in its destructor
(assuming you always use the same empty-key for all sub-sets).

Original comment by csilv...@gmail.com on 6 Apr 2009 at 5:56

• Changed state: Accepted
• Added labels: Priority-Medium, Type-Defect

[GoogleCodeExporter]

Great.  I'll try your workarounds for the time being.  

Thanks for the help.
  Brian

Original comment by brian.budge@gmail.com on 6 Apr 2009 at 6:00

[GoogleCodeExporter]

Ah, I remember why I had to take a value -- when we create an empty 
dense_hash_table,
it has 5 buckets (or however many) filled with the empty key.  This is the way
dense_hash_table works, and why it is (hopefully) fast: that it creates buckets
early, rather than creating them on demand.

However, these empty buckets have to be initialized to *something*.  What 
they're
initialized to is the default value-type.  So we need to create a 
dense_hash_set with
the default constructor.

Another fix I neglected to mention before is that you have the key be a pointer 
to a
dense_hash_set, rather than a dense_hash_set itself.  This is likely the best
solution, and the fastest, since otherwise when you resize the dense_hash_table,
you'll have to copy all those dense_hash_sets around, which could be quite slow.

That would also avoid the problem here.

I think the best fix I can make is to document that the value for 
dense_hash_map has
to have a zero-arg default constructor.  Since that doesn't really fix your 
problem,
I'm closing this as WontFix.  But I'll document the potential workarounds as 
well.

Original comment by csilv...@gmail.com on 6 Apr 2009 at 6:10

• Changed state: WontFix

[GoogleCodeExporter]

Ah, I should have thought of the pointer thing myself.  I might even keep a pool
around so that I don't have to keep allocating and deallocating them (this is a
common operation).

Thanks again :)

Original comment by brian.budge@gmail.com on 6 Apr 2009 at 6:20