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
>>> throwing exceptions?
>> I don't follow, can you explain or link to the relevant part of the
> 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
> 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
>> 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
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:
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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk