quote:
Why is this the wrong thing to do? Some directed points:
- code reuse (already mentioned)
- destructor mayhem
- potential memory overhead
- OO principles (e.g. relationship between Someclass, SomeclassNode and SomeclassList as opposed to the alternate solution of Someclass and a templated List and Node)
- dependencies (related to above)

And what reasons could the solution he gave be better? The only "benefit" listed is the ability to pass a node as an object, but on what metric is that a gain? Speed? Memory? Code maintainability?

Gotta get back to my project, I'll check back in later. Please, discuss among yourselves.

I usually code my own linked lists, out of habit I guess. I dont think using the STL gives that much of an advantage over not using it. I have to disagree with some of your points:

1. code reuse
okay you can have this one. very little code is getting reused however.

2. destructor mayhem
If you know a class is going to be inherited from, you make the destructor virtual. Programmer error here, can happen wether you use the STL or not.

3. potential memory overhead
If the memory requirements of pointers are your concern then you can use an array implementation. I wonder how the STL does it?

4. OO principals
I dont see where this comes in to play. I'm sure there are situations where you will want ObjectList to be an Object, that doesn't necessarily mean you should or shouldn't use the STL. That choice is an implementation issue and doesnt affect the design at all.

Now having said all that I cant really think of a reasing why NOT using the STL would be a better choice...




[edited by - Redemption on March 21, 2002 2:56:46 AM]

quote:Original post by Redemption
2. destructor mayhem
If you know a class is going to be inherited from, you make the destructor virtual. Programmer error here, can happen wether you use the STL or not.

Except that STL doesn''t use this inheritence hack, so it can''t happen using STL''s list.

What you fail to realize is that you may not be able to change the code. Let''s say I want to make a linked list of WAVEHDR, which I would want to do if I were writing a player using waveOutWrite. These are all WIN32 structures and functions. I can''t make WAVEHDR have a virtual destructor. Surely you must see that having to change a class or struct so that it can be put into a linked list is wrong. I don''t have to do that for arrays.

quote:
3. potential memory overhead
If the memory requirements of pointers are your concern then you can use an array implementation. I wonder how the STL does it?

You can''t use an array, these are fundamentally different types. I suggest your research linked lists.

The overhead I was talking about was not for the next/prev pointers in linked lists--those are part of the inherent overhead. I was referring to the extra vtable pointer, which increases the per-node overhead by 50%. STL''s implementation doesn''t use inheritence, so its node not required to have a vtable pointer.

If you''re curious as to how STL works, the source code is on your computer. Look at the file "list." in your compiler''s include directory.

quote:
4. OO principals
I dont see where this comes in to play. I''m sure there are situations where you will want ObjectList to be an Object, that doesn''t necessarily mean you should or shouldn''t use the STL. That choice is an implementation issue and doesnt affect the design at all.

Having to modify an object so that it will fit into a list, having clients depend on the internal detail of your list so they can use it, that sort of thing.

quote:Original post by BeerNutts
That is the ultimate generic list, and (GASP), no C++!

Unfortunately, it doesn't fit any definition of "ultimate" that I'm familiar with. It is both the "old way" and it is inferior to the templated solution. Use of the void* for genericity both bypasses the type-safety system and pushes certain responsibilities onto the client (such as type discovery). Another issue is that your solution only offers reference semantics, and cannot provide the value semantics in a non-invasive manner. Genericity is low, commodity value is low.

Oh, and it's only half a linked-list, if that. Where's its interface?

[edited by - SabreMan on March 21, 2002 3:18:23 PM]

Stoffel -- it''s the job of the programmer not to do stupid things like using a non virtual destructor when utilizing polymorphism. If someone is dumb enough to do the things that you mentioned above, then I think that you should hire a new "junior member."
Concerning the extra memory needed for the vtable, I''ll grant you that. If you are really pinching for memory then use a simple linkedlist or the STL list. However, you are really overestimating how much extra space that is. Considering you have less than 4 gigs of memory, the space required for a pointer is only 4 bytes. If you had a linked list of 20,000 elements, that''s not even an extra 80k in memory. Considering you have 20,000 of this datatype in memory already, that small bit of memory is not much at all. Also, remember that since you are not using the STL, you have the freedom of customizing the implementation of the list. Beernutts was a bit simple with his example, but his point was very well made. Take a look back at it for a second and notice that he has a pointer to "next." A singly linked list -- no "previous." The STL implementation of a list is doubly linked, meaning that for every single node you have 2 pointers. In many cases, for instance, my original example of the vectors, a pointer to a previous element would never be used because you''d only be going forward through the list. In that case, the fact that you need a vtable pointer doesn''t affect it at all because while you''re adding one pointer, you''re getting rid of one that you aren''t using. No extra memory is required.

More than anything else, even if you don''t "agree" with my implementation, you should understand that the STL isn''t always the best way of doing things. Just because it''s neatly packed for you, ready to be used, doesn''t (or rather shouldn''t) mean much. It''s not efficient in every situation. For me, the added polymorphism for no extra cost is what makes me use my implementation so much. If you can''t see the benefits, then that''s fine, use the STL, just don''t be so quick to rely on already written code when you can make something more useful for the situation on your own.

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

quote:
Except that STL doesn''t use this inheritence hack, so it can''t happen using STL''s list.

What you fail to realize is that you may not be able to change the code. Let''s say I want to make a linked list of WAVEHDR, which I would want to do if I were writing a player using waveOutWrite. These are all WIN32 structures and functions. I can''t make WAVEHDR have a virtual destructor. Surely you must see that having to change a class or struct so that it can be put into a linked list is wrong. I don''t have to do that for arrays.

Since when are virtual destructors an "inheritance hack". I''ve always heard that that was the accepted way to safely inherit from a class.

You seem to be missing my point. The act of making a linked list a subclass of a class has nothing to do with the question of using the STL or not.

quote:

You can''t use an array, these are fundamentally different types. I suggest your research linked lists.

The overhead I was talking about was not for the next/prev pointers in linked lists--those are part of the inherent overhead. I was referring to the extra vtable pointer, which increases the per-node overhead by 50%. STL''s implementation doesn''t use inheritence, so its node not required to have a vtable pointer.

If you''re curious as to how STL works, the source code is on your computer. Look at the file "list." in your compiler''s include directory.

I cant use arrays? Time for you to bust out the old algorithms book. You can easily use 3 arrays and implement a list structure.

If you are worried about the cost of virtual functions then I again say that the act of making a list a subclass of a class has nothing to do with using the STL.

quote:

Having to modify an object so that it will fit into a list, having clients depend on the internal detail of your list so they can use it, that sort of thing.

You are making your next pointer private correct? You are making the std::list private correct?

quote:Original post by Matt Calabrese
Stoffel -- it''s the job of the programmer not to do stupid things like using a non virtual destructor when utilizing polymorphism. If someone is dumb enough to do the things that you mentioned above, then I think that you should hire a new "junior member."

It''s also the job of the programmer to ensure that the code utilises various known idioms so that the intent of the code is reasonably clear. Use of a non-virtual dtor means "do not publicly inherit me". I''d be interested to know what utility you think there is in inheriting a list whose interface is complete and minimal.

quote:
Also, remember that since you are not using the STL, you have the freedom of customizing the implementation of the list.

Whoa! The STL is designed from the ground up to be extensible. What customisations did you have in mind when you wrote this?

quote:
The STL implementation of a list is doubly linked, meaning that for every single node you have 2 pointers.

This is a reasonable concern, but one which is easily overcome. There is a historical reason that the Standard incarnation of the STL did not include a singly-linked list, but it is as good as guaranteed to make it into C++0x. There is also an implementation of slist available with SGI''s STL (and STLport) - there''s little to stop you using that.

quote:
More than anything else, even if you don''t "agree" with my implementation, you should understand that the STL isn''t always the best way of doing things. Just because it''s neatly packed for you, ready to be used, doesn''t (or rather shouldn''t) mean much.

Oh? Why not?

--
"Many people would sooner die than think. In fact they do."

quote:Original post by BeerNutts
Sabre, you and I will never agree, but that''s OK.

To be honest, I hadn''t specifically noticed we had disagreed very much. If it has been happening, it''s certainly unintentional on my part.

quote:
If you really want the interface, I''ll show it to you later, when I get home to my great respository of ultimate tools (yes, Sabre, ULTIMATE), I will pull out List.c, and you may see it.

I''ll look forward to it.

quote:Half a linked list huh? You should open your other eye then you''ll see the other half

What I mean is that a list is next to useless with no functions to manipulate it.

--
"Many people would sooner die than think. In fact they do."