Re: Bidirectional map

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-02-07 17:43:28

Hello again Boosters. Apologies my response on this has taken so long 
(long story why).

In any case, I read through the responses to my original posting about 
the bidirectional map, and since at least one of them had a very 
detailed interface, I'd like to comment on it.

From: "John E. Potter" <jpotter_at_[hidden]>
> On Wed, 24 Jan 2001, George A. Heintzelman wrote:
> This has been mentioned several times on the news groups.  There does
> seem to be a demand.  Let me take a shot at what it isn't first.
> 
>    Key2 const& operator[] (Key1 const&) const;
>    Key1 const& operator[] (Key2 const&) const;
> 
> 1.  The only associative container which has operator[] is map and
>     there is only a non-const version because it inserts.
> 2.  Operator[] does not throw.
> 3.  Operator[] can not do an insert here.
> 4.  Many (most?) useful bidirectional maps have Key1 == Key2.
> 
> This thing does not have an operator[].

I think you are right, but not because of (4) -- in that case you 
simply cannot use operator[] without triggering an ambiguity error. And 
1 and 2 are not problems, as far as I'm concerned; this is a lot like a 
map. Item 3 is an issue. It *could* do an insert as with map, but then 
it would have to set the other key to the default value, meaning an 
expensive insert into the other map; and then when the value is changed 
you have to do another expensive insert. Also, it would *have* to throw 
if more than one copy of the default item was inserted, to preserve 
bidirectionality. This kind of inefficiency/surprise would be easily 
hidden from the users, so I think we ought to avoid it and not supply 
operator[].

> You could save a little space by putting all of the links needed into
> one node and writing all of that code. The number of links will depend
> upon the interface required.  A simple inplementation might be a set of
> pairs and a set of iterators into the first set.  This might generalize
> to many keys, but it is starting to sound like a relation and indicies.
> I think that interface would be different.

Right. I think once you get to ntuples, with indicies on different 
fields (and maybe some binary, maybe some hashed, maybe something else, 
maybe some no index at all), you need a different structure to handle 
the generality.

> 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->.

Hmm. I think you ought to be able to iterate on either key, and I don't 
see the cost in providing the second one. Probably will not be needed 
too often (heck you may not iterate through the first one very often), 
but then you just pay parsing costs on the compile, so there's no 
reason *not* to supply it.

I've snipped the proposed interface for map1to1. It looks pretty good 
to me, and was a thorough version of what I had been thinking about. 
There are a few things I have to think carefully about, especially the 
case where Key1 = Key2, but I think you nailed most of those correctly. 
OTOH, I think in a few cases what you should do is supply an 
un-extended alias for use in cases where Key1 != Key2, simply for 
convenience (and maybe you don't want to know which type is Key1 and 
which Key2). And I do think both values should be const in the 
value_type, because otherwise changing a mapping (requiring an 
expensive re-insert) is too easy.

>     iterator1 begin1 () const;
>     iterator2 begin2 () const;
>     iterator1 end1 () const;
>     iterator2 end2 () const;
>     reverse_iterator1 rbegin1 () const;
>     reverse_iterator2 rbegin2 () const;
>     reverse_iterator1 rend1 () const;
>     reverse_iterator2 rend2 () const;

I think begin() and end() and rbegin() and rend() should be supplied as 
aliases for begin1. Sometimes (often?) you just Don't Care, and this 
makes them fit with standard-looking stuff more easily.

>     Key2 const& at1 (Key1 const&) const;
>     Key1 const& at2 (key2 const&) const;

These throw presumably if they are not found. We should also supply as 
aliases:
      Key2 const & at(Key1 const &a) const {return at1(a) }
      Key1 const & at(Key2 const &a) const {return at2(a) }
which will die with ambiguity if used when Key1 == Key2. That's the way 
we want it.

Likewise for erase1 and erase2, find1 and find2.

> > } 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.

Right. These alternate possibilities may also be worth implementing, 
and probably not a great deal harder. But that'll come later.

> 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.

Often, I think you are right, but there is no cost in supplying them 
and someone may find a use. Often failure to see why something is 
needed is just a lack of imagination, and I suspect that is the case 
here.

> Are bidirectional maps really dynamic?

The ones that I am thinking about generally, at most grow only. This is 
what you get, for example, if you are building a dictionary. (Okay, a 
mindless dictionary with 1-to-1 translation, but you get my point).

OTOH, I suspect again that his is a failure of imagination on my part. 
It will naturally be more expensive to insert into a map1to1 than into 
a map, but probably less expensive than inserting into 2 maps with 
pointers each way and maintaining the correspondence yourself. But 
that's probably about as good as you get, until you start moving to a 
hash_map. Of course, modifying a map1to1 to use a hash instead is 
rather trivial (just use equality comparators and hashes on each key, 
and you're done).

Someone else wrote:

> In the same way that I believe I've shown we can generalize the binary
> search algorithms to use heterogeneous comparison operators, I believe we
> can generalize searching in the sorted associative containers. I want to see
> a generalization of the sorted associative container which supports
> comparison operator arguments to the searching functions, and an insert
> function where the iterator is more than just a hint.

I can see ways of doing this, but most of them involve building another 
index than the one the map itself uses (eg, a map<Key,map<Key,value>
::iterator>). What I don't see is how supplying this in a standard way 
buys much over rolling your own, unless you wanted to building 
something like a map that maintained indices on a list of comparator 
functions or something. I think that's going to be rather specialized. 
Could you expand on this in more detail?

George Heintzelman
georgeh_at_[hidden]