Re: [boost] Interest in a "Heterogenous Container" system?

Subject: Re: [boost] Interest in a "Heterogenous Container" system?
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-08-01 20:58:28

The motivation for my original proposal was to provide a framework for
heterogenous containers, and came from discussions about how cloning works
in ptr_container.

I wanted a way to make the cloning operation for ptr_container to use the
same allocator that the container uses (and indeed, have the container use
the correct allocator at all!). This ended up being quite a large task, and
spawned a whole separate 'Cloneable' library at http://tinyurl.com/ndy5n8.

A motivational example of Cloneable with Heterogenous containers is
something like:

struct B { int n; B(int x = 0) : n(x) { } bool operator<(B q) { return n <
q.n; } }; // provide a common base
struct A : cloneable::base<A, B> { A(int n = 1) : B(n) { } }; // derived1
struct C : cloneable::base<C, B> { C(int n = 2) : B(n) { } }; // derived2

void test()
{
    heterogenous::list<B, my_allocator<B> > list; // parameterised over the
base, give an allocator
    list.push_back<A>(12); // emplace
    list.push_back<C>(-4); // emplace
    heterogenous::list<B> list2 = list; // deep-copy, using rebound
my_allocator<T>
}

You simply have to use emplace semantics for these containers; otherwise you
aren't respecting the allocator. Similarly for the clone operation: it must
use the same allocator as the original container to make the clones,
otherwise there is no point in even providing a parameterised allocator
type.

Associative containers get a little more interesting:

void assoc()
{
    typedef heterogenous::set<B> Set;
    Set set;
    set.insert<A>(1);
    set.insert<C>(2);
    Set::iterator iter = set.find<A>(1); // find an instance of type A with
value 1
    iter = set.find<B>(2); // find any type that has a `value` of 2
}

And for maps, my current design is split between a mapping of value-type to
pointer-type, as well as an "isomorphic" mapping of pointer-to-pointer:

void maps()
{
    heterogenous::map<string, B> map; // map of value to pointer
    map.key("foo").value<A>(12);
    map.key("bar").value<C>(6);

    heterogenous:iso_map<B> iso;   // map of pointer to pointer
    iso.key<A>(1).value<C>(2);
    assert(iso.find<B>(1) != iso.end());
}

The key thing is that all such containers provide value semantics for
comparison and copying. Cloning these containers does a deep copy using the
same allocator as the parent container. It also allows for objects that do
not have default constructors, and provides a mechanism to provide custom
overrides of the clone operation.

So that sums up what I was trying to do originally. It currently has
problems with multiple inheritance:

It seems that the only way to write such a system that works with MI is to
give over the type information to Cloneable entirely:

struct Base { };
struct Derived1 : cloneable::base<Derived1, Base> { };
struct Derived2 : cloneable::base<Derived1, Derived2, Base> { }; //
inheritance
struct Derived3 : cloneable::base<Derived1, Derived2, Derived3, Base> { };
// inheritance (?)

To avoid having to derive from Base using virtual inheritance, it seems that
having to provide the base list to the system is unavoidable. Going down
this track is to create a reflected type-system adjacent to the C++ type
system, with all the compexity of casts and so on moved to compile-time. For
example, to deal with Derived3 above you'll need to provide a means to
virtually inherit:

struct Derived2 : clone::base<clone::virtual_derive<Derived1>, Derived2,
Base> { }; // inheritance
struct Derived3 : clone::base<clone::virtual_derive<Derived1>, Derived2,
Derived3, Base> { }; // inheritance (?)

An alternative is to remove cloneable::base<..> entirely, but that means
much more housekeeping on the behalf of the client to the point where the
system is of little practical benefit. Or of course, just don't support
derivation at all and leave it up to the user.

Anyway, all of this is to say that the problem is quite deep and I think
I'll be going back to the drawing board on this. I'll also be looking hard
at the Adobe library for inspiration.

I'd appreciate any comments; at the moment I think the work I've done so far
on this is promising but it may need a complete re-think and perhaps re-work
to support multiple inheritance correctly. Or, I could wrap it all up, strip
out the fledgling support for MI, and run with that? That isn't very
attractive.

It seems that there is some low-hanging fruit here, in terms of good support
for OO-style programming with containers. I am still finding the balance and
the best questions to ask.

Comments very welcome.

Cheers,
Christian.

On Sat, Aug 1, 2009 at 7:43 AM, Frank Mori Hess <frank.hess_at_[hidden]> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Friday 31 July 2009, Mathias Gaunard wrote:
> > A container of clone_ptr is a more elegant solution if you can't use
> > move semantics, since it actually has the right ones. You may want to
> > implement it using COW however since non move-aware containers can do a
> > lot of spurious copies.
>
> By the way, there is a cloning pointer included in the generic_ptr library
> I've been working on recently:
>
> https://svn.boost.org/trac/boost/browser/sandbox/fmhess/boost/generic_ptr
>
> Still no docs, but at least I'm starting to add some tests.  It should also
> be
> possible (haven't actually tried it yet) to combine the cloning pointer it
> with a shared pointer, like
>
> generic_ptr::cloning<generic_ptr::shared<T*> >
>
> to support a combination of deep and shallow copy handles, although you'd
> have
> to pass the cloning a null deleter to prevent it from double-deleting the
> owned object.
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
>
> iEYEARECAAYFAkpzSW0ACgkQ5vihyNWuA4U8rgCdHtMpaV/kEl9Z58iVwrw+c42y
> hwUAoJwb40mJHfAobIUV5MD/nARe8DWA
> =OF/7
> -----END PGP SIGNATURE-----
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>