Boost logo

Boost :

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

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at