[boost] Re: Interest in bidirectional map?

From: David B. Held (dheld_at_[hidden])
Date: 2002-10-22 17:47:07

joaquin_at_[hidden] wrote:

> [...]
> In boost-sandbox/boost-sandbox/libs/map/doc

Heh.  I wish I could call that file "documentation", but I'm glad you 
got something out of 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).

First of all, let me say that bimap is not a std-conforming map, even 
though you have striven greatly to make it so.  Neither is my map, 
except in the std-compatibility configuration.  To be honest, that 
doesn't really bother me.  I think the concepts defining std::map are 
fine for std::map, but I think more importantly, we need to define new 
concepts that allow us to work naturally in a new framework.  If that 
means that some map configurations are not Pair Associative Containers, 
I say: So be it.

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

Yes, I noticed your bit about inv_pairs.  I think the appropriate thing 
to do is to define a new Key Tuple concept appropriate for Generalized 
Associative Containers.  This could eliminate the inv_pair gymnastics 
altogether, and simply let us implement whatever is most natural.  We 
can always provide Pair Associative semantics for the compatibility case 
(which I already provide for).  I find them much too limiting for other 
cases.

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

Yeah, that was a pretty off-the-cuff suggestion.  What do you think of 
my slightly less elegant suggestion to Dirk?  It doesn't scale as 
nicely, but if we use the Preprocessor lib, we can make the limit 
user-configurable.

template <typename K1, typename K2, ...>
class map
{
public:
     template <typename T>
     class key
     {
         // ...
     public:
         int operator[](T) { return 5; }
     };
     key<K1> key0;
     key<K2> key1;
};

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

Apparently, "Download source files" at the top of the page was too 
obvious for my limited comprehension. ;)

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

Great.  Now that I can look at your code, I'll be thinking hard too.

Dave

P.S.  My first reaction to memberspaces was: "Oh, he's using public data 
members.  Hmm...there goes data-hiding."  However, I believe that proper 
manipulation of the types (making them non-copyable, limiting 
construction, etc.) allows it to be a suitable technique for introducing 
new lexical scope.  I'm a bit uncomfortable with the reinterpret_cast<>,
and would prefer it if there were a way to make the "parent access" more 
portable.  In fact, I see that there are probably problems with my 
template suggestion and your memberspace implementation.  In particular, 
this is going to be a trick:

     prebimap& owner()
     {
       return *reinterpret_cast<prebimap*>(
         reinterpret_cast<char*>(this)-offsetof(prebimap,from));
     };

First, getting the right params to pass to offsetof from within template 
code might simply be impossible.  Second, I would feel a lot more 
comfortable if this could be accomplished in a portable way with 
static_cast<>ing to/from void*.  However, I'm not sure that this is even 
necessary.  If you simply stored an "owner pointer" in each memberspace, 
you could eliminate the casts altogether.  Since a map is typically a 
large object anyway, a few extra pointers should not be a prohibitive cost.

Second, the code duplication of the from and to memberspaces is just the 
kind of thing we'd like to eliminate with a proper generalization. ;)

Third, an integration of your bimap into my map framework will make it 
even more efficient.  I thought you had a custom tree type that you 
stored your nodes in.  I see that you are simply using two std::set<>s, 
which, while effective and straightforward, is not as efficient as 
creating custom tree nodes and implementing the interleaved sets 
directly.  Designing an appropriate node type is going to be an 
interesting, non-trivial challenge. ;)  There is some minor potential 
for costs savings by packing the node color for multiple keys, but the 
simple fact of the matter is that multi-key maps have fat nodes. ;) 
There is also space savings because instead of storing from_type* and 
to_type* in each node, as well as having from_type & to_type on the 
heap, you can store them both directly in the tree nodes, which saves 
two pointers and three heap allocations.  For a data structure that's 
already criticized for being big and slow, that's a significant savings. 
;)  Well, those are a few things to think about...