Boost logo

Boost :

From: David B. Held (dheld_at_[hidden])
Date: 2002-10-22 17:47:07

joaquin_at_[hidden] wrote:

> [...]
> In boost-sandbox/boost-sandbox/libs/map/doc

Heh. I wish I could call that file "documentation", but I'm glad you
got something out of 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).

First of all, let me say that bimap is not a std-conforming map, even
though you have striven greatly to make it so. Neither is my map,
except in the std-compatibility configuration. To be honest, that
doesn't really bother me. I think the concepts defining std::map are
fine for std::map, but I think more importantly, we need to define new
concepts that allow us to work naturally in a new framework. If that
means that some map configurations are not Pair Associative Containers,
I say: So be it.

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

Yes, I noticed your bit about inv_pairs. I think the appropriate thing
to do is to define a new Key Tuple concept appropriate for Generalized
Associative Containers. This could eliminate the inv_pair gymnastics
altogether, and simply let us implement whatever is most natural. We
can always provide Pair Associative semantics for the compatibility case
(which I already provide for). I find them much too limiting for other

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

Yeah, that was a pretty off-the-cuff suggestion. What do you think of
my slightly less elegant suggestion to Dirk? It doesn't scale as
nicely, but if we use the Preprocessor lib, we can make the limit

template <typename K1, typename K2, ...>
class map
     template <typename T>
     class key
         // ...
         int operator[](T) { return 5; }
     key<K1> key0;
     key<K2> key1;

> [...]
> It is available right where the docs is, at

Apparently, "Download source files" at the top of the page was too
obvious for my limited comprehension. ;)

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

Great. Now that I can look at your code, I'll be thinking hard too.


P.S. My first reaction to memberspaces was: "Oh, he's using public data
members. Hmm...there goes data-hiding." However, I believe that proper
manipulation of the types (making them non-copyable, limiting
construction, etc.) allows it to be a suitable technique for introducing
new lexical scope. I'm a bit uncomfortable with the reinterpret_cast<>,
and would prefer it if there were a way to make the "parent access" more
portable. In fact, I see that there are probably problems with my
template suggestion and your memberspace implementation. In particular,
this is going to be a trick:

     prebimap& owner()
       return *reinterpret_cast<prebimap*>(

First, getting the right params to pass to offsetof from within template
code might simply be impossible. Second, I would feel a lot more
comfortable if this could be accomplished in a portable way with
static_cast<>ing to/from void*. However, I'm not sure that this is even
necessary. If you simply stored an "owner pointer" in each memberspace,
you could eliminate the casts altogether. Since a map is typically a
large object anyway, a few extra pointers should not be a prohibitive cost.

Second, the code duplication of the from and to memberspaces is just the
kind of thing we'd like to eliminate with a proper generalization. ;)

Third, an integration of your bimap into my map framework will make it
even more efficient. I thought you had a custom tree type that you
stored your nodes in. I see that you are simply using two std::set<>s,
which, while effective and straightforward, is not as efficient as
creating custom tree nodes and implementing the interleaved sets
directly. Designing an appropriate node type is going to be an
interesting, non-trivial challenge. ;) There is some minor potential
for costs savings by packing the node color for multiple keys, but the
simple fact of the matter is that multi-key maps have fat nodes. ;)
There is also space savings because instead of storing from_type* and
to_type* in each node, as well as having from_type & to_type on the
heap, you can store them both directly in the tree nodes, which saves
two pointers and three heap allocations. For a data structure that's
already criticized for being big and slow, that's a significant savings.
;) Well, those are a few things to think about...

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