Re: [boost] Boost.Bimap - Informal Review Request

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-08-10 07:43:28

----- Mensaje original -----
De: John Maddock <john_at_[hidden]>
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