Re: [boost] Bidirectional map preliminary submission

From: joaquin_at_[hidden]
Date: 2003-03-21 14:50:35

Hi George

----- Original Message -----
From: "George A. Heintzelman" <georgeh_at_[hidden]>
Date: Friday, March 21, 2003 7:38 pm
Subject: Re: [boost] Bidirectional map preliminary submission 

[stuff deleted]
 
> > 2. Pollution of namespace boost.
> > Apart from bimap, the following types and functions are already 
> defined> inside boost namespace:
> [snap]
> > Apart from bimap_base and possibly make_inv_pair, I'd like to 
> have all
> > of these
> > defined in an auxiliary namespace, but MSVC++, which is my work
> > compiler,
> > chokes at one point or another when tyring to do so.
> 
> That's odd. Lots of boost libraries use boost::detail or 
> boost::library_name::detail for implementation details. This 
> shouldn't 
> be a problem with MSVC++.

Yes, I think I've got to work more on this. I'm having
confusing errors dealing with globl swap functions when
pushing these auxiliary classes in inner namespaces. 

> 
> > 3. Nonconformances
> > To the best of my knowledge, there are two non-conformances in 
> the code:
> > 
> > * It is assumed that for these two classes (in simplified form 
> here):> 
> > template<typename A,typename B>
> > struct direct_pair
> > {
> >   A first;
> >   B second;
> > };
> > 
> > template<typename C,typename D>
> > struct inv_pair
> > {
> >   D second;
> >   C first;
> > };
> > it is asummed, I was saying, than a direct_pair<A,B> can be
> > reinterpret_cast'ed
> > to a inv_pair<C,D> (and vice versa) whenever A=D and B=C. 
> 
> Ugh. I know that this is almost certainly going to never be a 
> problem, 
> but I don't like it, even if just for the fact that it . Can you 
> summarize why this is necessary? Perhaps we can find a solution 
> which 
> doesn't require it.
> 
> I have taken just a brief look at the code, and I think I 
> understand 
> the driving motivation for this: You wanted the following behavior:
> 
> (in a bm where 1 <=> 2 )
> bm.from.find(1)->first = 1;
> bm.from.find(1)->second = 2;
> bm.to.find(2)->first = 2;
> bm.to.find(2)->second =1;
> 
> Right? Is there some other behavior that this machinery enables 
> that 
> I'm missing?

Yes, that's exactly the reason behind the direct_pair/inv_pair
trick.

> 
> Two comments: One is, both the memberspaces and the public data in 
> the 
> pair's could benefit from properties being part of C++. There's a 
> thread on comp.std.c++ about properties right now, and you might 
> consider contributing this use to that discussion.

Will look it up, thanx.

> 
> Second, I'm not sure that this motivation is strong enough to make 
> me 
> want the whole kit and kaboodle of the direct_pair, inv_pair, and 
> everything that you've set up. I don't really mind having to know 
> which 
> way my bimap is going and remember that I have to use the right 
> thing; 
> most bimap uses that I can imagine involve mostly bm.from[x] and 
> bm.to[y] which always take care of that for me.

I think you're a little misguided here; in fact, one should
never use direct_pairs or inv_pairs: they have been defined
so that you can treat each memberspace (viewed in isolation)
as a regular map, save the one-to-one constraint. Consider
this example:

bimap<int,string> bm;
bm.to.insert(make_pair("hello",1));

The code sees bm.to as a map from string to int in the same
way as bm.from is a map from int to string. You don't have
to invoke inv_pairs here at all, an std::pair is gladly accepted
and internally converted to an inv_pair with no extra cost 
(hence the reinterpret_cast stuff). The morale is: given
a bimap<A,B> bm you can treat bm.from in all respects as a
std::map<A,B> and bm.to as a std::map<B,A>.I hope I made
myself clear enough.

> 
> And, one thing I would like to see very much from a bimap is that 
> it 
> should be naturally generalizable to an N-map, where N of the 
> elements 
> are independent keys, having additional M elements of unkeyed 
> data, 
> carried along (M being 0 or 1 is good enough, given tuples, but 
> general 
> M would be nice syntactic sugar). Your implementation and 
> particularly 
> the direct_pair/inv_pair stuff seems antagonistic to such a 
> generalization.
> 

I'm afraid bimap is so strongly tied to the interface of
std::map that your proposed container could hardly be built
as a generilzation of it. BTW I'm working in a container like
you propose (modelled after set rather han map), but it'll take
long and won't resemble bimap at all.
So, IMHO bimap has to be regarded as the end of the road in
generalizing std::maps (unless someone with a brilliant mind
finds otherwise).

> Your implementation also leads to a tremendous amount of 
> duplicated or 
> near-duplicated code in the from and to memberspaces.
> 
> > * offsetof() is used for non-POD types. The types on which it is 
> used> are
> > arguably simple enough to be treated as POD (no virtual methods or
> > anything), but
> > then again the standard bans it. 
> 
> Again, can you summarize why this is necessary, rather than using 
> (say) 
> a pointer-to-member? It looks like you're using it to recover the 
> containing class from the memberspaces, is that right?
> 

Yes, that's it. I don't really know how to use a
pointer-to-member here. Suggestions are most welcome. The problem
reduces to, given the following structure:

struct A{
  struct B{
    A& owner();
  } b;
};

implementing A::B::owner() assuming that objects of type A::B
always are born as member b of class A.

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