Boost logo

Boost :

From: joaquin_at_[hidden]
Date: 2002-10-22 16:15:31

----- Original Message -----
From: "David B. Held" <dheld_at_[hidden]>
Date: Tuesday, October 22, 2002 9:00 pm
Subject: [boost] Re: Interest in bidirectional map?

> Joaquín Mª López Muñoz wrote:
> > I've had a look at the docs of your map,
> Really? Where did you find those? I don't believe I've written
> any
> documentation for it. ;) If I did, and don't know about it, I'd
> like to
> see what I forgot I wrote! ;) In fact, I didn't even say where
> one
> could look at it.

In boost-sandbox/boost-sandbox/libs/map/doc

> > and seems to me a fair amount of work has to be done in order to
> > integrate the features of bimap into boost::map.
> Yes. Very true. But the idea is to put that hard work to good
> use by
> generalizing the concept of a map even further than I have, so
> that all
> of the maps in question (std::set, map, and bimap) become special
> cases.As an analogy, consider the progression from std::pair<> ->
> boost::tuple<>. It may involve a complete redesign of both maps,
> but
> then it could result in something much more useful and powerful,
> as well.
> > * bimap uses two sets of pointers to the elements (one for the
> > from part, other for the to part). I don't see how this
> > can be implemented using your rb_tree's, I guess two of them
> > would be needed.
> Ok, then you did it the way I assumed. You essentially
> interleaved two
> trees over one set of nodes. This can be accomodated somewhat
> already
> in my map design, since the node type is a policy. For a single-
> key
> map, you simply provide single-threaded nodes. For a multi-key
> map, you
> provide nodes that have as many tree pointers as necessary. I had
> to
> make the node type a policy to support efficient indexing (you
> don't pay
> for indexing if you don't use it).

Yes, I think this can be approached the way you suggest. There's
another trick coming into play here (I'll sitck to bimap for
simplicity, but the problem remains even more challenging
for n-maps): if the nodes are pairs of (key1,key2) values, then
there's no problem with accessing them from key1-iterators:
the first member of the element pointed to is the key, the second
the value. On the contrary, the situation is reversed for
key2-iterator, and this is not what one expects from a regular map
(since both iterators behave as much as possible as regular
map iterators). To acommodate this, key2::values are not std::pairs,
but rather inv_pairs (more info on my docs), and generic code
won't notice the trick, accessing in both cases to elements whose
first element is the key. How to generalize this to n keys
is a non-trivial task.

> > * bimap uses an artifact I call memberspaces in order to allow
> for
> > duplicate operator[]s for the from and to part. To the best of
> my
> > knowledge, this trick hasn't used before, but it is not
> fundamentally
> > complex. With memberspaces, one can write things like:
> >
> > bimap bm;
> > bm.from[1]=2;
> >[10]=8;
> > bm[7]=6; //no memberspace specified, from assumed.
> Yes, I saw this discussion in your Annex. However, I obviously
> didn't
> study it closely enough to notice that this is how you support the
> subscripting operator over both keys. I like it. Clearly, it can
> be
> generalized to more than 2 keys, as well. Possibly a syntax like
> this
> could be possible:
> nmap map;
> map.key<1>["joe"] = employee_record;
> map.key<2>["123-45-6789"] = employee2;
> employee_id = map[35]; // defaults to .key<0>

This cannot be generalized so neatly. Memberspaces rely
on member objects whose name matches that of their type. This cannot
be extended to things like key<1>, which obviously doesn't
qualify as a name for an object.

> > With a little bit of PTS, memberspaces member functions can be
> > exported to the "global" memberspace when no ambiguity exists.
> > This techniques should have to be included in your boost::map.
> That doesn't concern me. I have no problem hacking the interface
> of my
> map, since I'm the only one who uses it right now (that I know
> of). And
> even though I put it in the boost namespace, beware that it's not
> a
> Boost library.
> > One concern about inclusion of bimap into boost::map is the possible
> > overhead incurred even when no bidirectionality is need. I guess
> > policy classes can be used to approach this problem.
> Yes, indeed. Like I said, the bidirectionality cost comes
> primarily in
> the form of extra memory usage. However, the bulk of this memory
> overhead is due to the node type, and not the actual tree type(s)
> used.
> By making the node type a policy, it should be possible to swap
> in any
> interface-compatible node type, supporting one, two, or n-key maps
> and
> sets. Now, the actual map interface would have to be modified to
> support the multiple keys, but that incurs no overhead. Functions
> that
> don't get called don't get generated. Types that don't get used
> don't
> get instantiated. This is, of course, the philosophy of
> Loki::SmartPtr.
> > If you're interested in evaluating the suitability of including
> > bimap-capabilities in your boost::map, I'm open to your
> questions. The
> > docs are complete enough, and I can assist you with the more
> technical
> > questions.
> Actually, I'd like to see the implementation, if you don't mind.
> If you
> could upload it to the files area or the sandbox, I would
> appreciate it.

It is available right where the docs is, at

> Also, since you have experience working with bimap, I was hoping
> you
> could help design a generalized node interface suitable for
> multiple-key
> trees. Ideally, the map would be able to select the actual tree
> representation from the trees library being discussed, but that
> sounds
> like a lot of work that I don't want to mess with right now.
> Part of the reason I haven't pushed for a review of my map is
> because I
> haven't had much time to work on it, and partly because I was
> afraid it
> was not sufficiently general to have a wide audience (though I
> personally feel it is an improvement over std::map, and can be a
> drop-in
> replacement, making that a compelling reason alone). Yet another
> reason
> is that the policies were intimidating. The map has seven
> template
> parameters, which is enough to make some programmers cringe in
> horror.
> However, progress in building an integrated policy adaptor for
> Loki::SmartPtr gives me hope that the large number of policies is
> no
> longer a problem. Of course, this is possible because of the
> incredibly
> powerful facilities provided by MPL.
> But seeing someone else using a funky map convinces me that a more
> generalized map is indeed useful, and that a policy-based design
> is the
> right way to go (I personally find the four std set/map types an
> abomination of duplication). If you have more time than I, I hope
> you
> will take a close look at the node policies, and see if there is
> an
> obvious way to generalize them in support of multiple keys. I
> know they
> are not very orthogonal right now, but that is primarily because I
> couldn't imagine other kinds of nodes that would be useful to use
> with
> the map. If you haven't figured it out already, the map is in the
> boost
> sandbox (I imagine that's where you found the "docs").

Time is scarce (I guess the same happens to you), but I'll
definitely have a look at your code and think about it.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

> Dave
> _______________________________________________
> Unsubscribe & other changes:

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