Re: [boost] Unordered associative containers and swap's exception safety

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-02-11 17:33:25

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.