Re: [boost] Re: Bidirectional map

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-02-10 14:21:29

On Wed, 7 Feb 2001, George A. Heintzelman wrote:

> From: "John E. Potter" <jpotter_at_[hidden]>
> > 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.

My thoughts also.  A bidirectional map should be symmetric in the two
keys.

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

Give up the symmetry?  I don't understand doing something with it
when you don't know what you're doing, don't know which key is which.
Do you have an example?

Agree that if any un-extended aliases are given, they all should be.

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

Nope, it requires a cast.  The value_type for a container is assignable
and some claim that std::map is not a container because of this.  No
reason to open the bidirectional map to the same complaints.  Like
std::set both iterator and const_iterator are constant iterators.  The
only access to an element of the container is through an iterator and
that yields a const& via operator* or a non-modifiable lvalue via
operator->.  map1to1<T, U> value_type e; e = *iter; should be valid.

> >     Key2 const& at1 (Key1 const&) const;
> >     Key1 const& at2 (key2 const&) const;
> 
> These throw presumably if they are not found.

Yes.  At normally throws out_of_range, but domain_error seems more
appropriate here.

> > Are bidirectional maps really dyna
> 
> 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).

Your point is exactly what I was thinking.  A map1to1 which is only
constructed and used would have a different interface and could be
implemented with much less space and slightly better time.

template <class Key1, class Key2, class Compare1 = less<Key1>,
      class Compare2 = less<Key2> >
class map1to1 {
public :
   template <class Fiter>
   map1to1 (Fiter first, Fiter last);
   Key2 const& at1 (Key1 const&) const;
   Key1 const& at2 (Key2 const&) const;
   // maybe find and lower_bound
   };

> OTOH, I suspect again that his is a failure of imagination on my part. 

My imagination has the same problem, and nobody else seems to care.

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

Dave is talking about a data set with the invariant e1.key1 < e2.key1
iff e1.key2 < e2.key2.  This would require no extra space and the
standard containers could be used if a compare object could be
supplied to the search members.  The invariant would be the responsibility
of the user not the class.  A much different animal from your view of
a bidirectional map.

John