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

From: John Maddock (john_at_[hidden])
Date: 2006-08-10 05:13:46

Matias Capeletto wrote:
> On 8/9/06, John Maddock <john_at_[hidden]> wrote:
>> Matias Capeletto wrote:
>
>>> * What do you think of the design of operator[]?
>>>   Is there a better way to be coherent with the stl that does not
>>> imply
>>>   throwing exceptions?
>>
>> I don't follow, can you explain or link to the relevant part of the
>> docs?
>
> In the STL unique associative containers (like std::map), operator[]
> first makes an insertion if
> the key element was not in the container. In addition, the container
> has no constraints in the data types, so it is an operation that never
> fails.
> We want to maintain a coherent behaviour between the extended mapping
> framework and the quite established STL one-side-oriented one, and
> that imply respecting in the best possible way each operation. For
> example, an insertion in a map view of a bimap may failed because the
> there are conflicts with the constraints from the other side. The
> standard insertion returns false when it fails, so it is very straight
> forward to extend it to the new framework.
> operator[] on the other hand, is quite a challenge. There are several
> possible ways to extend it. We (In fact, my mentor make me change my
> original implementation) opted for the most conservative
> implementation. When operator[] does not behaves exactly as the
> original counterpart, an exception is thrown.

OK understood, throwing seems like the most reasonable solution here.

>>> * A big part of the library implementation is ContainerAdaptor.
>>>   Do you deem Boost.ContainerAdaptor worth eventually proposing to
>>>   Boost?
>>
>> Where is container_adapter described?
>
> It is not yet documented.
> Here is an extract of Boost.Bimap rationale section:
>
> "The core of bimap will be obviously a multi_index_container. The
> basic idea to confront the implementation of the bimap class is to use
> iterator_adaptor  to convert the iterators from Boost.MultiIndex to
> the std::map and std::set behaviour. The map_view and the set_view can
> be implemented directly using this new transformed iterators and a
> wrapper around each index of the core container. However, there is a
> hidden idiom here, that once coded will be very useful for other parts
> of this library and Boost.MRU library. Following the ideas from
> iterator_adaptor, Boost.Bimap views are implemented using a
> container_adaptor. Basically there are several template classes (for
> example map_adaptor  and set_adaptor) that takes a std::map signature
> conformant class and new iterators, and adapts the container so it now
> use this iterators instead of the original ones. For example, if you
> have a std::set<int*> you can build other container that behaves
> exactly as a std::set<int> using set_adaptor and iterator_adaptor. The
> use of this two tools together is very powerful. A container_adaptor
> can take classes that do not fulfill all the requirements of the
> adapted container. The new container must define these missing
> functions."

Sounds interesting, and might well be useful in it's own right, but I would 
place Bimap and a MRU cache higher up my wish list.

>> 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?

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

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

Hopefully the list would be rather short :-)

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.

Thanks, John.