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 http://igaztanaga.drivehq.com/unordered/unordered/comparison.html)
"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. Daniel