Boost logo

Boost :

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]


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk