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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users