Boost logo

Boost Users :

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)

> 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
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?

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at