Boost logo

Boost :

From: David B. Held (dheld_at_[hidden])
Date: 2002-10-22 14:00:28

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.

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

> * 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;
> 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>

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


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