[Boost-users] Maps: one-to-one one-to-many many-to-many

From: Travis Parks (jehugaleahsa_at_[hidden])
Date: 2007-04-22 00:08:27

Hello:

I am constantly trying to jump into boost. However, I can only read so
many pages of documentation before my brain explodes.

I have always been interested in a data structure for storing pairs of
of keys. In math it is a one-to-one mapping. I find it useful from
time to time to have a container that allows me to treat it like an
enum, but then to do the operation the other way. I usually do it
lazily and just do a map and then do a linear search for the value
when I need to.

However, I have been thinking about it, and why should I have to
suffer linear half the time? So today I wrote a very ugly class that
does it log n both ways for me. I did it in less than 30 minutes so it
has three methods, namely, insert, get_by_first and get_by_second.

It is exceptionally ugly because you have to guaruntee that you will
never change the data structure by returning a reference to one of the
keys. Worse, if you want to save memory and make sure comparisons work
the way you expect them, you have to use two maps of pointers with
custom comparison functions that call the user's comparison function
with the key-pointers dereferenced!

I am wondering if there is something like this already out there
already. Or is there a better way of dealing with my issue? I want
structures that let me go on to things like one-to-many and
many-to-many as well. Of course, what would "many" look like? Would it
be an array of the mapped values? Perhaps I should stick with
one-to-one!

Finally, what would be a good name for this structure? I have been
calling it bi-directional map. But this name doesn't carry well for
one-to-many and many-to-many. And what should the interface look like?
This structure is kind of hard to map to a STL container's interface
due to the two keys (no operator[] for instance and no mapped_type or
key_type).

Thanks for any input! Ask if you want my horrible source code. Ever
see two const_casts in one line? Want to?