Re: [boost] Status of Hash Collections?

From: Aristid Breitkreuz (aribrei_at_[hidden])
Date: 2006-10-28 14:29:37

Hello Joaquin,

Thanks for the insight!

Am Samstag, den 28.10.2006, 18:07 +0200 schrieb "JOAQUIN LOPEZ MU?Z":
> Hello Aristid,
> 
> Well, I too support the inclusion of standalone TR1-compliant
> unordered containers into Boost, but since you mention
> Boost.MultiIndex hashed indices let me explain how they stand
> in comparison with unordered_[multi]set. The instantiation
> 
> multi_index_container<
>   Value,
>   indexed_by<
>     hashed_[non_]unique<identity<Value>,Hash,Pred>
>   >,
>   Alloc
> >
> 
> completely replicates the interface and complexity bounds of
> 
> unordered_[multi]set<Value,Hash,Pred,Alloc>
> 
> except that insert(const value&) returns a pair<iterator,bool>
> both for hashed_unique and hashed_non_unique indices, while
> unordered_multiset::insert returns an iterator.

Will hashed_non_unique ever return a false second there?

> 
> Due to design constraints, B.MI hashed indices provide the
> following guarantees that are *not* mandated for TR1 unordered
> containers:
> 
> * Iterator validity is preserved in any case during insertion
> or rehashing: TR1 allows for iterator invalidation when a rehash
> (implicit or explicit) is performed.
> * Erasing an element or range of elements via iterators does not
> throw ever, as the internal hash function and equality predicate
> objects are not actually invoked. 
> * rehash provides the strong exception safety guarantee
> unconditionally. TR1 only warrants it if the internal hash
> function and equality predicate objects do not throw.
> 
> These stronger guarantees might result in some performance
> penalties in the area of iterator increment, erase and
> rehash operations, though my measurings lead me to think
> that the actual impact is low or negligible.

Does this imply that implementing TR1 unordered containers on top of
B.MI would not impose a serious performance drawback? The interface is
nearly the same so writing a TR1 compliant wrapper should be ... doable,
right?

And it should be done if it shall be part of 1.35 :-).

Aristid Breitkreuz

PS: I hope 1.34 will come out soon now. (Who doesn't?)