----- Mensaje original -----
De: Elisha Berns
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?