On Mon, Jun 29, 2009 at 11:36 AM, Ross Levine <ross.levine@uky.edu> wrote:

On Sun, Jun 28, 2009 at 5:10 PM, Christian Schladetsch < christian.schladetsch@gmail.com> wrote:

...

One initial issue that may break any interest is that instances put into the container must be of a type T that derives from heterogenous::base<T>.

So, how is this different from using a ptr_container and dynamic_cast?

The instances in a heterogenous::container are added to the container using the correct allocator, and are duplicated using the correct (and same) allocator. struct base {}; struct derived : base {}; typedef ptr_vector<base, heap_clone_alocator, custom_allocator<base> > vec; vec v0; v0.push_back(new T(args)); // doesnt use the correct allocator vec v1 = v0; // clones are not created using the containers allocator as opposed to: typedef heterogenous::vector<custom_allocator> vec; vec v0; v0.push_back<T>(args); // uses correct allocator vec v1 = v0; // clones created using correct allocator, no custom clone_allocator required Of course, I have missed here that for this to work, T must derive from base<T>. There is a good case to be made for using std::vector<any> to do a similar thing. It's much simpler for a start. However, boost::any uses the heap and doesn't know about or use allocators. I've made modifications to boost::any, giving it an allocator type. See http://tinyurl.com/mxh9gm. This allows, for instance: typedef any<custom_allocator<char> > any_type; typedef std::vector<any_type, custom_allocator<any_type> > vec; vec v; v.push_back(T0(42)); v.push_back(T1("foo")); vec v2 = v; And this works - and T0 and T1 don't have to derive from anything. However, it creates the instances to add on the stack, then copies them into the container. v.push_back<type>(..args..) doesn't make a copy - it is constructed in-place using the correct storage provided by the allocator. This may be a pretty weak argument against a 'heterogenous container' based on any rather than ptr_container. Perhaps just making any<> take an allocator type argument would suffice for this? Regards, Christian.

How is this different from a container of <boost/variant.hpp> Robert Ramey Ross Levine wrote:

On Sun, Jun 28, 2009 at 5:10 PM, Christian Schladetsch < christian.schladetsch@gmail.com> wrote:

...

One initial issue that may break any interest is that instances put into the container must be of a type T that derives from heterogenous::base<T>.

So, how is this different from using a ptr_container and dynamic_cast? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

2009/6/28 Christian Schladetsch <christian.schladetsch@gmail.com>:

On Mon, Jun 29, 2009 at 12:58 PM, Robert Ramey <ramey@rrsd.com> wrote:

...

How is this different from a container of <boost/variant.hpp>

boost::variant doesnt support custom allocators. it uses naked new and delete.

A quick test with geordi suggests that it uses placement new, not naked new: <> geordi, { unique_ptr<tracked::B> p(new tracked::B); } <geordi> new(B) B0* B0~ delete(B0) <> geordi, { boost::variant<tracked::B> v; v = tracked::B(); } <geordi> B0* B1* B0=B1 B1~ B0~

Christian Schladetsch wrote:

boost::variant doesnt support custom allocators. it uses naked new and delete.

variant stores objects within itself. If you declare a variant on the stack, your object lies on the stack. The temporary heap backup is only there in operator= and only when you don't have a nothrow move or nothrow default constructor on one of your types. And it's only used for a few instructions unless you throw anyway, so who cares about what allocator it uses. Alternatively, it could also store the backup in the object itself to avoid heap allocations, but that would double its size.

On Mon, Jun 29, 2009 at 6:12 PM, Christian Schladetsch < christian.schladetsch@gmail.com> wrote:

The issue of which allocator to use is quite important to some people, especially in embedded and/or high-performance situations. Sliding in a heap allocation somewhere in a container which has an allocator is a big no-no. ptr_container does it as well when making temporary arrays and for clones.

High-performance/embedded situations are probably not going to need heterogeneous storage. Moreover, not only does deriving from common_base suddenly make a class polymorphic, which adds a vptr, and thus extra size, to every class instance, but your code uses dynamic_cast which requires RTTI, which is typically disabled in these environments to reduce overhead.

Christian Schladetsch wrote:

* vector<variant<T0, .. Tn>, alloc<variant<T0,...Tn> > requires all types that could go into the container to be known at the point of declaration, which is contrary to the idea of having a generic heterogenous container. Adding an object to a vector<variant> also makes a copy and possibly an allocation that does not use the containers allocator [1]. map<variant<..>, variant<...> > could make sense but it would be a lot of work and difficult to maintain, as a variant<> with N types needs N*N comparison functions.

* heterogenous::vector<> requires that a type T added to the container must derive at some point from heterogenous::common_base. This excludes adding builtin types, and means that you either have to change your existing class definitions to put them into such a container, or use a supplied heterogenous::adaptor<T> system. Allowing the addition of builtin types, and types not derived from common_base is certainly possible. However, I don't think that would be a benefit. In that case, you may's well use vector<any<>

Deriving from a common ancestor base class is contrary to generic programming. Knowing all your types ahead of time (at compile time) is not unreasonable, it is the common case for generic programming. Saying it is contrary to your idea is like saying it is different from what you implemented. That isn't exactly a strong argument for why people should use heterogenous::vector instead of vector<variant<> >. I can tell you people will not be happy to derive from your common base class. This kind of design relegates it to being useful only to new classes that people write, and not to legacy classes that people use. That hugely narrows the scope of where it can be useful. It may be pretty particular to what you want to do and not generally useful in a context where people aren't so picky about which allocator they use and all types in an application tend to use the same one. Regards, Luke

[It looks like I forgot to send this message.] Christian Schladetsch wrote:

On Tue, Jun 30, 2009 at 11:14 AM, Simonson, Lucanus J < lucanus.j.simonson@intel.com> wrote:

...

[snip] Deriving from a common ancestor base class is contrary to generic programming. Knowing all your types ahead of time (at compile time) is not unreasonable, it is the common case for generic programming.

Sure, but as much as we'd perhaps like to forget about it, it is true that C++ supports OO style as well as generic programming, especially in GUIs and other object hierarchies. In these cases, you either cannot know or don't want to know all the types that may be used ahead of time. This is the basic premise of loose coupling.

ptr_containers and the heterogeneous containers should account for polymorphic type use cases. Somewhere in that space, however, should be support for cases of homogenous containers of pointers to a single type such that the purpose of the container, aside from holding the pointers, is to assume ownership of them and delete them when the container goes out of scope (unless told to avoid taking ownership). The latter use case makes tracking the lifetime of allocated memory easier. Yes, containers of shared_ptrs would work, but they add overhead that isn't always wanted. Yes, it is possible to leave pointers to former elements dangling when the container is destroyed, but C++ is replete with such opportunities to cause problems. Sometimes, performance wins. The heterogeneous containers, being implemented as class templates, need only be defined in terms of operations supported by its parameterizing types. Require that the type T be a common base of all objects in the container and that it provide specific polymorphic operations and you have all that's needed. There's no need to impose that by requiring derivation from any particular base class, just whatever is sensible to the user. If that can be captured via TMP to support types that aren't related with a default that assumes types that are, all the better. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Mathias Gaunard wrote:

Stewart, Robert wrote:

...

Yes, containers of shared_ptrs would work, but they add overhead that isn't always wanted.

Then use containers of unique_ptr, like you should (shared_ptr

"like you should" is a rather strong statement.

is meant for shared ownership or making it easy to fix broken code), or use the boost pointer containers if you can't (which move semantics mostly render obsolete). You could alternatively use boost.any, adobe.poly, clone_ptr, or whatever is relevant.

All of those schemes mean that the container interface is in terms of those wrapper types rather than raw pointers. They will work, but they complicate the code using the elements. I'm not suggesting that is onerous, but the interface isn't as simple.

...

The heterogeneous containers, being implemented as class templates, need only be defined in terms of operations supported by its parameterizing types.

This merely looks like a container of Adobe.Poly.

I've never used anything from the Adobe library. You may be right, but why shouldn't Boost provide a clean solution for itself? _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Mathias Gaunard wrote:

Stewart, Robert wrote

...

...

...

Yes, containers of shared_ptrs would work, but they add overhead that isn't always wanted. Then use containers of unique_ptr, like you should (shared_ptr

"like you should" is a rather strong statement.

If you want a container of pointers with the container owning the pointees, in order to use inclusion polymorphism for example, then a container of unique_ptr is the standard solution, while a container of shared_ptr is not only overkill since it adds a lot of useless overhead, it also gives the wrong semantics.

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.

It seems you just made my point for me. There are numerous approaches to take, each with tradeoffs.

...

All of those schemes mean that the container interface is in terms of those wrapper types rather than raw pointers. They will work, but they complicate the code using the elements. I'm not suggesting that is onerous, but the interface isn't as simple.

How are smart pointers, smart references or smart objects (whatever you want to call them) any more difficult to use than pointers or objects?

The client code must be written in terms of wrapper_type<T> or container::value_type rather than T * or it must ask the wrapper for its raw pointer, an extra step. The point I'm making is that there are times when a container that does nothing more than own pointers is useful. Other code can use the pointers at will until the container goes out of scope. There's no need to wrap the pointers in anything in that case. Maybe that's too uncommon to warrant support in this context, but that's the use case I was proposing. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

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@nist.gov> 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

On Saturday 01 August 2009, Mathias Gaunard wrote:

I personally never understood why they tied the type into the allocator. Having just the size and alignment would be so much better.

It seems to me any benefits of such a scheme would be non-portable, since the sizes and alignments of two types may be the same with one compiler (setting) and different with others.

AMDG Christian Schladetsch wrote:

On Mon, Aug 3, 2009 at 5:44 AM, Frank Mori Hess <fmhess@speakeasy.net>wrote:

...

On Saturday 01 August 2009, Mathias Gaunard wrote:

...

I personally never understood why they tied the type into the allocator. Having just the size and alignment would be so much better.

It seems to me any benefits of such a scheme would be non-portable, since the sizes and alignments of two types may be the same with one compiler (setting) and different with others.

I don't see a problem. As long as the objects are created with correct alignment for a given compiler (setting), what that alignment is, is not important.

Unfortunately, this requires the ability to find the alignment of an arbitrary type. boost::alignment_of only guarantees that it will return a positive multiple of the type's alignment. In Christ, Steven Watanabe

Frank Mori Hess wrote:

I wasn't following the thread too closely, but I assumed the benefit of using size+alignment instead of type would be that you could reuse the same allocator with different types (as long as they had the same size and alignment). But since a type's size+alignment varies across platforms, you wouldn't be able to portably reuse such an allocator with different types (hence no portable benefit).

The size + alignment wouldn't be part of the type of the allocator, it would be part of the arguments it receives to perform a given allocation. (i.e., like posix_memalign). But strictly speaking, the language doesn't even require to take into account arbitrary alignments, you can just align to anything big enough, like malloc and operator new do.

On Sun, Aug 2, 2009 at 1:31 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:

Christian Schladetsch wrote:

...

[snip] 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!).

Standard allocators are inherently incompatible with the very idea of cloneable objects, since the type information is supposed to be lost.

The only sensible thing you can do (IMHO) is use a standard allocator of char or use an allocator interface similar to that of malloc or operator new.

I personally never understood why they tied the type into the allocator. Having just the size and alignment would be so much better.

This is largely what I did. The allocation model used by Cloneable is based on covariant virtual methods that are passed an 'abstract allocator' which takes the alignment as an argument. struct abstract_allocator { typedef char *pointer; virtual pointer allocate_bytes(size_t num_bytes, size_t alignment) = 0; virtual void deallocate_bytes(pointer, size_t alignment) = 0; static size_t calc_padding(pointer ptr, size_t alignment); }; An abstract allocator is then adapted from a type that models std::allocator and is passed to methods used to create objects used by the system. Yes, it means that 'type info' is lost, as the allocations are really just sequences of correctly-aligned bytes - but I can't see this as a problem (and anyway, it is exactly what is happening). As you say, there doesn't seem to be anything to gain from having the type information in the signature of an allocator type - and much to lose. So I just inverted it, removed the type from the allocator signature, and now pass the alignment down as needed from where the type information is.

You simply have to use emplace semantics for these containers;

...

otherwise you aren't respecting the allocator

For when you copy the container later, do you maybe add a pointer overhead per object on your heterogeneous list to reference a rightly rebound function for cloning with the given container allocator? Not something very nice, since it could be avoided.

No, there is no per-object overhead. Each object in the container is `cloneable`, via the mixin that is added in the declaration: struct MyDerived : cloneable::base<MyDerived, SomeBase> { ... }; This of couse adds a vtbl to all your types used by the library, but that is unavoidable. The main costs are the dynamic_cast's used by the system, both internally and to answer queries for the associative containers (which answer based on type and value). Dynamic_cast<> can be very slow, but the effect is mitigated because in general the casts succeed (dynamic_cast is slowest for classes with many derived types when the cast eventually fails). The need for dynamic_cast<> over static_cast<> was introduced when I had to make the base virtual to allow rudimentary multiple inheritance support. That said, there is a structure in the libary called 'cloneable::instance<>' which stores an object pointer and a reference to the allocator that made it. This is used by the system when adding new objects to containers but is not stored anywhere. However, I found the idea of pairing objects with their allocators so appealing that I exposed it in the public interface for the library. It is one thing to be able to clone an object using clone(Q) or Q.clone(); but that is only half the story. To be complete, IMO, these methods should also be able to make a clone using the same allocator as the original. Hence the idea of a 'cloneable::instance<>'. How important this is in general may be questionable. But for high-performance system software, where lifetime management is often optimised for different timeframes (scope-local, per-frame, across milliseconds, across seconds, across hours etc), then knowledge about an instance including its allocator can be very handy. It is a way of adding semantics to an instance, not all of which are created equally. Anyway, I'm currently blocked on how to deal with multiple inheritance and will have to make the call soon about whether to drop explicit support for it, or to basically re-write it to pass the derived types to the cloneable system and have it synthesise everything itself. That approach may or may not even work. Regards, Christian.