I''m curious about a point on linked lists. Back in C and ASM, I used to write the next/prev pointers right into the data structure itself. Using C++, the nature of the language and encapsulation frowns on this, so I''ve been creating a seperate NodeStruc { Node *data; NodeStruc *next; NodeStruc *prev; } structure that is the actual component of my linked list. However, this introduces list overhead, and complicates some simple things. What''s the verdict? Use C-style integrated linked lists, or have a seperate list template that, for each node in the list, simply has a pointer to the real data? And finally, if you use a seperate list template, how best to handle traversing through the list? The STL uses iterators, but I''ve been warned away from the STL list for efficiency reasons and overhead. For non-essential stuff it doesn''t matter, but, for example, in my particle system I have hundreds of particles active at once, and a small overhead will show up in memory and efficiency. - Remnant
- (Steve Schmitt)

You missed an option: declare a node class and then inherit from it. i.e.
class Node {
Node * next;
Node * prev;
}

class Particle : Node {
int blah;
}

That elminates most of your overhead (double indirection and additional space). At the same time you can use Node functions on your specific data types.

It''s still not the best C++ code, but if the overhead of a template method concerns you, it''s probably your best bet.

hmm, interesting, I hadn''t thought of that. Do you know what kind of overhead is involved in multiple inheritance? That''s something I''ve been thinking of using (for other purposes as well), but I haven''t read much about its real-world efficiency as compared to regular single inheritance.


- Remnant
- (Steve Schmitt)

Hellu.
I consider a linked list as an object itself. Therefor I like to create a Class for a linked list. However the objects which is contained in the list have no knowledge that they are in a linked list. The psuedo for this is:

class CElement
{
CElement* next;
CType* item;
}

class CLinkedList
{
CType* operator[](int index); // Gives the list a look of an array
void AddObj(CType& obj); // Adds an object to the list
CType* RemoveObj(int index); //Removes and returns the object on index
}

This approach could be used both as a template or through inheritance, having a generic class in your project CObject or something and inherit everything from that.
There may be better ways to do this, but this is the way i usually do it.

/Greetings Derwiath

Multiple inheritance has very little runtime overhead as long as your classes are well-formed. As for the qualification of well-formed, as long as you, the programmer, know pretty much unambigously which class a variable or methdod is inherited from, it probably won''t have too big a runtime overhead.
At compile time, it''s amazing how much only a few multiple inherited classes can slow up things.

The only concern you might have with STL is code size. As for performance, STL is AFAIK better than good. The two problems I have with templates are:

1) Terrible error messages
2) Terrible syntax

Beyond that, the concept is beautiful.

(IOW: Terrible implementation of a great idea)

/Niels

Another thing: For particles you could use a fixed size array. Allocate room for, say 200 particles. When particle 201 is added, overwrite the oldest. This is how I implemented it and it is VERY fast, and nobody notices if a few out of several hundred particles dissapear prematurely.

The real overhead in linked lists is *NOT* in the presence or absence of a single pointer or encapsulation layer but in memory management.

/Niels

Edited by - Niels on 1/14/00 7:19:59 AM

Note on Niels array concept:
If you use a static array, you *must* have an array of objects not an array of object pointers. Otherwise you have the same non-locality and heap-fragmentation issues as using a C style linked list.
i.e.
good :
Particle particle_list[200];
bad :
Particle * particle_list[200];

btw, What''s IOW mean?

I''m guessing In Other Words
Took awhile to figure out tho *grins*


-ns-