Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2006-11-01 11:36:07


John Maddock wrote:
> Daniel James wrote:
>> There is one problem that might be more serious. I'm not sure if
>> Allocator::address or the allocator comparison operators are allowed
>> to
>> throw an exception. If they can, the implementation doesn't meet the
>> exception requirements. Actually, if the allocator comparison
>> operators
>> can throw then it might not be possible to meet the swap exception
>> requirements for most of the standard containers. So maybe I'm missing
>> something. I haven't looked into this in much detail yet.
>
> I don't know about address, but you are allowed to assume that all
> allocators compare equal. Does that help?

The standard allows ignoring equality and also allows ignoring pointer,
reference and other typedefs but I would like to make boost unordered
containers compatible with Boost.Interprocess shared memory allocators
and avoid writing my own unordered container.

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.

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.

According to TR1:

6.3.1.1 Exception safety guarantees [tr.unord.req.except]

1 For unordered associative containers, no clear() function throws an
exception. No erase() function throws an exception unless that exception
is thrown by the container’s Hash or Pred object (if any).

2 For unordered associative containers, if an exception is thrown by any
operation other than the container’s hash function from within an
insert() function inserting a single element, the insert() function has
no effect.

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).

4 For unordered associative containers, if an exception is thrown from
within a rehash() function other than by the container’s hash function
or comparison function, the rehash() function has no effect.

I haven't implemented these containers myself, but aren't these
exception guarantees an overhead when implementing these containers?

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.

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?

Regards,

Ion


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk