Re: [boost] [cpo-proposal] presentation of the idea
Date: Tue, 13 Aug 2013 07:42:03 -0500 From: Larry Evans <cppljevans@suddenlink.net> To: boost@lists.boost.org Subject: Re: [boost] [cpo-proposal] presentation of the idea
What if the class hierarchy is used to model a graph that contains cycles. For example, something like a spirit grammar where a non-terminal on the rhs of a non-terminals definition?
I don't see any problem, as long as they fulfill the requirements of the classifier container, i.e. the objects to be inserted should be copyable and derived from the base class in the template argument of the classifier.
Wouldn't this require some sort of smart pointer or other garbage collection method with the ability to collect cycles?
I don't think so, the classifier container should be able to replace any occurence of something like: vector< shared_ptr <base> > in almost in any circunstance. Beside, you could avoid virtual destructors because the classifier will destroy the object directly not from a base* pointer.
Date: Tue, 13 Aug 2013 18:33:41 +0200 From: Klaim - Jo?l Lamotte <mjklaim@gmail.com>
Maybe a classic implementation example would make a clearer point on which case it solves.
I will try, actually I have to write the full documentation. Anyway, let us suppose you have something as simple as a class hierarchy of shapes. Base class: shape, and derived classes: square and triangle. You might like to store shape objects in one container but you might not want to use: vector <shape*>, nor vector< shared_ptr< shape> >, nor boost pointer container library. Then the classifier could be an alternative.
What if the class hierarchy is used to model a graph that contains cycles. For example, something like a spirit grammar where a non-terminal on the rhs of a non-terminals definition? Wouldn't this require some sort of smart pointer or other garbage collection method with the ability to collect cycles?
My understanding of the proposed container is that it's mostly like having a collection of vectors, one for each final types, but exposing only one base interface in container interface. If I'm correct, I don't see how the problem you describe might be a problem.
Joel.
Yes, that is the idea. Actually, whether the implementation uses a collection of vectors or other mechanism is an implementation detail. I use a map of vectors in the classifier container, but I will try other implementations.
Date: Tue, 13 Aug 2013 13:54:09 -0500 From: Larry Evans <cppljevans@suddenlink.net>
Rereading the OP, I see:
collection.insert( derived_A(21) );
which means a completely new object is created during the insert; hence, no cycles in pointer graph can occur.
Yes, the interface of classifier<base> (for instance: classifier<shape>) should be similar to vector<triangle> but with the ability of inserting any object that derives from shape. Moreover, you can not have a std::vector of a pure abstract class, but you could have a classifier of an abstract class.
Date: Tue, 13 Aug 2013 23:33:25 +0400 From: Andrey Semashev <andrey.semashev@gmail.com>
- The container classifier is _not_ a sequence.
Why? Is this intentional?
Both intentional and accidental, because I want to allocate objects contiguously in memory I have to store them in a collection of vectors, the container is not a sequence but a collection of sequences, one sequence for every class in the classifier. I will implement a sequence, but later.
- The allocator argument in the classifier will be applied to every object added to the classifier. Thus, the allocator is provided without its argument. The std::allocator is the default argument.
It's better not to use template template parameters in the container interface as it limits its usefullness because users won't be able to specify non- template allocators or template allocators with different template arguments. You can use the standard interface for allocator rebinding:
typedef allocator<T> allocator_T; typedef typename allocator_T::template rebind<U>::other allocator_U;
You can use std::allocator<void> by default then.
I am not sure how to do this. I need a allocator with a parameter in order to get: allocator<triangle>, allocator<square>, ... this allocator must be instantiated when an object of a new class is inserted in the classifier.
All in all the basic idea looks interesting, although I'm not sure about the particular classifier container. It looks very specific to me, the same functionality could be achieved with a multimap or unordered_multimap of polymorphic elements.
...or I should have said "multiset or unordered_multiset".
As far as I know it is not possible to get a multimap of a pure abstract class, therefore, for example, you can not use a multimap<string, shape> or multiset<shape> but you can use a classifier<shape> to store triangles, squares, or any derived class. I plan to implement an associate container later, thus you could have classifier<string, shape> and you could look for an object in the classifier using a key. Best regards, Santiago Tapia
On 08/16/13 08:21, Santiago Tapia wrote:
Date: Tue, 13 Aug 2013 18:33:41 +0200 From: Klaim - Jo?l Lamotte <mjklaim@gmail.com>
Maybe a classic implementation example would make a clearer point on which case it solves.
I will try, actually I have to write the full documentation.
Anyway, let us suppose you have something as simple as a class hierarchy of shapes. Base class: shape, and derived classes: square and triangle. You might like to store shape objects in one container but you might not want to use: vector <shape*>, nor vector< shared_ptr< shape> >, nor boost pointer container library.
Then the classifier could be an alternative.
What if the class hierarchy is used to model a graph that contains cycles. For example, something like a spirit grammar where a non-terminal on the rhs of a non-terminals definition? Wouldn't this require some sort of smart pointer or other garbage collection method with the ability to collect cycles?
My understanding of the proposed container is that it's mostly like having a collection of vectors, one for each final types, but exposing only one base interface in container interface. If I'm correct, I don't see how the problem you describe might be a problem.
Joel.
Yes, that is the idea. Actually, whether the implementation uses a collection of vectors or other mechanism is an implementation detail. I use a map of vectors in the classifier container, but I will try other implementations. Is the map key something like the type_info:
http://www.cplusplus.com/reference/typeinfo/ If there is a separate vector for each type, then the storage for a container containing more than one type can't be contiguous, since the vectors for the containers for the types cannot be contiguous, or am I missing something? I think what Thorsten was aiming at in this post: http://article.gmane.org/gmane.comp.lib.boost.devel/243504 was each element in the container was truly contiguous. IOW, given a container, c, then. c.insert(T1()); c.insert(T2()); The T1 inserted into c would be contigous with the T2. [snip]
Date: Tue, 13 Aug 2013 23:33:25 +0400 From: Andrey Semashev <andrey.semashev@gmail.com>
- The container classifier is _not_ a sequence.
Why? Is this intentional?
Both intentional and accidental, because I want to allocate objects contiguously in memory I have to store them in a collection of vectors, the container is not a sequence but a collection of sequences, one sequence for every class in the classifier. I will implement a sequence, but later.
The above reinforces my above conclusion that T1 and T2 elements cannot be contiguous in the container. [snip] -regards, Larry
On 08/16/13 19:20, Larry Evans wrote:
On 08/16/13 08:21, Santiago Tapia wrote: [snip]
Yes, that is the idea. Actually, whether the implementation uses a collection of vectors or other mechanism is an implementation detail. I use a map of vectors in the classifier container, but I will try other implementations.
Is the map key something like the type_info:
http://www.cplusplus.com/reference/typeinfo/
If there is a separate vector for each type, then the storage for a container containing more than one type can't be contiguous, since the vectors for the containers for the types cannot be contiguous, or am I missing something? I think what Thorsten was aiming at in this post:
http://article.gmane.org/gmane.comp.lib.boost.devel/243504
was each element in the container was truly contiguous. IOW, given a container, c, then.
c.insert(T1()); c.insert(T2());
The T1 inserted into c would be contigous with the T2.
[snip] The attached demonstrates, I believe, what Thorsten was aiming at an shows the storage of *different* types in contiguous storage. HTH. -regards, Larry
Hi Larry,
[snip] The attached demonstrates, I believe, what Thorsten was aiming at an shows the storage of *different* types in contiguous storage.
I was hoping this could be done a lot easier. My outset is that objects are added by saying // in-place contruction by forwarding x and y cont.push_back<Derived>( x, y ); This should give maximum information about the size and alignment of Derived to the container, allthough I was hoping that some kind of maximal aligment could be assumed, eg. 4 bytes boundaries on 32 bit systems. I see no limitation in adding the elements this way, as it completely mirrors a container of pointers: ptr_container.push_back( new Derived( x, y ) ); So far so good. The polymorphic_vector< class Base, class Allocator > class template would internally only need an std::vector<char>. The question would be how to copy the objects? This is where I imagined the base class requirement should enter, that is, the base class of the class hierarchy should inherit from boost::polymophic_object which has a single function: unsigned copy( char* into, const char* from ) { // inplace copy or move return sizeof(Derived); } In any case, I would rather see virtual functions to be added to this interface if it removes the need to store things like size/alignment. When saying // in-place contruction by forwarding x and y cont.push_back<Derived>( x, y ); we should also store a pointer to the next element to allow forward iteration, so maybe a start and end pointer also needs to be stored directly in the container. Perhaps this can be avoided by just letting the user get a pointer from push_back. -Thorsten
On Aug 16, 2013, at 9:21 AM, Santiago Tapia <santiago.tapia@upm.es> wrote:
Date: Tue, 13 Aug 2013 23:33:25 +0400 From: Andrey Semashev <andrey.semashev@gmail.com>
- The allocator argument in the classifier will be applied to every object added to the classifier. Thus, the allocator is provided without its argument. The std::allocator is the default argument.
You can use the standard interface for allocator rebinding:
typedef allocator<T> allocator_T; typedef typename allocator_T::template rebind<U>::other allocator_U;
You can use std::allocator<void> by default then.
I am not sure how to do this. I need a allocator with a parameter in order to get: allocator<triangle>, allocator<square>, ... this allocator must be instantiated when an object of a new class is inserted in the classifier.
That's the point of rebind. Starting with allocator<A>, you can get allocator<B>. The spelling of allocator<B> just looks odd: typename allocator<A> template ::rebind<B>::other ___ Rob (Sent from my portable computation engine)
On Fri, Aug 16, 2013 at 5:21 PM, Santiago Tapia <santiago.tapia@upm.es>wrote:
Date: Tue, 13 Aug 2013 23:33:25 +0400 From: Andrey Semashev <andrey.semashev@gmail.com>
- The container classifier is _not_ a sequence.
Why? Is this intentional?
Both intentional and accidental, because I want to allocate objects contiguously in memory I have to store them in a collection of vectors, the container is not a sequence but a collection of sequences, one sequence for every class in the classifier. I will implement a sequence, but later.
The storage strategy does not mandate the interface of the container. unordered_set/map are implemented as a number of buckets (i.e. single-linked lists), yet they provide sequence interface with an additional ability to iterate within a single bucket. I don't see why a similar approach couldn't be taken in your container.
All in all the basic idea looks interesting, although I'm not sure about the particular classifier container. It looks very specific to me, the same functionality could be achieved with a multimap or unordered_multimap of polymorphic elements.
...or I should have said "multiset or unordered_multiset".
As far as I know it is not possible to get a multimap of a pure abstract class, therefore, for example, you can not use a multimap<string, shape> or multiset<shape> but you can use a classifier<shape> to store triangles, squares, or any derived class. I plan to implement an associate container later, thus you could have classifier<string, shape> and you could look for an object in the classifier using a key.
You can't create std::multiset<shape> but you can create boost::intrusive::multiset<shape>. The reason for that is that std::multiset attempts to allocate storage for shape, while boost::intrusive::multiset doesn't, leaving this to the user. This allows you to insert any objects derived from shape to the single boost::intrusive::multiset and work with this container pretty much the same way you would with std::multiset. You can even insert the very same object in multiple containers if you need to. I recommend you to have a look at Boost.Intrusive, it is a truly amazing library.
participants (5)
-
Andrey Semashev -
Larry Evans -
Rob Stewart -
Santiago Tapia -
Thorsten Ottosen