Collections of derived objects

[Olivier Scalbert]

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

 

[Marcel Müller]

Hi,

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

 

[Michael Doubez]

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 Doubez]

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]

 

[Marcel Müller]

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

 

[Kai-Uwe Bux]

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

 

[Michael Doubez]

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.

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.

 

[Marcel Müller]

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

 

[Kai-Uwe Bux]

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

 

[Noah Roberts]

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.

 

[Jeff Flinn]

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), 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).

I can't think of many reasons why one would want to use std::list
instead of std::deque. The only thing I can think of is if one wants

While I haven't analyzed performance of std::list iterating through
std::deque is significantly slower than iterating through a std::vector
on MSVC8 and XCode3.1.2 gcc 4.0. Until we get hierarchical algorithms
iterator performance is another dimension to deciding which container
type to use.

Jeff

 

[Brian Wood]

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.

I worked on a project that I thought overused deque. I'd
mention stable_vector:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
http://webEbenezer.net/misc/stable_vector.hpp


Brian Wood
http://webEbenezer.net
(651) 251-9384


"House and riches are the inheritance of fathers: and a
prudent wife is from the L-RD." Proverbs 19:14

 

[Marcel Müller]

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.

You are right. I forgot about that fact.


Marcel

 

[Olivier Scalbert]

Hello,

Thanks to all of you.
I have a lot of info to digest now !
;-)

If you are curious, just let me give some context info !

The events hierarchy will be midi events.
The collections will be tracks (time ordered midi events).

The tracks will be generated by a higher level component (kind of
compositor).

The generated tracks will be transformed into a midi file.

Midi events transformations: one for serialize in midi bytes and one for
display nice text info (for debug).

So no real time (at least now), only batch processing !

Other challenge: I would like to avoid new and delete stuff (see the
interesting discussion in
http://groups.google.com/group/comp...c?lnk=gst&q=olivier+scalbert#92c3ef30416f766c
)

Again thanks you everybody !


Olivier

 

[Jorgen Grahn]

Hi,



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

or I would prefer

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

Or just wrap that vector<Event*> in a class, expose the functionality
you need, and make sure this class manages the objects properly.
Works well at least for some problems.

/Jorgen