Re: [boost] Status of Hash Collections?

From: Daniel James (daniel_james_at_[hidden])
Date: 2006-11-01 15:37:07

Ion Gaztañaga wrote:
> My bet is to use the option 3 for Issue 431:
>
> http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2004/n1599.html
>
> If comparing allocators throws, swap would throw, so this would 
> invalidate one of the best arguments of this option. I sincerely would 
> assume that comparing allocators does not throw, to obtain a no-throw swap.
>   
I think option 3 is best as well. I don't think this is actually a 
problem. The guarantee becomes something like, "swap is no-throw, as 
long as comparing and swapping allocators are no-throw operations." And 
really, I expect that allocators that throws in these circumstances are 
very rare, if they exist at all.

The problem is the swap requirements:
> 3 For unordered associative containers, no swap function throws an 
> exception unless that exception is thrown by the copy constructor or 
> copy assignment operator of the container’s Hash or Pred object (if any).
>   
Something probably should be added about allocators.
> Apart from this, the old implementation of Boost unordered supposed that 
> the hash function and the predicate can throw, something that I found 
> really nasty. If I remember correctly, there was a double-buffer trick 
> in the old implementation, that incremented the size of the hash.
>   
It's still there. Yes, hashes and predicates that can throw are a bit 
weird. But the standard specifically allows them. My implementation is 
never going to be the most efficient hash table. At the moment, the main 
object is certainly larger than it needs to be - I'm not even using EBO. 
But typically this won't be too when you consider the space used by the 
nodes and it will improve in the future. I'd quite like to have the 
first release support older compilers, and then the second discard them 
and improve the implementation. I expect several people would prefer me 
to skip the first part of that plan.
> I haven't implemented these containers myself, but aren't these 
> exception guarantees an overhead when implementing these containers?
>   
It's not too bad. There's the double buffer that you mentioned, and 
insert could be simplified if it didn't need to meet the requirements.
> When swapping, if the hash function's copy-constructor does not throw 
> but the predicate's copy constructor throws what's the state of the 
> half-constructed container? The only way to obtain strong guarantee 
> would be to have an array of two has functions and use an index or 
> member pointer that we could rollback.
>   
Yep, I've also got a similar problem with allocators. I have to choose 
either to store a single allocator - which causes problems in the 
destructor as I'll have to construct an extra allocator (at least two 
allocators are needed in the destructor - one for buckets and one for 
nodes) or I have to store multiple allocators leading to problems when 
swapping. Actually, I haven't dealt with that yet - I'm currently 
expecting a no-throw swap.
> This complicates the implementation a lot and it might have an space 
> overhead. Is realistic to have both a throwing pred and hash function? I 
>   have never used a comparison function or has that throws, is there any 
> real-life example of throwing hash and predicate?
>   
Not that I know of. But the standard feels the need to specify that they 
can. Normally I wouldn't care about these things, but it seems to me 
that when implementing a standard container it's worth being overly 
cautious.

Daniel