Re: [boost] Bidirectional map

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-27 21:47:10

On Sat, 27 Jan 2001, Gregory Seidman wrote:

> John E. Potter sez:
> } On Wed, 24 Jan 2001, George A. Heintzelman wrote:
> I mostly agree with you, but not quite. I have often wished that map's
> op[] did not insert but, instead, threw an exception if the key was not
> found (especially if there were a const version that did). This
> bidirectional map could take that approach.

Operator[] does not throw.  The member at() throws.  See vector and
deque.  Wishes aside, that is the standard protocol.

> Also, while I agree that many times a bimap would have Key1 == Key2, this
> is an opportunity for partial specialization; op[] is defined for neither
> if Key1 == Key2, and both if Key1 != Key2.

Not needed.  It is defined for both.  If you use it with Key1 == Key2,
it will not compile.  Since we are talking about a template, when it
is not used, it will compile.  Because of this nonsense, a well known
member at() is better.

> } I see it as a set<Pair<Key1, Key2> >.  This leaves four possibilities
> } when we project the two keys.  Map1to1 is a set<Key1> and a set<Key2>.
> } Map1toN is a multiset<Key1> and a set<Key2>.  MapMto1 is a set<Key1>
> } and a multiset<Key2>.  MapMtoN is a multiset<Key1> and a multiset<Key2>.
> } We could also allow associated non-key values which would then lead to
> } MultimapXtoY also.  What are the use cases and demands for other than
> } the map1to1?
> 
> I do not think it is especially useful to keep the pairs as a set.

That's an implementatiuon detail that I did not intend here.  Please
read the above set<> as a concept.  This map may not have a tuple
(k1, k2) more than once for any of the possibilities.  In a map1toN,
k1 may appear more than once, but k2 may not.

> If we
> one map<Key1, Key2> and one map<Key2, map<Key1, Key2>::const_iterator> then
> we have the functionality we need with a minimum of overhead. A map is,
> effectively, a set of pairs with a more convenient interface and a
> specialized comparator. Of course, for Mto1, 1toN, and MtoN we simply
> replace one or both of the maps with multimaps.

NO!  Multimaps allow unlimited duplication.  This is a map which might
look like a relation which is a set.  Note that the only difference
between map and set is operator[] which does not fit this and the type
of the parameter to the search members.

> Since I do database research, relations and indices rather appeal to me.
> In fact, the primary use I have for such a structure is to cache a table in
> memory rather than doing lots of ODBC calls. Nonetheless, generalizing to
> more columns is a task for another day.

Agreed.  Think about it. :)

> } > However you do the 
> } > underlying implementation, I think that specifying an interface to such 
> } > a container would be useful.
> } 
> } Yes.  Let me take a shot at it with everything required by the standard
> } and variations that might be useful.  Did I miss anything?  Would usage
> } allow cutting everything related to iteration over the second key?  That
> } would give a single iterator and come close to a standard associative.
> } The iterators are constant iterators which return a const& from operator*
> } and a const* from operator->.
> 
> There is no reason to talk of "iteration over the second key" since there
> is no good reason to guarantee an ordering.

But, this is a map not a hash_map.  It is an ordered collection on both
data members.  Two iterators is as reasonable as none.  I think that
none may be what is actually needed.

Are bidirectional maps really dynamic?

I leave the rest for consideration of the above.  It may be the case
that bidirectional maps are only constructed and used.

John