[boost] Bidirectional map preliminary submission

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-03-21 10:16:58

First of all, congratulations to all for the new 1.30.0 baby.

I've boostified my bimap library so that it can be more easily
reviewed. Now bimap lives into namespace boost and some
metastuff have been removed in favor of utilities already
provided by Boost itself.
The bimap.hpp header has been uploaded to the Files Section,
under the folder bimap. A sample test is provided as well as
a draft of the documentation, coming from the one I wrote for
CodeProject.

All suggestions and comments are most welcome. I feel that
in its present form boost has no severe barriers to be accepted,
but I'm sure there's lots of room for improvement. In preparation
for critiques, I've compiled a list of several hot topics that may arise

during the prelminary review:

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

2. Pollution of namespace boost.
Apart from bimap, the following types and functions are already defined
inside boost namespace:
* direct_pair
* inv_pair
* make_inv_pair
* bimap_base
* prebimap
* bimap_equal_types
* bimap_different_types
* prebimap_identity
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.

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. I cannot
imagine
how on earth this couldn't be so for any conceivable compiler, but I'm
afraid a
strict interpretation of the standard does not guarantee this.
* 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. G++ complains at this, an ugly
workaround has
been applied for this case.
I'd like to know whether these two points could prevent bimap from
entering
Boost, or, in the contrary, they can be tolerated. Standard workarounds
are most
welcome, of course.

3. Compiler support
The version submitted works for MSVC++6.0sp5 and GNU CC 3.2 (cygwin).
Non-boost bimap also worked for the follwing:
* VC++ 7.0 (aka .NET)
* GNU GCC 3.0, 3.0.2, 3.0.4 (Linux 2.4.18, SunOS 5.8)
* GNU GCC 3.1 (Linux 2.4.18, SunOS 5.8)
* GNU GCC 3.2 (Cygwin 1.3.18-1, Linux 2.4.18, SunOS 5.8), 3.2.1 (Linux
2.4.18,
SunOS 5.8)
* Metrowerks CodeWarrior 8.3 (Mac OS 9.2.2, Mac OS X 10.2.3)
As only minor changes have been made, I guess all of these will still
merrily
compile the thing. Strictly speaking, though, I haven't tested it.

4. Compiler workarounds
There's non-surprising worarounds to cope with several well known
defficiencies
of MSVC++. For GNU CC, the illegal use of offsetof has been masked with
a dubious workaround; more interestingly, there's a compiler bug with
respect
to a constructs I call memberspaces (see
http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=9159

for details). This has been fixed in a satisfactory manner (IMHO).
Finally,
CodeWarrior seems to have a hard time with some dependent typenames, the

patches applied might deserve some thinking over.

Regards,

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