Re: [boost] Class views on an associative container

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-04-28 09:37:49

Seska Peel ha escrito:

> > What this approach can't do is to produce subviews
> > of intermediate types as you also request, since typeid(x)
> > returns a type_info object referring to the final class
> > of x.
> >
> > Does this help?
>
> Well, it's better than my current version. Still it lacks the
> intermediate type views, and that's a must.

Yesterday night I was playing a little more with this, and come up
with a way to have intermediate types too: the problem with sorting
elements by type_info::before() is that the resulting order has nothing
to do with the base-derived relations among the types involved.
What we need to query intermediate types is a type ordering
which packs a given type and its descendants together, in formal
terms, if T<Q where Q is not derived from T and T' is derived from T
then T'<Q. This is impossible to achieve unless the user explicitly
marks the base-derivation relations in the hierarchy (the essential
reason being that type_info does not provide an API to query for
derivation.)

So, the attached code (compiled with GCC 3.2) exercises the idea.
Instead of the simple type_info_extractor, we use now a more elaborate
extractor named  hierarchical_type_order_extractor  whose associated
ordering respects hierarchy as described above. Base-derivation info
must be provided by the user at run-time, like the following:

  // inform that B is derived from A
  // invoke before first use of hierarchical_type_order
  hierarchical_type_order::declare_base_and_derived<A,B>();

Using this new ordering, we can query for final types as before:

  // list all elements of type B
  dump(m.equal_range(typeid(B)));

and *also* for intermediate types:

  // list all elements of type B or derived from B
  dump(m.equal_range(is_a(typeid(B))));

Note the is_a(...) construct. This kind of magic relies in B.MI
support for so-called *compatible sorting criteria*:

http://boost.org/libs/multi_index/doc/tutorial.html#special_lookup

Two caveats:

1. This only works with single-inheritance hierarchies. I don't
know if it can be extended to multiple inheritance, probably not.

2. Note that in the example the index uses a composite key
on (type order, id). When you query for a final type, the
resulting elements are thus sorted by id:

  equal_range(typeid(B)) --> 3 4
  equal_range(typeid(C)) --> 5 6
  equal_range(typeid(C1)) --> 10
  equal_range(typeid(D)) --> 7
  equal_range(typeid(E)) --> 8 9

But when you use intermediate types, the id order is not
necessarily preserved:

  // B and derived types are: B, C, C1, D, E
  // note the "misplaced" 10!
  equal_range(is_a(typeid(B))) -->  3 4 5 6 10 7 8 9

If you think about it, there is no way to have one single index correctly
id-sorted for every final type and also for every intermediate type. This
unfortunately means that, although you can do this:

  // list all B's with id==5
  equal_range(make_tuple(typeid(B),5));

you *cannot* do this:

  // wrong: try to list all B-or-derived elements with id==5
  equal_range(make_tuple(is_a(typeid(B)),5));

Other than these two caveats, I think this approach could serve
your purposes.

> After thinking a bit more on the "scope" improvement I was explaining
> in my last post, it turns out this is something I'll need to implement
> right now. So I'll add an even more complex feature to this container,
> that would be to add some kind of path (say
> GamesIDo/MyFirstGame/Level1) so that resources could be shared among
> several levels (as instance a character reaching the end of a level
> ... the entire level would have to be unloaded, whereas the character
> would need to be kept, so the character resource would be in
> GamesIDo/MyFirstGame/). Queries on this container could take an
> additional input path to speed things up.

The path thing can be plugged into B.MI by designing an appropriate
extractor and taking advantage of the compatible sorting criteria stuff
referred to above. Then, you can use it on its own index or combined
with other extractors via composite_key. If you decide to go this way
and implement such a path-based key extraction code, don't hesitate
to contact me, privately or thru the list, for further assistance.

Best,

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