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

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2006-08-10 10:31:11

On 8/10/06, John Maddock <john_at_[hidden]> wrote:
> Matias Capeletto wrote:
>
> >> If I ask for a bimap<list_of<A>, B> do I get std::list complexity
> >> guarentees when accessing bimap.left, or does it just look like a
> >> list, but not really behave like one?
> >
> > You get the std::list complexity guarantees. To be fair you get a very
> > close approximation to it.
> > For example, insertion operations are affected by the other selected
> > views. The complexity of each operation of the library is documented
> > in the reference section of each set type specifiers. Here is a
> > direct link
> > to the list_of reference:
> >
> > http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/reference/list_of_reference.html
>
> I did see that they were there, what I was trying to avoid was proof-reading
> all the reference docs and comparing the complexities to the std :-)
>
> So maybe what I was asking for was for each container-view-type:
>
> * Syntactic differences:
> What are the breaking changes in syntax compared to the std counterpart?

The only syntactic difference is that you can not construct empty views.

> * Semantic differences:
> What are the changes in behaviour compared to the std counterpart?

The change is in the insertion functions. They may now fail because
the insertion may be banned by the other views.
operator[] is different too.
The other difference is that iterators return const objects. Joaquin has
post a feature that will alleviate this in some cases.

> * Complexity differences:
> What are the differences in complexity compared to the std counterpart?

Again, the main change is in the insertion functions. But the complexity of
deletion or modifying is affected too. But as Joaquin explained this is because
we have to update each view.
The important thing is that you get the look up complexity guarantee equal to
the standard containers.

> However, looking at the reference docs for the list view, I'm confused, for
> example what is:
>
> O(I(n)) ?

Look at Joaquin post first and then read:

http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/reference/bimap_reference.html#boost_bimap.reference.bimap_reference.complexity_signature

Best regards
Matias