----- Mensaje original ----- De: John Maddock <john@johnmaddock.co.uk> Fecha: Jueves, Agosto 10, 2006 11:13 am Asunto: Re: [boost] Boost.Bimap - Informal Review Request [...]

However, looking at the reference docs for the list view, I'm confused, for example what is:

O(I(n)) ?

Looked a lot like a mis-spelled O(log(n)) when I looked at the html.

What is O(D(n)) , O(R(n)) , O(M(n)) ?

None of these have immediately obvious meanings to me.

This notation is inherited from Boost.MultiIndex, so let me explain it briefly: the problem with documenting complexities for B.MI is that the overall O() estimate for a given operation depends on the number and type of indices the container is composed of: for instance, inserting into a container with a hashed index and a list-like index is O(1), but if we add an oredred index (which is based on a rb-tree) then the overall insertion complexity raises to O(log n). To document all this with precision, I analyze (complexity-wise) every operation in terms of six "primitives": * copying, * insertion, * hinted insertion, * deletion, * replacement, * modification, Each index, viewed in isolation, is characterized by a so-called complexity signature composed of functions c(n),i(n),h(n),d(n), r(m) and m(n). We use uppercase to refer to the sum of all individual contributions, for instance C(n)=c1(n)+...+cN(n) where ci is the copying complexity of the i-th index. Then, I can say that insertion into a multi-index container is O(I(n)): the exact expression of I(n) can be then calculated by summing the correspoding i(n) of each index, which are given in the reference. This is all explained in http://boost- consulting.com/boost/libs/multi_index/doc/reference/indices.html#comple xity_signature and also replicated (in the context of Boost.Bimap) in the reference of this lib. Is this clear now?

Thanks, John.

Joaquín M López Muñoz Telefónica, Investigación y Desarrollo