Re: [boost] [multi_index][hash][rfc] Hashed indices preview + Boost.Hash

From: John Maddock (john_at_[hidden])
Date: 2005-02-19 12:02:24

> 1. Hashed indices are modeled according to the latest TR1 draft, with
> some significant diversions:
> 1.1. erase() does not throw ever, even it the user-provided Hash object
> throws. This is imposed by the general framework of Boost.MultiIndex.
> This goodie does not come for free: if the Hash object throws, erase()
> decays to a linear search. Not that there's any alternative, but I'd
> like
> to point it out.

Sounds reasonable, I wouldn't normally want erase to ever throw anyway, and 
there has been some discussion on the C++ committee list about requiring 
function hash object construct/copy/swap/invoke to not throw anyway, as 
otherwise some things are unreasonably hard to implement.

> 1.2. insert() has strong exception safety (TR1 only requires basic.)
> Again, the way Boost.MultiIndex is designed forces this.

Good, IMO.

> 1.3. hash indices iterators are bidirectional.

Good.

> 1.4. Usual implementations use one pointer per bucket, whereas
> Boost.MultiIndex has two pointers per bucket. This addresses potential
> performance problems of insert() and erase() under low load conditions,
> as discussed in
> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
> issue 6.14. Is this convenient?

Well it's not unreasonable, you need what you need.

> 2. The material is complete except for a section in the tutorial and
> possibly
> one more example (example 8 already exercises hashed indices.) Tests
> fully sport hashed indices. The reference is also updated.
> 3. All in all, I'd greatly appreciate your comments on this:
> suitability,
> documentation, performance, etc. I plan to commit this to the CVS
> if nobody objects in a reasonable amount of time (a couple of weeks.)
> I'm open to all kind of suggestions --I'm eager to recieve them, as it
> happens :)

Sounds reasonable, no one normally objects to library updates - and actually 
since some folks have asked for a release soon, it's better done sooner 
rather than later, if you're going to do it at all.

> 6. Yet, this hasn't undergone any formal review, so some of you might
> (with reason) object to its being commited to the CVS. From our point
> of view, we have three valid alternatives:
>  * Boost members agree to have it in CVS without more ado.
>  * As this is used by Boost.MultiIndex, Boost.Hash is suitable for
>  fasttrack review.
>  * This is untolerable and the library should be push_back()'ed to
>  the review queue. Meanwhile, Boost.Hash should live as an impl
>  detail of Boost.MultiIndex.

I don't see how you can place it in a detail namespace if users are going to 
be expected to (possibly) provide their own specialisations of the hash 
function object.

I've no objection to either a fast track review, or just adding to cvs,

John.