Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Collections of derived objects

Reply
Thread Tools

Collections of derived objects

 
 
Olivier Scalbert
Guest
Posts: n/a
 
      03-19-2010
Hello,

Let's say I have a base class Event and some sub classes EventType1,
EventType2, ...


1)
I would like to have a collection (vector or list for example) of a mix
of EventType1, EventType2, ...

I think I have to create a vector<Event*> and starts playing with "new".
And of course, I will forget the "delete" !

Are there any other options, to keep the code clean ?

2)
I would like to transform (serialize in string or something else) these
events (contained into a collection). As I will have different
transformations, I do not want to put the serialization code inside the
events, to not pollute them. How can I do that, in a clean way ? Visitor
pattern or something like that?

Thanks you very much and have a nice day !

Olivier
 
Reply With Quote
 
 
 
 
Marcel Müller
Guest
Posts: n/a
 
      03-19-2010
Hi,

Olivier Scalbert wrote:
> I think I have to create a vector<Event*> and starts playing with "new".
> And of course, I will forget the "delete" !
>
> Are there any other options, to keep the code clean ?


std::vector<boost::shared_ptr<Event> >;

or I would prefer

std::vector<boost::intrusive_ptr<Event> >;

Btw.: unless you want random access to the Events in your container, a
linked List might be more appropriate.


> 2)
> I would like to transform (serialize in string or something else) these
> events (contained into a collection). As I will have different
> transformations, I do not want to put the serialization code inside the
> events, to not pollute them. How can I do that, in a clean way ? Visitor
> pattern or something like that?


You need a serializer.

If you have n Event types and m target formats you have in general n*m
Implementations. Do you really want to do this?
(Note, this is a multiple dispatch problem.)


Marcel
 
Reply With Quote
 
 
 
 
Michael Doubez
Guest
Posts: n/a
 
      03-19-2010
On 19 mar, 07:40, Olivier Scalbert <(E-Mail Removed)>
wrote:
> Let's say I have a base class Event and some sub classes EventType1,
> EventType2, ...
>
> 1)
> I would like to have a collection (vector or list for example) of a mix
> of EventType1, EventType2, ...
>
> I think I have to create a vector<Event*> and starts playing with "new".
> And of course, I will forget the "delete" !


If your class is properly encapsulated and you define member functions
for inserting/removing elements, there is no reason you would forget
to delete them.

> Are there any other options, to keep the code clean ?


Use an appropriate strategy.
Some mentioned smart pointer; I think it may be overkill if your only
concern is not forgetting to delete them.

> 2)
> I would like to transform (serialize in string or something else) these
> events (contained into a collection). As I will have different
> transformations, I do not want to put the serialization code inside the
> events, to not pollute them. How can I do that, in a clean way ? Visitor
> pattern or something like that?


I don't understand what you call transformation.

Visitor is a solution but you also could abstract the serialization
sink.

--
Michael
 
Reply With Quote
 
Michael Doubez
Guest
Posts: n/a
 
      03-19-2010
On 19 mar, 13:55, "Daniel T." <(E-Mail Removed)> wrote:
> Olivier Scalbert <(E-Mail Removed)> wrote:
> > Let's say I have a base class Event and some sub classes EventType1,
> > EventType2, ...

>
> > 1)
> > I would like to have a collection (vector or list for example) of a mix
> > of EventType1, EventType2, ...

>
> > I think I have to create a vector<Event*> and starts playing with "new".
> > And of course, I will forget the "delete" !

>
> > Are there any other options, to keep the code clean ?

>
> I agree with Marcel's answer on this one. Use a smart pointer. If events
> are immutable, you might also consider the flyweight pattern.
>
> In the Flyweight, a factory keeps tabs on every possible event object
> (conceptually at least, it can create them on demand,) and that way you
> don't have to worry about deleting them. I stress though that this
> pattern only works well if your Event objects are immutable.


Flyweight pattern is a structural pattern not a creational one. The
architecture you are describing may work but it is not a flyweight.

More a kind of factory/prototype mix always serving the same instances
(possibly lazily created).

[snip]

--
Michael
 
Reply With Quote
 
Marcel Müller
Guest
Posts: n/a
 
      03-19-2010
Juha Nieminen wrote:
> Marcel Müller wrote:
>> Btw.: unless you want random access to the Events in your container, a
>> linked List might be more appropriate.

>
> Out of curiosity: Why?


Because event collections tend to grow over time and this would cause a
bunch of reallocations in the vector resulting at least in O(n*log n).
With a linked list you are O(n).

Of course, if you do not carry many event and/or know the number of
events approximately at the of the vector construction, this does not apply.


Marcel
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      03-19-2010
Marcel Müller wrote:

> Juha Nieminen wrote:
>> Marcel Müller wrote:
>>> Btw.: unless you want random access to the Events in your container, a
>>> linked List might be more appropriate.

>>
>> Out of curiosity: Why?

>
> Because event collections tend to grow over time and this would cause a
> bunch of reallocations in the vector resulting at least in O(n*log n).
> With a linked list you are O(n).

[...]

No: std::vector<> has amortized constant time for inserting elements.
Therefore, a bunch of n insertions takes O(n) time.

BTW: Efficiency is rarely ever a reason to use std::list (std::vector and
std::deque tend to have better memory locality). Iterator invalidation
properties of containers can provide a reason to use std::list.


Best

Kai-Uwe Bux
 
Reply With Quote
 
Michael Doubez
Guest
Posts: n/a
 
      03-19-2010
On 19 mar, 15:32, Juha Nieminen <(E-Mail Removed)> wrote:
> Kai-Uwe Bux wrote:
> > Marcel M ller wrote:

>
> >> Juha Nieminen wrote:
> >>> Marcel M ller wrote:
> >>>> Btw.: unless you want random access to the Events in your container, a
> >>>> linked List might be more appropriate.
> >>> * Out of curiosity: Why?
> >> Because event collections tend to grow over time and this would cause a
> >> bunch of reallocations in the vector resulting at least in O(n*log n).
> >> With a linked list you are O(n).

> > [...]

>
> > No: std::vector<> has amortized constant time for inserting elements.
> > Therefore, a bunch of n insertions takes O(n) time.

>
> > BTW: Efficiency is rarely ever a reason to use std::list (std::vector and
> > std::deque tend to have better memory locality). Iterator invalidation
> > properties of containers can provide a reason to use std::list.

>
> * If std::vector reallocation is a (real) concern, then std::deque is
> the most efficient alternative.
>
> * I don't really understand why so many people seem to think that
> std::vector and std::list are the only viable alternatives for
> sequential containers, completely dismissing std::deque.
>
> * std::deque is significantly faster than std::list with most operations
> (for the simple reason that it executes significantly less allocations
> and deallocations),


Insertion/deletion near the middle incurs N/2 moves.
Better than vector<> by hals but still a hit for big objects.

> consumes less memory (unless we are talking about
> just a few elements) and offers constant-time random access. Also
> pointers don't get invalidated if elements are added to a std::deque (in
> the same way as they don't when using a std::list).


They are not invalidate for operation at either end (front/back).
Otherwise, they do get invalidated.

> * I can't think of many reasons why one would want to use std::list
> instead of std::deque.


When you store objects that must not be copied/invalidated upon
insertion/deletion in the container. Or if lots of insertion/deletion
is done in the middle.

[snip]


If this case, the OP is storing pointer. I don't see the matter with
reallocation/copy time. It all depends on how the container is used.
It the OP must hold distinct instances and order of insertion is not
important, a std::set<> is also a good choice.

--
Michael
 
Reply With Quote
 
Marcel Müller
Guest
Posts: n/a
 
      03-19-2010
Kai-Uwe Bux wrote:
> No: std::vector<> has amortized constant time for inserting elements.
> Therefore, a bunch of n insertions takes O(n) time.


Where did you get that from?
O(1) for an insertion is only sufficient as long as you reserved enough
space before. The reallocation is O(n). So you could end up with O(n²)
when inserting n elements. However, if the implementation uses
exponential growth the overall performance will be O(n*log n). The
drawback of this implementation is the memory footprint. However,
nowadays almost no one cares about memory resources as long as it is
still O(n).

> BTW: Efficiency is rarely ever a reason to use std::list (std::vector and
> std::deque tend to have better memory locality).


.... if you store the objects by value. If you store them by reference,
it makes not so much difference.

> Iterator invalidation
> properties of containers can provide a reason to use std::list.


Of course.


Marcel
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      03-19-2010
Marcel Müller wrote:

> Kai-Uwe Bux wrote:
>> No: std::vector<> has amortized constant time for inserting elements.
>> Therefore, a bunch of n insertions takes O(n) time.

>
> Where did you get that from?


E.g., the standard [23.1.1/12]:
Table 68 lists sequence operations that are provided for some types of
sequential containers but not others. An implementation shall provide
these operations for all container types shown in the ??container??
column, and shall implement them so as to take amortized constant time.

> O(1) for an insertion is only sufficient as long as you reserved enough
> space before. The reallocation is O(n). So you could end up with O(n²)
> when inserting n elements. However, if the implementation uses
> exponential growth the overall performance will be O(n*log n).


If the implementation uses exponential growth, then you get O(n). To see
this, assume a growth factor of 2 (for simplicity). If you insert 2^20
items, the sequence of events runs as follows:

start: no memory allocated, no item stored, no reallocation done
1st item: space for 1 item allocated,
one call for copy constructor (total = 1 = 2^1 -1)
2nd item: space for 2 items allocated,
two calls to copy constructors,
space for one item returned (total = 3 = 2^2-1)
3rd item: space for 4 items allocated,
three calls to copy constructors (total = 6)
space for for two items returned
4th item: one call to copy constructor (total = 7 = 2^3-1)
5th item: space for 8 items allocated,
5 calls to copy constructors (total = 12),
space for 4 items returned
6th item -- 8th item: one call each (total = 15 = 2^4-1)
9th item: space for 16 items allocated
9 calls to copy constructor (total = 24)
space for 8 items returned
10th -- 16th item: one call per item (total = 31 = 2^5-1)
...

When the 2^20th item is inserted, there is a total of 2^21-1 calls to the
copy constructor. Thus, the total cost of all reallocations is O(n) with a
constant of 2. It is true that reallocation happens log(n) times. But not
all of these reallocations incur a cost of n.


> The drawback of this implementation is the memory footprint. However,
> nowadays almost no one cares about memory resources as long as it is
> still O(n).


True. The growth factor influences the reallocation cost and the memory
footprint. The less space you want to waste, the more time you have to spend
on copying stuff around.


Best

Kai-Uwe Bux
 
Reply With Quote
 
Noah Roberts
Guest
Posts: n/a
 
      03-19-2010
In article <4ba31cbc$0$2858$(E-Mail Removed)>,
http://www.velocityreviews.com/forums/(E-Mail Removed) says...
>
> Hello,
>
> Let's say I have a base class Event and some sub classes EventType1,
> EventType2, ...
>
>
> 1)
> I would like to have a collection (vector or list for example) of a mix
> of EventType1, EventType2, ...
>
> I think I have to create a vector<Event*> and starts playing with "new".
> And of course, I will forget the "delete" !
>
> Are there any other options, to keep the code clean ?


You can make many higherarchies that you have control over value types
with some work. It involves the use of the handle/body idiom:

// event.h
struct event
{
// NVI
typedef ? event_type_id;
event_type_id event_type() const { return pimpl->event_type(); }
//...

event(event_type_id id);

struct impl
{
virtual event_type_id event_type() const = 0;
// ...
};

private:
std::auto_ptr<impl> pimpl;
};

// event.cpp

struct x_event : event::impl
{
event_type_id event_type() const { return ??; }
};

event::impl * impl_factory(event_type_id id)
{
event::impl * = new ?? discovery;
}

event::event(event_type_id id) : pimpl(impl_factory(id)) {}

-------------------------

Issue with this design: subclasses MUST all have the exact same requests
to implement. For example, mouse_event could not have extra or
different functionality from keyboard_event. It could only implement
that functionality with differing behavior. You're probably better off
with the pointer solution but I figured more knowledge can't hurt.

>
> 2)
> I would like to transform (serialize in string or something else) these
> events (contained into a collection). As I will have different
> transformations, I do not want to put the serialization code inside the
> events, to not pollute them. How can I do that, in a clean way ? Visitor
> pattern or something like that?


Visitor is debatably clean. I have found it quite useful. You could
also get "Modern C++ Design" and read the chapter on multimethods.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Derived::Derived(const Base&) and Derived& operator=(const Base&) developereo@hotmail.com C++ 1 05-23-2007 01:44 PM
Derived::Derived(const Base&) developereo@hotmail.com C++ 4 05-23-2007 09:32 AM
Derived::Derived(const Base&) and Derived& operator=(const Base&) developereo@hotmail.com C++ 1 05-23-2007 12:07 AM
Sorting collections based on nested collections Doug Poland Java 9 09-27-2003 10:46 PM
InnerProperty Persistance for Collections containing other Collections mutex ASP .Net Building Controls 0 07-27-2003 02:45 PM



Advertisments