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

From: joaquin_at_[hidden]
Date: 2002-10-22 16:15:31

----- Original Message -----
From: "David B. Held" <dheld_at_[hidden]>
Date: Tuesday, October 22, 2002 9:00 pm
Subject: [boost] Re: Interest in bidirectional map?

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

In boost-sandbox/boost-sandbox/libs/map/doc

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

Yes, I think this can be approached the way you suggest. There's
another trick coming into play here (I'll sitck to bimap for
simplicity, but the problem remains even more challenging
for n-maps): if the nodes are pairs of (key1,key2) values, then
there's no problem with accessing them from key1-iterators:
the first member of the element pointed to is the key, the second
the value. On the contrary, the situation is reversed for
key2-iterator, and this is not what one expects from a regular map
(since both iterators behave as much as possible as regular
map iterators). To acommodate this, key2::values are not std::pairs,
but rather inv_pairs (more info on my docs), and generic code
won't notice the trick, accessing in both cases to elements whose
first element is the key. How to generalize this to n keys
is a non-trivial task.

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

This cannot be generalized so neatly. Memberspaces rely
on member objects whose name matches that of their type. This cannot
be extended to things like key<1>, which obviously doesn't
qualify as a name for an object.

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

It is available right where the docs is, at
http://www.codeproject.com/vcpp/stl/bimap.asp

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

Time is scarce (I guess the same happens to you), but I'll
definitely have a look at your code and think about it.

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

> 
> Dave
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost