Re: [Boost-users] Container/Algorithm question

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-15 20:15:47

Joaquin,

Sorry to be the bearer of bad news, but for some reason the multi-index
container starts to fail for some larger number of pairs (a few
hundred).  The container doesn't/won't insert them, and to be honest, I
don't have a clue at this point why.  If you're up for it you might want
to stress test the code you sent me with thousands of unique pairs and
redundant pairs.

Elisha

> 
> ----- 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?
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users