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