On 8/9/06, fred bertsch <fred.bertsch@gmail.com> wrote:

That sounds interesting, but I couldn't click on the online docs on your webpage.

The link is in the word: "here", not in the picture. Best Regards Matias

On 8/9/06, John Maddock <john@johnmaddock.co.uk> 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. It is documented in the reference section. Here is the direct link: http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/referen...

...

* 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." You can browse ContainerAdaptor code from the Boost.Bimap doxygen docs, here it is a direct link: http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/doxydoc/namespacebo...

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/referen...

That aside, it looks like a very successful SOC to me, and to be a worthy addition to Boost. Very nice looking docs too BTW!

Thank you very much for the positive review :) Best Regards Matias

Paul A Bristow wrote:

| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Matias Capeletto | Sent: 09 August 2006 14:59 | To: boost@lists.boost.org | Subject: Re: [boost] Boost.Bimap - Informal Review Request | | On 8/9/06, John Maddock <john@johnmaddock.co.uk> wrote: | | > That aside, it looks like a very successful SOC to me, and | to be a worthy | > addition to Boost. Very nice looking docs too BTW!

Nice docs indeed - though I noticed a intially puzzling spelling mistake at

http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/doxydoc/namespacebo ost_1_1bimap_1_1tags.html

"A ligth non invasive idiom to tag a type"

ligth should be 'light'?

This appears twice. It looks like it should indeed be "light" as the correct spelling is used towards the bottom of the page. There are rather a lot more typos on this page: * "can not inherited" - should this be "cannot inherit"? * "another level of indirection, an example ..." is a run-on sentence. Replace the comma with either a semicolon or a full stop (a period), thus: "indirection; an example" or "indirection. An example" * "are intend" should be "are intended" * "user do not" should be "user does not" * "suitted" should be "suited" * "As an optional" - should this be "As an option"? * "in the indexed by declaration" - this doesn't seem to make sense, but I haven't looked at what it refers to * "refered" should be "referred"; "referred by it" should be "referred to by it" * "writer point of view" should probably be "writer's point of view" * "more simpler" should be "simpler" * "built-in", "non-invasive" (in three places), "user-friendly" (in two places) and "multi-index" should all be hyphenated. Could I respectfully suggest that you ask someone to proof-read your documentation? This will greatly aid the user. Paul (hoping he hasn't made any typos of his own in this email)

Matias Capeletto wrote:

On 8/9/06, John Maddock <john@johnmaddock.co.uk> 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/referen...

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.

On 8/10/06, John Maddock <john@johnmaddock.co.uk> 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/referen...

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/referen... Best regards Matias

On 8/10/06, John Maddock <john@johnmaddock.co.uk> wrote:

Matias Capeletto wrote: Perhaps you could link the complexity guarentees to the explanation? Should just be a regex search and replace job, and it would save a lot of folks asking the same question :-)

Yes, I have to put anchor all over the docs and cross-link the explanations. The thing is that after two and a half moth of work, I couldn't wait any more for the presentation :) Another item in Boost.Bimap TODO list. Best Regards Matias

Matias Capeletto wrote:

Yes, I have discussed a policy approach with my mentor. In fact, the first implementation of operator[] was to ignore the insertion is something goes wrong. I like the idea of a policy to control this behavior but I have to find a way to maintain the bimap template parameters as simple as they are today. The problem now is to determine if throwing exceptions is the better default behaviour. The policy approach can be implemented as a future feature maintaining backward compatibility.

That all sounds very reasonable. Throwing an exception seems like a good default behavior since pretty much all of the other behaviors can be obtained from that using try/catch or checking for collisions before the insertion. In addition, I know that my own uses of bimaps threw an exception when there were collisions. David

On 8/16/06, Julio M. Merino Vidal <jmmv84@gmail.com> wrote:

On 8/9/06, Matias Capeletto <matias.capeletto@gmail.com> wrote:

...

Hello,

Boost.Bimap, my SoC project is ready to confront the list. The project is being mentored by Joaquín López Muñoz. I want to publicly thank him.

With Boost.Bimap you can create associative containers where both types can be used as key. You can think a bimap<X,Y> as a merge of a std::map<X,Y> and a std::map<Y,X>. The learning curve of bimap is almost zero if you know how to use standard containers. [...]

I can't provide a real review of the library because I have not used it. So far, I've only seen the documentation but I'd like to say that the documentation itself seems very complete and looks great. Aside that, from what I gather from the examples, the library's interface seems very easy to use, at least at a basic level.

Thanks Julio! I really need some usage feedback, so please tell me how its feel when you managed to use it. BTW, I am looking at Boost.Process docs now... Enhorabuena! :) As far as I have read, it really sounds. I will post my review later. Best Regards Matias