Re: [Boost-users] Container/Algorithm question

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2005-07-15 18:14:34

----- Mensaje original -----
De: Elisha Berns <e.berns_at_[hidden]>
Fecha: Viernes, Julio 15, 2005 7:40 pm
Asunto: Re: [Boost-users] Container/Algorithm question

> Thanks Joaquin, 
> 
> Your code worked perfectly and probably sped up the application by a
> factor of 3.

Such a large speedup hints at an improvement on algorithmic
complexity. My proposal has O(log n) insertion and O(log n)
lookup.

>  One thing though, out of curiosity, what kind of 
> containerdoes Boose.MultiIndex use internally?

Strictly speaking, Boost.MultiIndex does not rely on
any external container. A multi_index_container, though,
is composed of several indices, each of which is roughly
modelled after some std:: container. Ordered indices, which
are the ones used in this case, behave like std::set, so the
proposal is equivalent to a hand made container using
two std::sets --actually, it should be more efficient
than the hand made option.

>  And is there any 
> way to further
> optimize Boost.MultiIndex by specifying what type of container is used
> internally?
> 

Yes. Starting with Boost 1.33. Boost.MultiIndex provides
hashed indices, which, if properly used, can yield
better performance both at insertion and lookup wrt ordered
indices.
I'm compiler-disabled during weekends, so let me come back to
you next Monday with alternatives to my first proposal
taking advantage of hashed indices.

Have a nice weekend,

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

PS: I'm curious, in which context do you need this
kind of rather odd container?