
Boost : 
From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 20060810 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 misspelled 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 listlike index is O(1), but if we
add an oredred index (which is based on a rbtree) then
the overall insertion complexity raises to O(log n). To
document all this with precision, I analyze (complexitywise)
every operation in terms of six "primitives":
* copying,
* insertion,
* hinted insertion,
* deletion,
* replacement,
* modification,
Each index, viewed in isolation, is characterized by a socalled
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 ith index. Then, I can
say that insertion into a multiindex 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk