Boost logo

Boost :

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

This is all explained in


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, gregod at, cpdaniel at, john at