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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk