[boost] Re: Interest in bidirectional map?

From: David B. Held (dheld_at_[hidden])
Date: 2002-10-22 14:00:28

Joaquín Mª López Muñoz wrote:

> I've had a look at the docs of your map,

Really?  Where did you find those?  I don't believe I've written any 
documentation for it. ;)  If I did, and don't know about it, I'd like to 
see what I forgot I wrote! ;)  In fact, I didn't even say where one 
could look at it.

> and seems to me a fair amount of work has to be done in order to 
> integrate the features of bimap into boost::map.

Yes.  Very true.  But the idea is to put that hard work to good use by 
generalizing the concept of a map even further than I have, so that all 
of the maps in question (std::set, map, and bimap) become special cases.
As an analogy, consider the progression from std::pair<> -> 
boost::tuple<>.  It may involve a complete redesign of both maps, but 
then it could result in something much more useful and powerful, as well.

> * 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.

Ok, then you did it the way I assumed.  You essentially interleaved two 
trees over one set of nodes.  This can be accomodated somewhat already 
in my map design, since the node type is a policy.  For a single-key 
map, you simply provide single-threaded nodes.  For a multi-key map, you 
provide nodes that have as many tree pointers as necessary.  I had to 
make the node type a policy to support efficient indexing (you don't pay 
for indexing if you don't use it).

> * 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 bm;
> bm.from[1]=2;
> bm.to[10]=8;
> bm[7]=6; //no memberspace specified, from assumed.

Yes, I saw this discussion in your Annex.  However, I obviously didn't 
study it closely enough to notice that this is how you support the 
subscripting operator over both keys.  I like it.  Clearly, it can be 
generalized to more than 2 keys, as well.  Possibly a syntax like this 
could be possible:

nmap map;
map.key<1>["joe"] = employee_record;
map.key<2>["123-45-6789"] = employee2;
employee_id = map[35]; // defaults to .key<0>

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

That doesn't concern me.  I have no problem hacking the interface of my 
map, since I'm the only one who uses it right now (that I know of).  And 
even though I put it in the boost namespace, beware that it's not a 
Boost library.

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

Yes, indeed.  Like I said, the bidirectionality cost comes primarily in 
the form of extra memory usage.  However, the bulk of this memory 
overhead is due to the node type, and not the actual tree type(s) used. 
  By making the node type a policy, it should be possible to swap in any 
interface-compatible node type, supporting one, two, or n-key maps and 
sets.  Now, the actual map interface would have to be modified to 
support the multiple keys, but that incurs no overhead.  Functions that 
don't get called don't get generated.  Types that don't get used don't 
get instantiated.  This is, of course, the philosophy of Loki::SmartPtr.

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

Actually, I'd like to see the implementation, if you don't mind.  If you 
could upload it to the files area or the sandbox, I would appreciate it. 
  Also, since you have experience working with bimap, I was hoping you 
could help design a generalized node interface suitable for multiple-key 
trees.  Ideally, the map would be able to select the actual tree 
representation from the trees library being discussed, but that sounds 
like a lot of work that I don't want to mess with right now.

Part of the reason I haven't pushed for a review of my map is because I 
haven't had much time to work on it, and partly because I was afraid it 
was not sufficiently general to have a wide audience (though I 
personally feel it is an improvement over std::map, and can be a drop-in 
replacement, making that a compelling reason alone).  Yet another reason 
is that the policies were intimidating.  The map has seven template 
parameters, which is enough to make some programmers cringe in horror. 
However, progress in building an integrated policy adaptor for 
Loki::SmartPtr gives me hope that the large number of policies is no 
longer a problem.  Of course, this is possible because of the incredibly 
powerful facilities provided by MPL.

But seeing someone else using a funky map convinces me that a more 
generalized map is indeed useful, and that a policy-based design is the 
right way to go (I personally find the four std set/map types an 
abomination of duplication).  If you have more time than I, I hope you 
will take a close look at the node policies, and see if there is an 
obvious way to generalize them in support of multiple keys.  I know they 
are not very orthogonal right now, but that is primarily because I 
couldn't imagine other kinds of nodes that would be useful to use with 
the map.  If you haven't figured it out already, the map is in the boost 
sandbox (I imagine that's where you found the "docs").

Dave