Design question - linked list or std::list

[Angus]

Hello

I am modelling a telephone system and I have created a call and a
party class. A call can have one to many parties. For example in a
conference call there can be 3 or more parties. In a call transfer
there can be 3 parties and one of the parties disconnects to transfer
the call.

I need to be able to traverse the list of parties on each call. for
example if each party to the call is disconnected I can remove the
call object.

I create the call object as a pointer and so I delete when the each
party to the call has disconnected. The call object has a std::list
of the party objects. Currently, the list is of party objects, not
pointers to party objects.

I was wondering if it would be better to change the design so that the
std::list is of pointers to party. Or even to have the call object
create party* 's and the party object to be a linked list - ie a means
to SetNextParty(party* next).

But if I implement as a linked list I have the hassle of having to
delete each party. I would do this when the call* was being deleted.

Anyone got any comments on the best approach?

A

 

[Alf P. Steinbach]

* Angus:

Hello

I am modelling a telephone system and I have created a call and a
party class. A call can have one to many parties. For example in a
conference call there can be 3 or more parties. In a call transfer
there can be 3 parties and one of the parties disconnects to transfer
the call.

I need to be able to traverse the list of parties on each call. for
example if each party to the call is disconnected I can remove the
call object.

I create the call object as a pointer and so I delete when the each
party to the call has disconnected. The call object has a std::list
of the party objects. Currently, the list is of party objects, not
pointers to party objects.

I was wondering if it would be better to change the design so that the
std::list is of pointers to party. Or even to have the call object
create party* 's and the party object to be a linked list - ie a means
to SetNextParty(party* next).

But if I implement as a linked list I have the hassle of having to
delete each party. I would do this when the call* was being deleted.

Anyone got any comments on the best approach?

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.

std::list is good idea in C++.

Try to avoid setters and getters, they're generally in the same class of
features-to-avoid as global variables, indicating redundantly duplicated logic
at caller sites, i.e. that you're missing some crucial abstraction(s).


Cheers & hth.,

- Alf

 

[James Kanze]

I am modelling a telephone system and I have created a call
and a party class. A call can have one to many parties. For
example in a conference call there can be 3 or more parties.
In a call transfer there can be 3 parties and one of the
parties disconnects to transfer the call.

I need to be able to traverse the list of parties on each
call. for example if each party to the call is disconnected I
can remove the call object.

I create the call object as a pointer and so I delete when the
each party to the call has disconnected. The call object has
a std::list of the party objects. Currently, the list is of
party objects, not pointers to party objects.

I'm having trouble with your vocabulary. You don't "create
something as a pointer", you create an object (which probably
isn't a pointer). If your system is anything like the telephone
systems I've worked on, then Party and Call have identity (and
explicit lifetimes), and can't be copied, so all of your
containers would just contain pointers.

The simplest solution would probably be to use std::set for the
parties of a Call, e.g.:

class Call
{
public:
explicit Call( Party* initializingParty )
{
connect( initializingParty ) ;
}

void connect( Party* addedParty )
{
myConnectedParties.insert( addedParty ) ;
}

void disconnect( Party* removedParty )
{
myConnectedParties.erase( removedParty ) ;
if ( myConnectedParties.empty() ) {
delete this ;
}
}

private:
std::set< Party* > myConnectedParty ;
} ;

Of course, you'll need additional logic for other aspects of the
call.

I was wondering if it would be better to change the design so
that the std::list is of pointers to party. Or even to have
the call object create party* 's and the party object to be a
linked list - ie a means to SetNextParty(party* next).

I can't think of why you'd use a list here. (Given the
typically small size of the set, using std::vector would
probably be more efficient, but it requires more code.) And I
can't quite imagine a case where Party would be copiable, and
could be used in a standard container.

But if I implement as a linked list I have the hassle of
having to delete each party. I would do this when the call*
was being deleted.

You only delete a Party when it becomes unknown to the system.
Not when it disconnects from a call.

 

[James Kanze]

* 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. As you
point out, boost::smart_ptr will only complicate things; using
raw pointers is far simpler, safer and more appropriate.

std::list is good idea in C++.

Better than implementing your own, but in this case, I'd use
either std::set or std::vector.

 

[James Kanze]

Angus wrote:

Why? Why not let a standard collection manage the calls, just
as a collection manages the parties? Even if a collection
isn't the right tool, a smart-pointer might be.

Because calls (and parties) are entity objects, and have
explicit lifetimes which have nothing to do with containers (or
pointers) used for navigation, and you can't use containers of
the objects, because they don't support copy. This is a
classical example of a case where he needs raw pointers; smart
pointers just lead to more complicated code.

 

[Alf P. Steinbach]

* James Kanze:

No. The pointers here are only used for navigation.

You don't know that the pointers are used for navigation. And chances are they
will not be purely navigation. Don't recommend an unsafe alternative just
because you think or wish there's a chance that it might be safe.

As you
point out, boost::smart_ptr will only complicate things; using
raw pointers is far simpler, safer and more appropriate.

I'm sorry, that's wrong.

Better than implementing your own, but in this case, I'd use
either std::set or std::vector.

I was commenting on the OP's info that he's using std::list; I was not making a
freestanding recommendation. There is too little to go on regarding his data
structures, what they are and what they will be, to make a freestanding
recommendation. I know the big layout from work in that domain, but the details
you'd need for making the choice that you're making are not available, so that
recommendation is most likely the opposite of helpful -- your recommendation
is sort of like recommending to someone designing a "vehicle" that it should
have rubber tires, which is helpful only by chance, if it is.


Cheers & hth.,

- Alf

 

[James Kanze]

* James Kanze:

[...]

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.

And chances are they will not be purely navigation.

In which case, that's the error that needs fixing.

Don't recommend an unsafe alternative just because you think
or wish there's a chance that it might be safe.

In this case, it's boost::shared_ptr which would be unsafe, and
likely lead to memory leaks (due to cycles).

I'm sorry, that's wrong.

No. I've worked on enough different systems to know,
particularly in this domain. Navigation is important, objects
have explicit lifetimes, and boost::shared_ptr is not
appropriate for navigation and objects with explicit lifetimes.

I was commenting on the OP's info that he's using std::list; I
was not making a freestanding recommendation. There is too
little to go on regarding his data structures, what they are
and what they will be, to make a freestanding recommendation.

Yes and no. Knowing the domain quite well, I do have quite a
bit to go on. But seriously, you probably know enough about
telephones, and using them, to be able to guess what he's trying
to do (at least at the level he has asked about---call
management is a lot more complicated than that).

I know the big layout from work in that domain, but the
details you'd need for making the choice that you're making
are not available, so that recommendation is most likely the
opposite of helpful -- your recommendation is sort of like
recommending to someone designing a "vehicle" that it should
have rubber tires, which is helpful only by chance, if it is.

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

 

[James Kanze]

Boo.

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

 

[Guest]

I am modelling a telephone system and I have created a call and a
party class.  A call can have one to many parties.  For example in a
conference call there can be 3 or more parties.  In a call transfer
there can be 3 parties and one of the parties disconnects to transfer
the call.

ok so far

I need to be able to traverse the list of parties on each call.  for
example if each party to the call is disconnected I can remove the
call object.

what does "remove" mean. Yes , you remove it from the call, but what
happens to it next?

I create the call object as a pointer and so I delete when the each
party to the call has disconnected.

why are calls different from parties? They both seem equally dynamic
to me.

 The call object has a std::list
of the party objects.  Currently, the list is of party objects, not
pointers to party objects.

as someone else said, why a list?

I was wondering if it would be better to change the design so that the
std::list is of pointers to party.  Or even to have the call object
create party* 's

that doesn't sound right to me. I'd have thought something external
to the call would create parties.

and the party object to be a linked list - ie a means
to SetNextParty(party* next).

But if I implement as a linked list I have the hassle of having to
delete each party.

I think you have to "delete" or "free" the party however you
implement this. When you transfer a call one party gets removed
and another one added. What happens to the removed party?

 I would do this when the call* was being deleted.

Anyone got any comments on the best approach?

both parties and calls are dynamic (they appear and disappear
on timescales shorter than the program's) so they need to be handled
in a dynamic fashion. If you don't want new and delete you need
to manage a pool yourself. Somehow.

 

[Guest]

Because calls (and parties) are entity objects, and have
explicit lifetimes which have nothing to do with containers (or
pointers) used for navigation, and you can't use containers of
the objects, because they don't support copy.  This is a
classical example of a case where he needs raw pointers; smart
pointers just lead to more complicated code.

This is refreshing to hear. Maybe my own telecommunication's
background predjudices me...

 

[Alf P. Steinbach]

* James Kanze:

* James Kanze:

* 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

 

[James Kanze]

* James Kanze:

* James Kanze:
* 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]

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?)

 

[Alf P. Steinbach]

* 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

 

[James Kanze]

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]

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.

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.

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.

[...]

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.

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.

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.

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.

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.

 

[hanukas]

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.