Boost logo

Boost :

From: Daniel James (daniel_james_at_[hidden])
Date: 2007-12-08 05:11:40

Ion Gaztañaga wrote:
> Thorsten Ottosen wrote:
>> I vote to accept this library. The documentation is very nice.
> Thanks for the vote.

Thank you from me as well.

>> One thing puzzled me though:
>> (see
>> "The containers hash or predicate function can throw exceptions from erase"
>> Under what cicumstances can/should/would I construct a ahsh or predicate
>> that throws? I mean, the hash computes an integer, and comparisons reads
>> data to determine its answer.
>> This migth be what the standard requires, but it certainly seems
>> non-intuitive. Why not just require that neither hash nor predicates can
>> throw?
> The same could be said about Predicate for ordered containers like
> std::set/map. I haven't seen a practical case where the comparison could
> throw. But standard library experts should answer this better than me.

One example where they could throw is if the hash function used a
numeric type which throws an exception when it overflows (which does
suggest a buggy hash function but there you go). Another is that the
data required to evaluate the hash function or check for equality is
expensive and is lazily evaluated. For example, if you had a class which
represents file, and based your equality test on calculating the SHA-1
signature then you might only calculate it when required - which could
be a call to the hash or equality function.

> Certainly, Daniel has tried to achieve strong exception guarantees and
> the implementation becomes quite complicated if comparison/hash throws.
> Double buffering and other tricks are needed. I think this is a very
> good question both for boosters and people from the LWG.

Dealing with a call to comparison and hash isn't that bad - the
implementation of the insert functions is a little intricate because of
the exception requirements. The main problem is if the copy constructor,
assignment or swap calls. (Ion knows all of this, it's for the benefit
of everyone else).

If either objects throw an exception while swapping or assigning a
container it could leave the hash and comparison in an unknown state
which would make the object invalid. To avoid this I store two of each,
and a pointer to the current functions. And manipulation is done on the
ones that aren't in use and when finished the pointer is switched to the
new functions, making the operation atomic.

The main cost is the memory use of the main container object. Instead of
containing 2 small objects, it contains 4 small objects and a pointer -
on 32-bit x86 this typically means an extra 6 bytes, although if the
hash or equality object has members it can be more. I don't see this as
a significant problem because the memory required for the container's
buckets and nodes is typically much larger.

Without doing something like this, I don't think the container could use
a boost::function for its hash or comparison object and meet the current
standard's requirements. The requirements could be weakened to say that
after such an exception the only thing you could with the container is
destruct it, but that would be inconsistent with the rest of the
standard library.


Boost list run by bdawes at, gregod at, cpdaniel at, john at