Re: [boost] Status of Hash Collections?

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-10-28 12:07:16

Hello Aristid,

----- Mensaje original -----
De: Aristid Breitkreuz <aribrei_at_[hidden]>
Fecha: Sábado, Octubre 28, 2006 2:41 pm
Asunto: Re: [boost] Status of Hash Collections?
Para: boost_at_[hidden]

> What about multi_index? They have support for hashing.
> 
> But quite probably stand-alone hashed containers would be
> good to for two reasons:
>     1. TR1 compliance
>     2. Possibly the multi_index implementation or
>        interface has some serious drawbacks
> 
> Am I mistaken?

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.

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.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo