Collections of derived objects

Discussion in 'C++' started by Olivier Scalbert, Mar 19, 2010.

  1. 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
     
    Olivier Scalbert, Mar 19, 2010
    #1
    1. Advertising

  2. 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
     
    Marcel Müller, Mar 19, 2010
    #2
    1. Advertising

  3. On 19 mar, 07:40, Olivier Scalbert <>
    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
     
    Michael Doubez, Mar 19, 2010
    #3
  4. On 19 mar, 13:55, "Daniel T." <> wrote:
    > Olivier Scalbert <> 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
     
    Michael Doubez, Mar 19, 2010
    #4
  5. 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
     
    Marcel Müller, Mar 19, 2010
    #5
  6. Olivier Scalbert

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Mar 19, 2010
    #6
  7. On 19 mar, 15:32, Juha Nieminen <> 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
     
    Michael Doubez, Mar 19, 2010
    #7
  8. 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
     
    Marcel Müller, Mar 19, 2010
    #8
  9. Olivier Scalbert

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Mar 19, 2010
    #9
  10. Olivier Scalbert

    Noah Roberts Guest

    In article <4ba31cbc$0$2858$>,
    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.
     
    Noah Roberts, Mar 19, 2010
    #10
  11. Olivier Scalbert

    Jeff Flinn Guest

    Juha Nieminen 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), 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
     
    Jeff Flinn, Mar 19, 2010
    #11
  12. Olivier Scalbert

    Brian Wood Guest

    On Mar 19, 9:32 am, Juha Nieminen <> 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.
    >


    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
     
    Brian Wood, Mar 19, 2010
    #12
  13. Kai-Uwe Bux wrote:
    > 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
     
    Marcel Müller, Mar 19, 2010
    #13
  14. 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





    Olivier Scalbert wrote:
    > 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
     
    Olivier Scalbert, Mar 20, 2010
    #14
  15. Olivier Scalbert

    Jorgen Grahn Guest

    On Fri, 2010-03-19, Marcel Müller wrote:
    > 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> >;


    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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Mar 20, 2010
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Doug Poland
    Replies:
    9
    Views:
    742
    VisionSet
    Sep 27, 2003
  2. Replies:
    4
    Views:
    427
    Alf P. Steinbach
    May 23, 2007
  3. Replies:
    1
    Views:
    405
    myork
    May 23, 2007
  4. Replies:
    1
    Views:
    395
    Victor Bazarov
    May 23, 2007
  5. mutex
    Replies:
    0
    Views:
    219
    mutex
    Jul 27, 2003
Loading...

Share This Page