Unordered associative containers and swap's exception safety
Hello everyone, I've got an exception safety problem implementing the hash containers. The draft standard says (from 6.3.1.1): '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 [equality] Pred object (if any).' This is a problem, because for the container to be valid, its hash buckets, equality predicate and hash function need to consistent. Since both the hash and predicate can throw, this is impossible (or hard?) to achieve. If swapping/copying the first one succeeds, and the second one throws they won't match. Any ideas on what I should do? I don't think this can cause any major problems, like memory leaks or access to unowned memory, but it can cause unpredictable behaviour - since equal keys can end up in different buckets. Basically the invariant ends up totally broken. The only solution that I've come up with, is to store the two function objects in a seperate structure, allocated on the heap, so that only pointers have to be swapped. But this seems unfortunate since most function objects won't throw. This problem also applies to the copy assignment operator. Daniel
Daniel James wrote:
Hello everyone,
I've got an exception safety problem implementing the hash containers. The draft standard says (from 6.3.1.1):
'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 [equality] Pred object (if any).'
This is a problem, because for the container to be valid, its hash buckets, equality predicate and hash function need to consistent. Since both the hash and predicate can throw, this is impossible (or hard?) to achieve. If swapping/copying the first one succeeds, and the second one throws they won't match. Any ideas on what I should do?
I don't think this can cause any major problems, like memory leaks or access to unowned memory, but it can cause unpredictable behaviour - since equal keys can end up in different buckets. Basically the invariant ends up totally broken.
The only solution that I've come up with, is to store the two function objects in a seperate structure, allocated on the heap, so that only pointers have to be swapped. But this seems unfortunate since most function objects won't throw.
Another option is to double-buffer the hash function and the predicate. Hash hash_[ 2 ]; Pred pred_[ 2 ]; int which_; void swap( this_type & rhs ) { using std::swap; hash_[ !which_ ] = rhs.hash_[ rhs.which_ ]; pred_[ !which_ ] = rhs.pred_[ rhs.which_ ]; rhs.hash_[ !rhs.which_ ] = hash_[ which_ ]; rhs.pred_[ !rhs.which_ ] = pred_[ which_ ]; // do other things that may fail // commit which_ = !which_; rhs.which_ = !rhs.which_; } or something like that. Untested.
Peter Dimov wrote:
Another option is to double-buffer the hash function and the predicate.
I think I'll go for this. It's a pity to require the extra expense, but it'll only really be noticeable if you have a complicated function object. thanks, Daniel
Daniel James wrote:
[...] '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 [equality] Pred object (if any).' [...]
Frankly, I don't understand why Hash or Pred should be copied at all during a swap. If swapping Hash or Pred via std::swap() would throw, it seems like a no-brainer that the authors of Hash and Pred should provide a non-throwing swap() which can be discovered via ADL. In fact, I don't see any good reason why the standard shouldn't simply require that Hash and Pred provide a non-throwing swap() if std::swap() would throw. Dave
participants (3)
-
Daniel James -
David B. Held -
Peter Dimov