Linked List Isn't Working Correctly

[darrell.blake]

I've just written a doubly linked list but when I tell the iterator to
move forward in the list it removes all the previous elements in the
list. i.e. If I were to do:

List list;

list.AddAtEnd(20);
list.AddAtEnd(30);
list.AddAtEnd(40);
list.AddAtBeginning(10);

Iterator iterator = list.GetIterator();
iterator.MoveToStart();
iterator.MoveForward();

I would expect to still get an output of 10, 20, 30, 40 when I cycle
through the list but it only outputs 20, 30 40. Similarly, if I were to
call MoveForward() one more time it would only output 30, 40.

Because of the size of the files I wont post the code here but I have
provided URLs to my LinkedList classes below:

http://www.dunmanifestin.co.uk/LinkedList.cpp
http://www.dunmanifestin.co.uk/LinkedList.h

I would be really grateful if someone could have a look at my files and
try and figure out what I'm doing wrong.

Thanks,

Darrell

p.s. The operator overloader that I've put in I can only seem to get to
work if I put everything in the header file. Is it possible to split it
up between the header and the source like all the other member
functions?

 

[mlimber]

I've just written a doubly linked list

Why? As the FAQ recommends
(http://www.parashift.com/c++-faq-lite/containers.html#faq-34.5)
regarding containers: "don't roll your own from scratch unless there is
a compelling reason to do so [e.g., if it's for homework or your own
edification]".

but when I tell the iterator to
move forward in the list it removes all the previous elements in the
list.

[snip]

I don't see anything obviously wrong with it. Have you stepped through
it in your debugger?

Cheers! --M

 

[Peter Most]

I've just written a doubly linked list but when I tell the iterator to
move forward in the list it removes all the previous elements in the
list. i.e. If I were to do:

List list;

list.AddAtEnd(20);
list.AddAtEnd(30);
list.AddAtEnd(40);
list.AddAtBeginning(10);

Iterator iterator = list.GetIterator();
iterator.MoveToStart();
iterator.MoveForward();

I would expect to still get an output of 10, 20, 30, 40 when I cycle
through the list but it only outputs 20, 30 40. Similarly, if I were to
call MoveForward() one more time it would only output 30, 40.

Because of the size of the files I wont post the code here but I have
provided URLs to my LinkedList classes below:

http://www.dunmanifestin.co.uk/LinkedList.cpp
http://www.dunmanifestin.co.uk/LinkedList.h

I would be really grateful if someone could have a look at my files and
try and figure out what I'm doing wrong.

Thanks,

Darrell

p.s. The operator overloader that I've put in I can only seem to get to
work if I put everything in the header file. Is it possible to split it
up between the header and the source like all the other member
functions?

Do you have a good reason not to use the std::list class?

Kind regards Peter

 

[Howard]

I've just written a doubly linked list but when I tell the iterator to
move forward in the list it removes all the previous elements in the
list. i.e. If I were to do:

List list;

list.AddAtEnd(20);
list.AddAtEnd(30);
list.AddAtEnd(40);
list.AddAtBeginning(10);

Iterator iterator = list.GetIterator();
iterator.MoveToStart();
iterator.MoveForward();

I would expect to still get an output of 10, 20, 30, 40 when I cycle
through the list but it only outputs 20, 30 40. Similarly, if I were to
call MoveForward() one more time it would only output 30, 40.

What do you mean by "cycle through the list"? Perhaps you're just starting
at the "current" position, which is incremented by the MoveForward call?
(In your listing, I don't see the code that's making the calls shown above,
and I don't see any code to cycle through the list here, but I'd suspect
that's the case.) Use your debugger, and it will tell you _exactly_ what
it's doing.

-Howard

 

[darrell.blake]

Perhaps you're just starting
at the "current" position, which is incremented by the MoveForward
call?

Bingo. Thanks, you've sorted out my problem.

As for the std::list class. I didn't realise there was one. I'm writing
a particle system for my final year dissertation at University and I
figured linked lists would be the best way to store the particles. If
there's any better way I'd be glad to accept any suggestions? I'll
certainly take a look at std::list. I don't want to use any STL stuff
though.

 

[mlimber]

As for the std::list class. I didn't realise there was one. I'm writing
a particle system for my final year dissertation at University and I
figured linked lists would be the best way to store the particles. If
there's any better way I'd be glad to accept any suggestions? I'll
certainly take a look at std::list. I don't want to use any STL stuff
though.

std::list is part of the STL, but why not use a tried and true linked
list instead of your own (see the FAQ I previously cited)? You can use
std::list without using all of the STL if you dislike parts of it
(e.g., the strange syntax for some algorithms).

Cheers! --M

 

[Peter Most]

at the "current" position, which is incremented by the MoveForward
call?

Bingo. Thanks, you've sorted out my problem.

As for the std::list class. I didn't realise there was one. I'm writing
a particle system for my final year dissertation at University and I
figured linked lists would be the best way to store the particles. If
there's any better way I'd be glad to accept any suggestions? I'll
certainly take a look at std::list. I don't want to use any STL stuff
though.

Any particular reason? It's free and probably pretty bug free ;-)

-- Peter

 

[Default User]

As for the std::list class. I didn't realise there was one. I'm
writing a particle system for my final year dissertation at
University and I figured linked lists would be the best way to store
the particles. If there's any better way I'd be glad to accept any
suggestions? I'll certainly take a look at std::list. I don't want to
use any STL stuff though.

Why don't you want to use the standard library containers? There are
very few good reasons for that decision. More likely you are
misinformed about some aspects of the standard library.


Brian

 

[darrell.blake]

I don't particularly want to use STL because I know various people who
work in the games idustry (a few of whom are lead developers) and none
of them recommend STL because of speed issues. I have to admit, I have
no opinion of my own about such things because I haven't encoutered
them yet but, obviously, I respect their opinion.

I'm going to have a word with a couple of lecturers at my University
who specialise in games development and see what they recommend. At the
end of the day, I'm more bothered about correct code than speed at this
moment in time because it's only for my dissertation.

 

[Thomas Tutone]

I don't particularly want to use STL because I know various people who
work in the games idustry (a few of whom are lead developers) and none
of them recommend STL because of speed issues. I have to admit, I have
no opinion of my own about such things because I haven't encoutered
them yet but, obviously, I respect their opinion.

For something like a linked list, I find it difficult to believe you
could write code that was materially faster than the standard library's
linked list. A more credible criticism is that using some standard
library features causes code bloat, but that's just a quality of
implementation issue.

I'm going to have a word with a couple of lecturers at my University
who specialise in games development and see what they recommend. At the
end of the day, I'm more bothered about correct code than speed at this
moment in time because it's only for my dissertation.

As you should be. The correct thing to do is use the standard
library's features and, if speed of execution truly is an issue,
profile your code and find out where the bottleneck is. I bet it's not
in the standard library's linked list implementation.

Best regards,

Tom

 

[Puppet_Sock]

I don't particularly want to use STL because I know various people who
work in the games idustry (a few of whom are lead developers) and none
of them recommend STL because of speed issues.

[snip]

Whenever anybody raises "speed issues" you have to stop and
ask, who did the measurements? And under what conditions?
And does the "faster" software really do the same job?

The STL has some overhead for some things. If you "roll your
own" you can remove that. Maybe. If you spend a lot of time
and effort doing it. And documenting it if you are in a group
development situation. And integrating it with the rest of the
project. And teaching the other developers how to use it.
And convincing them that *their* roll-yer-own version isn't
better than yours.

Or, you could wind up with something that's buggy, and runs
maybe 5 percent faster in a few situations, is not noticably
different in most situations, and actually runs massively
slower in some situations. And takes something like three
to five times as long to implement as the STL code would.

You mentioned a project for your senior year. I'm thinking
that anything that will speed your development effort will
be of interest to you.

The STL has performance promises. It has a standard, well
documented interface. There are many tutorials on how to
use it safely, efficiently, and understandably. It's standard
with modern compilers. It handles plenty of things you may
not think of when you are first throwing together your app.
It has hooks to do many more. And it has properly thought
out plans and warnings for tricky parts of many others.
Just as one example: The STL containers have had a lot
of thought put into them regarding such things as const
correctness and related issues.
Socks

 

[Brian Lawson]

I find this reply interesting and a bit amusing. As a lead graphics
programmer in the "industry" I can assure you that if you're storing
your particles in a list to begin with, you've got more to be concerned
about than whether your "home brewed" list implementation is faster
than STL's.

For now, I wouldn't be too concerned about STL. From my experience,
most people who complain about it, are usually mis-informed about it.
If you want a decent read about game development in general, which also
happens to discuss use of STL in game code, I highly recommend "C++ For
Game Programmers" by Noel LLopis.

 

[darrell.blake]

if you're storing your particles in a list to begin with,

you've got more to be concerned about than whether
your "home brewed" list implementation is faster than STL's.

What data structure would you suggest I use then? From my research so
far (and I've read quite a few theses, books and articles) every one of
them has recommended linked lists.

 

[peter koch]

(e-mail address removed) skrev:

I don't particularly want to use STL because I know various people who
work in the games idustry (a few of whom are lead developers) and none
of them recommend STL because of speed issues. I have to admit, I have
no opinion of my own about such things because I haven't encoutered
them yet but, obviously, I respect their opinion

This is not correct. I have read articles by game-developers (and
certainly not "nodbodys) recommending the opposite - namely to prefer
the standard library (what you call "STL") instead of rolling your own.
Google Pete Isensee for one such example. You should find valuable
information there (if only i remember his name correctly). An open
question is if you want to use a list. Lists are bad if you consider
how well the cpu's caches are used.

I'm going to have a word with a couple of lecturers at my University
who specialise in games development and see what they recommend. At the
end of the day, I'm more bothered about correct code than speed at this
moment in time because it's only for my dissertation.

I agree with you here, certainly.

/Peter

 

[Brian Lawson]

What data structure would you suggest I use then? From my research so

far (and I've read quite a few theses, books and articles) every one of
them has recommended linked lists.

Storing your particle data in a linked list is bad for two reason that
I can think of immediately off the top of my head. The first is the
one reason that Peter Koch mentioned...which is the lack of cache
coherency. The second reason, is that as particles come and go from a
system, and you insert and remove them from the list you're having
dynamically allocate memory off the heap to get the new node that your
newly spawned particle is going to be stored in. That ties back into
the first reason, in that dynamically allocating off the heap like that
at runtime almost guarentees that your particles will not be stored in
side-by-side memory blocks. Maybe you can see where this is going...

The best way to store particle data is without a doubt in a contiguous
block of memory. There's no reason that you can't precompute the
maximum number of particles that your system will need and then block
allocate enough memory to hold all of those particles. You might argue
that that would result in slightly wasted space since the system may or
may not always be running at peak throughput. However, it's all about
trade-offs when it comes to performance programming. I'll gladly
sacrifice a little bit of worst case unused space to ensure that when I
need to blast through my particle data for the update, I'm assured that
when I go from one particle to the next, the next particle's data is
already sitting in my CPU's cache because of the way I chose to lay out
my data/memory...rather than incurring the CPU stall while the required
data gets fetched and loaded into the CPU's cache. Make sense? When
you're trying to run 10s of thousands of particles in a scene that also
has a million other graphical things going on as well, you'll quikcly
realize that storing particle data in a linked list is definitely not
the way to go. Hopefully that helped clear some things up.

 

[darrell.blake]

So are you suggesting I use arrays?

I have to say; although what you're saying makes pefect sense, I find
it a little disconcerting that none of the articles I've read on
particle systems recommend arrays...

 

[Brian Lawson]

So are you suggesting I use arrays?

I have to say; although what you're saying makes pefect sense, I find
it a little disconcerting that none of the articles I've read on
particle systems recommend arrays...

Absolutely. An array of contiguously allocated memory. i.e. one call
to new Particle[ nNumParticles ];

I too found it a bit strange, back when I was learning/reading all that
I could possibly get my hands on...that every example I ever saw of a
particle system, stored the particles in a linked list. I've come to
the conclusion that a lot of the material that's available for purchase
or even on the net, is written by amatures. Or, in the event that the
book/article is clearly NOT written by an amature, then I must assume
that the linked list representation was used merely for keeping the
demonstration/example easy to use/peruse as a learning tool.

 

[Puppet_Sock]

Re: Array vs. linked list. (Disregarding whether to use the standard
library or not.)

To make this decision you need more information.

For example: If you need to do indexed accessing of the data,
as "get me the 125th particle" then a linked list may be a poor
choice. A linked list might mean you had to step through the
list to find the 125th particle, where an array would mean you
simply accessed particles[index] and gave index the right value.

There are several other considerations. As for example, do
you need to sort the elements? Or do you need them in some
particular order? Are the elements large and stored in place
in the container? Or are you storing only pointers to the
elements? Or are the elements quite small? Do you need
to do a lot of insertion and deletion in the middle of the
collection? What kinds of operations do you want to do to
the collection as a whole? And quite a few other questions.

If you get a good tutorial on the standard library, it should have
a section on how to choose the right container.
Socks