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.