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
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 hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net