Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Design question - linked list or std::list

Reply
Thread Tools

Design question - linked list or std::list

 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      03-16-2009
* James Kanze:
> On Mar 15, 7:43 pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
>> * James Kanze:
>>> On Mar 15, 1:32 pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
>>>> * Angus:

>
> [...]
>>>> Avoid raw pointers. Use boost::shared_ptr and boost::weak_ptr.
>>>> I did this thing once, unfortunately as bug-fixing for
>>>> existing system implemented in Visual Basic, and it turned
>>>> you'll end up with circular references, but not more than can
>>>> be fixed by proper application of weak pointers.

>
>>> No. The pointers here are only used for navigation.

>
>> You don't know that the pointers are used for navigation.

>
> Actually, I do. Having working in telecoms for a large part of
> my career, I have a pretty good idea as to what is needed, and
> what isn't.


The above is a classic logic error. High-level domain knowledge does not
transfer to details of internal data structures. It can tell you some high level
properties, such as that there will likely be circular references, which I
commented on. It cannot, however, tell you the details -- even if one has
successfully implemented tens of such systems all in just about the same way.

In the absence of more detailed data structure information, and with the
information that the OP explicitly mentioned using std::list as opposed to using
raw pointers (presumably used in C style), the only sound recommendation is to
automate memory management and object lifetimes as far as possible.

For that, smart pointers and standard containers are the way to go, and given
that there will (almost certainly) be circular references, one should not
neglect to mention the necessity of using weak_ptr. Recommending raw pointers to
someone who feels it pertinent to mention use of std::list, it's bad advice. In
any case where shared_ptr presents a problem here there is a problem of
ownership and/or circularity, and raw pointers can only exacerbate that.


[snip]
> A somewhat closer analogy would be that my recommendation is
> like recommending to someone designing a "vehicle" that it
> should have round wheels.


Should it? Consider any watercraft or e.g a snowmobile...


Cheers & hth.,

- Alf

--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! Just going there is good. Linking
to it is even better! Thanks in advance!
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      03-17-2009
On Mar 16, 12:39 pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
> * James Kanze:
> > On Mar 15, 7:43 pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
> >> * James Kanze:
> >>> On Mar 15, 1:32 pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
> >>>> * Angus:


> > [...]
> >>>> Avoid raw pointers. Use boost::shared_ptr and
> >>>> boost::weak_ptr. I did this thing once, unfortunately as
> >>>> bug-fixing for existing system implemented in Visual
> >>>> Basic, and it turned you'll end up with circular
> >>>> references, but not more than can be fixed by proper
> >>>> application of weak pointers.


> >>> No. The pointers here are only used for navigation.


> >> You don't know that the pointers are used for navigation.


> > Actually, I do. Having working in telecoms for a large part
> > of my career, I have a pretty good idea as to what is
> > needed, and what isn't.


> The above is a classic logic error. High-level domain
> knowledge does not transfer to details of internal data
> structures. It can tell you some high level properties, such
> as that there will likely be circular references, which I
> commented on. It cannot, however, tell you the details --
> even if one has successfully implemented tens of such systems
> all in just about the same way.


It does give you a strong indication as to what the entity
objects might be. I pretty much know what the abstraction
behind a Call and a Party should be.

> In the absence of more detailed data structure information,
> and with the information that the OP explicitly mentioned
> using std::list as opposed to using raw pointers (presumably
> used in C style), the only sound recommendation is to automate
> memory management and object lifetimes as far as possible.


Actually, it sounds more like he hasn't really understood the
difference between entity objects and value objects. Not that
it matters in this case: if the Party are value objects, then
there should be no pointers, and if they are entity objects
(more logical), then there should be raw pointers.

> For that, smart pointers and standard containers are the way
> to go,


Smart pointers are almost never the way to go, and I can't think
of a case off hand where they'd be appropriate in a standard
container. (Well, I can, but they're pretty special.)

> and given that there will (almost certainly) be circular
> references, one should not neglect to mention the necessity of
> using weak_ptr.


Even better is to recommend raw pointers, and not have to worry
about where you have to break the cycle.

> Recommending raw pointers to someone who feels it pertinent to
> mention use of std::list, it's bad advice. In any case where
> shared_ptr presents a problem here there is a problem of
> ownership and/or circularity, and raw pointers can only
> exacerbate that.


What a lot of bullshit. Circularity is a problem created by
shared_ptr---it simply doesn't exist if you use raw pointers.
And there's no issues of ownership either, except in so far as
smart pointers introduce one.

This is one case where it would be a serious design error to
even consider shared_ptr.

> [snip]


> > A somewhat closer analogy would be that my recommendation is
> > like recommending to someone designing a "vehicle" that it
> > should have round wheels.


> Should it? Consider any watercraft or e.g a snowmobile...


If they have wheels, the wheels should be round.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      03-17-2009
On Mar 16, 2:48 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Mar 15, 8:52 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >> James Kanze wrote:
> >>> delete this ;


> >> Boo.


> > Other suggestions. If you have a better alternative, present it
> > (and explain why it is better).


> The alternative I already suggested was that a separate object
> be used to manage the lifetimes of the calls. "Why it is
> better" is left as an exercise to the reader.


But that's what I can't figure out. Why introduce additional
objects, when the object itself knows best? (In other words,
why introduce additional complexity when there's no need for
it?)

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      03-17-2009
* James Kanze:
>

[snip]
> if the Party are value objects, then
> there should be no pointers, and if they are entity objects
> (more logical), then there should be raw pointers.


Goodie , there remains no case for smart pointers in any system -- for
either you have value objects (no pointers), or entity objects (raw pointers).


> Smart pointers are almost never the way to go, and I can't think
> of a case off hand where they'd be appropriate in a standard
> container. (Well, I can, but they're pretty special.)


I think I can help you. Right above you have presented an unassailable argument
that smart pointers are /never/ appropriate. So there's no need for opening up
for some cases, "almost" never, which is inconsistent; Just Say No.


[snip]
> What a lot of bullshit. Circularity is a problem created by
> shared_ptr---it simply doesn't exist if you use raw pointers.
> And there's no issues of ownership either, except in so far as
> smart pointers introduce one.


Yap, agreed, those fools inventing weak_ptr really didn't understand a thing.


Cheers,

- Alf

--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! Just going there is good. Linking
to it is even better! Thanks in advance!
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      03-17-2009
On Mar 17, 5:27 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Mar 16, 2:48 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >> James Kanze wrote:
> >>> On Mar 15, 8:52 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >>>> James Kanze wrote:
> >>>>> delete this ;


> >>>> Boo.


> >>> Other suggestions. If you have a better alternative,
> >>> present it (and explain why it is better).


> >> The alternative I already suggested was that a separate
> >> object be used to manage the lifetimes of the calls. "Why
> >> it is better" is left as an exercise to the reader.


> > But that's what I can't figure out. Why introduce
> > additional objects, when the object itself knows best? (In
> > other words, why introduce additional complexity when
> > there's no need for it?)


> I dispute your premises: the object does not know best,


So who knows better when a call should be terminated than the
call itself?

> nor would a separate object to manage lifetimes represents
> additional, unneeded complexity.


More objects, more complexity. And who manages the lifetime of
the object which manages the call objects' lifetimes?

> The code "delete this" shows an unhealthy lack of clear
> ownership semantics, which IMO are the most important aspect
> of C++ development. You've shown an illness, just not the
> symptoms; in a large program, though, such symptoms will
> arise.


The aversion to "delete this" shows an unhealthy lack of
understanding of basic OO design principles. Nobody owns the
object; nobody should. The object has intelligence of its own.

> Lifetime management is a vital responsibility; further, no
> object should be responsible for more than one thing. It is
> therefore nonsensical to have an object managing its own
> lifetime, much less doing this sort of partial lifetime
> management.


The call object is responsible for call management. That
includes shutting down the call, and terminating its existance
when appropriate.

> Each dynamically allocated object ought to have an owner,


Why? (And why just dynamically allocated objects?)

> and unless an explicit transfer of ownership has taken place,
> the owner should be the creator of the object. The owner is
> responsible for both creation and deletion. Since the object
> obviously didn't create itself, it hardly makes sense for it
> to destroy itself.


That's just silly prejudice. And totally impossible to
implement in just about any server (and probably many other
applications as well): the whole point of dynamically allocating
an object is that it will outlive whatever (function or other
object) which creates it. Otherwise, just make it a local
variable or a member.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      03-18-2009
On Mar 18, 1:21 am, Jeff Schwab <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Mar 17, 5:27 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >> James Kanze wrote:
> >>> On Mar 16, 2:48 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >>>> James Kanze wrote:
> >>>>> On Mar 15, 8:52 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >>>>>> James Kanze wrote:
> >>>>>>> delete this ;


> >>>>>> Boo.


> >>>>> Other suggestions. If you have a better alternative,
> >>>>> present it (and explain why it is better).


> >>>> The alternative I already suggested was that a separate
> >>>> object be used to manage the lifetimes of the calls. "Why
> >>>> it is better" is left as an exercise to the reader.


> >>> But that's what I can't figure out. Why introduce
> >>> additional objects, when the object itself knows best? (In
> >>> other words, why introduce additional complexity when
> >>> there's no need for it?)


> >> I dispute your premises: the object does not know best,


> > So who knows better when a call should be terminated than
> > the call itself?


> The owner of the call.


A call doesn't really have an owner. I guess you could call the
initiating party the owner, but he won't necessarily be around
when the call needs to be terminated. One of the basic
characteristics of a call in modern systems is that once
established, it has a life independent of the establishing
party.

> >> nor would a separate object to manage lifetimes represents
> >> additional, unneeded complexity.


> > More objects, more complexity.


> That does not follow. Often, in fact, more objects lead to
> less complexity. You obviously don't stick all your code into
> a single, unstructured object, so I'm not sure why you would
> make this claim.


In this case, the added object doesn't provide any additional
functionality; it just adds complexity, for no reason.

> > And who manages the lifetime of the object which manages the
> > call objects' lifetimes?


> Its owner, and so on, up to the top level of the program. If
> you're ever built a GUI, you know that there are a few
> top-level entities (usually frames), and that every other
> widget falls into a hierarchy, with a clear ownership tree.


Yes, and I also know that in most cases, it isn't the *owner*
who destroys the various objects, at least at specific levels;
if the frame is destructed, of course, it may destruct
everything below it, but if you swap specific panes in and out,
the frame doesn't normally get involved.

> This kind of organization isn't GUI-specific, nor in fact does
> any other kind of organization make much sense for
> general-purpose programming.


I'm sorry, but in practice, I find very few cases in general
programming where "ownership" makes sense. It's sometimes
introduced artificially into C++, because C++ lacks a garbage
collector, and it does make sense for some special low level
objects, like mutex locks (but such objects are usually local
variables, so the issue doesn't really arise), but most entity
objects don't logically have an owner, and forcing them to have
one distorts the design.

> The function call mechanism, for example, forms such a tree:
> Each function-call is made by, and outlived by, some other,
> parent call.


Yes, but if you're dynamically allocating objects, instead of
using local variables, it's precisely because the function call
model of nested lifetimes doesn't apply.

[...]
> >> Lifetime management is a vital responsibility; further, no
> >> object should be responsible for more than one thing. It
> >> is therefore nonsensical to have an object managing its own
> >> lifetime, much less doing this sort of partial lifetime
> >> management.


> > The call object is responsible for call management. That
> > includes shutting down the call, and terminating its
> > existance when appropriate.


> You're using call to mean two different things there: The
> physical process represented by the software object, and the
> object itself.


It's an entity object; it models a non-software entity in the
actual application.

> >> Each dynamically allocated object ought to have an owner,


> > Why?


> I didn't realize we were this far apart. This is a topic for
> a book, not a usenet post.


Yes, but to date, I've yet to find any book arguing your point
of view. The major references (e.g. Booch) tend to agree with
me.

> > (And why just dynamically allocated objects?)


> Because auto objects are effectively owned by their stack
> frames, which aren't objects.


That could be argued as well. In C++, for historical
reasons, stack frames aren't treated as objects, but but lambda
comes very close to eliminating the differences in some cases.

> Static objects are owned by the larger run-time environment,
> to the extent they have ownership at all. There's always a
> base case to ownership.


Yes. The OS owns your program, and you (or your employer) own
the machine on which it runs.

So? I think you're forcing the issue---quite obviously, the
sense of "own" is different when I say you own the machine. If
you diffuse the meaning this much, yes, every object has an
owner. Or several. Or at times none. But if you diffuse the
sense of "own" this much, it has nothing to do with lifetime, or
who should call delete.

> >> and unless an explicit transfer of ownership has taken place,
> >> the owner should be the creator of the object. The owner is
> >> responsible for both creation and deletion. Since the object
> >> obviously didn't create itself, it hardly makes sense for it
> >> to destroy itself.


> > That's just silly prejudice.


> Thanks for keeping this erudite.


As long as you can't give a reason for it, it's prejudice. To
date, you've made a lot of pronouncements as to how things
"should" be, without giving any reasons as to why they should
be. And what you claim "should" be goes against concrete
experience.

> > And totally impossible to implement in just about any server
> > (and probably many other applications as well): the whole
> > point of dynamically allocating an object is that it will
> > outlive whatever (function or other object) which creates
> > it. Otherwise, just make it a local variable or a member.


> The point of dynamic allocation is that you don't know a
> priori how many of something you'll need, or else that it may
> not fit in the stack. That's why we have resizable
> containers. If a function needs to return something that will
> outlive the call, that something should be obtained from a
> factory that lives at a higher level of abstraction. This is
> the canonical case of dependency inversion. Parameterizing
> the code with a specific factory is the canonical case for
> dependency injection.


Adding factories for no other reason than to ensure that the
creating object outlives its creator is just added verbosity.
What's the difference between:
return XxxFactory::instance().createObject() ;
and
return new Xxx ;
or between:
XxxFactory::instance().deleteMe() ;
and
delete this ;
? Other than you've introduced added verbosity, and additional
code which needs maintaining.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
hanukas
Guest
Posts: n/a
 
      03-18-2009
On Mar 17, 6:27*pm, Jeff Schwab <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Mar 16, 2:48 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >> James Kanze wrote:
> >>> On Mar 15, 8:52 pm, Jeff Schwab <(E-Mail Removed)> wrote:
> >>>> James Kanze wrote:
> >>>>> * * * * * * * * delete this ;

>
> >>>> Boo.

>
> >>> Other suggestions. *If you have a better alternative, present it
> >>> (and explain why it is better).

>
> >> The alternative I already suggested was that a separate object
> >> be used to manage the lifetimes of the calls. *"Why it is
> >> better" is left as an exercise to the reader.

>
> > But that's what I can't figure out. *Why introduce additional
> > objects, when the object itself knows best? *(In other words,
> > why introduce additional complexity when there's no need for
> > it?)

>
> I dispute your premises: the object does not know best, nor would a
> separate object to manage lifetimes represents additional, unneeded
> complexity.
>
> The code "delete this" shows an unhealthy lack of clear ownership
> semantics, which IMO are the most important aspect of C++ development.
> You've shown an illness, just not the symptoms; in a large program,
> though, such symptoms will arise.
>
> Lifetime management is a vital responsibility; further, no object should
> be responsible for more than one thing. *It is therefore nonsensical to
> have an object managing its own lifetime, much less doing this sort of
> partial lifetime management.
>
> Each dynamically allocated object ought to have an owner, and unless an
> explicit transfer of ownership has taken place, the owner should be the
> creator of the object. *The owner is responsible for both creation and
> deletion. *Since the object obviously didn't create itself, it hardly
> makes sense for it to destroy itself.- Hide quoted text -
>
> - Show quoted text -


Factory design pattern. COM. Create. Release. Enough said.
 
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
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments