Bidirectional map

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-01-24 14:26:36

Hello fellow boosters,

One of the things I find most lacking in the standard containers as 
they stand is a bidirectional map, or in mathematical terms an 
isomorphism, where lookups in both directions are O(log n).

Of course, there are ways to do this. One way is to represent this 
internally is to use two maps, each between a key and a pointer to the 
other type, stored in the other map. But writing the bookkeeping for 
such a container is somewhat annoying and painful, so I would rather do 
it once in template form and then forget about it. Alternatively, you 
might use a more explicitly-written form more purely optimized to 
storing this special situation (say, as linked pairs with a link field 
for each key'd item. You might even be able to generalize this to an 
ntuple'd isomorphism with lookups on each key... ).  However you do the 
underlying implementation, I think that specifying an interface to such 
a container would be useful.

I intend to do this for my own use over the next few weeks. That being 
the case, I thought I would take a quick check over on boost to see if 
there was interest in having this kind of container boostified, and if 
so open discussion on what should be in its interface. Or, if there is 
such a thing out there somewhere already that I'm not aware of, and 
that means I shouldn't bother to do it, pointers and information about 
it would be appreciated. I did look at the VTL and, while that library 
is extremely nice and quite useful, nothing matching what I am thinking 
about is in there (though VTL concepts could be used to help build 
something that looks like what I am thinking of).

Anyway, feedback is welcome.

George Heintzelman
georgeh_at_[hidden]