Re: [boost] Bidirectional map preliminary submission

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2003-03-21 13:38:17

A bidirectional map is something I've wanted a good implementation of 
for a while. I have one that has some terrible performance in memory 
and speed, but does what I need in its current context. Having a better 
one would be great, so I applaud your submission.

> 1. Syntax and semantics
> Since bimap follows as closely as possible the interface of std::map,
> there's little IMHO to add or remove from here. The added constraint
> of bidirectionality imposes some behavior that diverges from regular
> maps, though. I don't think there's an alternate way to handle the
> following
> issues:
> * operator[], when used for inspection on a non-existent value, throws
> bimap_base::value_not_found. std::maps, on the other hand, automatically
> insert a default value. This I cannot do in bimap, since it would
> violate the bidirectionality.

This is the right choice, I think.

> * bimap_base::duplicate_value is thrown whenever an assignment is
> attempted to a value already present in the bimap: this again stems from
> the preservation of the bidirectionality invariant.

Likewise. No problem here.

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

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

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.

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.

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.

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?

George Heintzelman