Re: [boost] Re: Interest in bidirectional map?

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2002-10-22 08:30:28

Hi David,

I've had a look at the docs of your map, and seems to me a fair amount
of work has to be done in order to integrate the features of bimap
into boost::map. On a first approach, these changes should be made
in order to accomodate bimap:

* bimap uses two sets of pointers to the elements (one for the
from part, other for the to part). I don't see how this
can be implemented using your rb_tree's, I guess two of them
would be needed.
* bimap uses an artifact I call memberspaces in order to
allow for duplicate operator[]s for the from and to part. To the best
of my knowledge, this trick hasn't used before, but it is not
fundamentally complex. With memberspaces, one can write
things like:

bimap<int,int> bm;
bm.from[1]=2;
bm.to[10]=8;
bm[7]=6; //no memberspace specified, from assumed.

With a little bit of PTS, memberspaces member functions can be
exported to the "global" memberspace when no ambiguity exists.
This techniques should have to be included in your boost::map.

One concern about inclusion of bimap into boost::map is the possible
overhead incurred even when no bidirectionality is need. I guess
policy classes can be used to approach this problem.
If you're interested in evaluating the suitability of including bimap-capabilities

in your boost::map, I'm open to your questions. The docs are
complete enough, and I can assist you with the more technical questions.

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

"David B. Held" ha escrito:

> joaquin_at_[hidden] wrote:
>  > [...]
>  > A couple of weeks ago I completed a bidirectional map
> > library in the spirit of C++ and posted it to CodeProject:
> > [...]
>
> I have written a policy-based map using STLport's implementation
> as a starting point.  It seems to me that your bimap could be
> implemented as a policy set of my map framework, which might help
> reduce library proliferation.  I don't see why one would never
> want a multi-bimap.  Allowing for unique and non-unique insert
> is a policy in my framework, and could be in yours as well.
> Also, my map supports indexing, which I see your page refers
> to in one of the links.  So your bimap could also potentially
> benefit from an indexing policy.  I'm not sure how your bimap
> is implemented, but it seems to me that you would want to
> interleave the two sets over the same tree nodes.  It could be
> possible to generalize map into an arbitrary-arity tuple ordering
> container.  After all, why not a trimap?  I could imagine this
> might be a useful way to implement a multi-field key index.
>
> Dave
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost