Linked List Isn't Working Correctly

Discussion in 'C++' started by darrell.blake@gmail.com, Dec 9, 2005.

  1. Guest

    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?
     
    , Dec 9, 2005
    #1
    1. Advertising

  2. mlimber Guest

    wrote:
    > 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
     
    mlimber, Dec 9, 2005
    #2
    1. Advertising

  3. Peter Most Guest

    wrote:

    > 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
     
    Peter Most, Dec 9, 2005
    #3
  4. Howard Guest

    <> wrote in message
    news:...
    > 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
     
    Howard, Dec 9, 2005
    #4
  5. Guest

    > 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.
     
    , Dec 9, 2005
    #5
  6. mlimber Guest

    wrote:
    > 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
     
    mlimber, Dec 9, 2005
    #6
  7. Peter Most Guest

    wrote:

    >> 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.

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

    -- Peter
     
    Peter Most, Dec 9, 2005
    #7
  8. Default User Guest

    wrote:


    > 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
     
    Default User, Dec 9, 2005
    #8
  9. Guest

    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.
     
    , Dec 9, 2005
    #9
  10. wrote:
    > 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
     
    Thomas Tutone, Dec 9, 2005
    #10
  11. Puppet_Sock Guest

    wrote:
    > 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
     
    Puppet_Sock, Dec 9, 2005
    #11
  12. Brian Lawson Guest

    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.
     
    Brian Lawson, Dec 10, 2005
    #12
  13. Guest

    >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.
     
    , Dec 10, 2005
    #13
  14. peter koch Guest

    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
     
    peter koch, Dec 10, 2005
    #14
  15. Brian Lawson Guest

    >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.
     
    Brian Lawson, Dec 10, 2005
    #15
  16. Guest

    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...
     
    , Dec 11, 2005
    #16
  17. Brian Lawson Guest

    >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.
     
    Brian Lawson, Dec 11, 2005
    #17
  18. Puppet_Sock Guest

    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
     
    Puppet_Sock, Dec 12, 2005
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    491
    emerth
    Jul 10, 2003
  2. interpim

    Why isn't this working correctly?

    interpim, Dec 17, 2003, in forum: C Programming
    Replies:
    29
    Views:
    753
    Mark McIntyre
    Dec 17, 2003
  3. fool
    Replies:
    14
    Views:
    523
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    682
    John Carson
    Oct 2, 2006
  5. Mufasa
    Replies:
    6
    Views:
    465
    Juan T. Llibre
    Jun 9, 2008
Loading...

Share This Page