arrays vs lists? And containers in general!

This is a discussion on arrays vs lists? And containers in general! within the C++ Programming forums, part of the General Programming Boards category; A question I have after reading and meticulously copying each block into a word document for reference. Is there a ...

  1. #16
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    A question I have after reading and meticulously copying each block into a word document for reference. Is there a time, meaning occasionally or better, where it is effective to use one container for its strong performance in certain areas, and then copy into another container for its strong performance characteristics? Or is that avoided at all costs because it's too expensive?

  2. #17
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    There may be such a time, but I 've never heard of such a case.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    When picking a data structure the first question you ask yourself should always be: Is there any reason I can't simply use an array or vector?
    The second question is then: Are you sure your answer to the first question is correct?


    Now, in your first post you mentioned a number of data structures. You mentioned lists, and linked-lists as two seperate container types. If you believe this to be the case, what would be the difference between them? Or are they in fact really just synonyms?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Quote Originally Posted by clegs View Post
    A question I have after reading and meticulously copying each block into a word document for reference. Is there a time, meaning occasionally or better, where it is effective to use one container for its strong performance in certain areas, and then copy into another container for its strong performance characteristics? Or is that avoided at all costs because it's too expensive?
    Never say never. However it only makes sense to do such a thing when circumstances change significantly. For example when the number of items goes from being around 10 to being around 1 million. Or when you go from rapidly inserting and removing items without iterating through them, to when you need to iterate over all items in order frequently without performing many inserts or removals any more.

    In practice it is very rare because to do it you have to have code for both containers, as well as code that detects when the circumstances change significantly. Even then you can't just guess that circumstances have changed, you have to know that circumstances really have changed and are going to stay that way for a while.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    what about the
    1. always use std::vector by default (to maximize cache-hits)
    if it's to slow:
    2. profile and compare with other containers (chosen by complexity consideration)

    CornedBee posted it once and I made a habit of it.

  6. #21
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> THANK YOU SO MUCH DAVED!
    Your welcome. I'm no expert on this stuff, and it's good for me to go over the pros and cons of different solutions rather than get stuck using the same thing over and over without remembering why. Plus I had a bunch of time to kill.

    >> Is there a time, meaning occasionally or better, where it is effective to use one container for
    >> its strong performance in certain areas, and then copy into another container for its strong
    >> performance characteristics?
    You mean like maybe using a vector to sort the objects then transferring to a list to delete them? It's possible, but in many cases I think there will be an even better option out there.

    >> what about the always use std::vector by default
    In practice, absolutely. However, when actually learning about the different data structures you want to dive a little deeper than that.

    Basically, you want to choose the right to tool for the job so that things are clear to anybody looking at or maintaining your code what is going on. If two options are equally clear, then you want to start with the one that theoretically would give the best performance. That means going through a thought process like the one I presented earlier.

    However, the point of the "always use vector" advice is that if you did go through that thought process, you'd find that vector wins most of the time. This example is probably one of the few where it doesn't (and in practice it is possible it would win). So it's not that you shouldn't think about what's the best option, it's that you should know that vector usually is for several reasons (including the cache-hits thing).

  7. #22
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Daved View Post
    Basically, you want to choose the right to tool for the job so that things are clear to anybody looking at or maintaining your code what is going on. If two options are equally clear, then you want to start with the one that theoretically would give the best performance. That means going through a thought process like the one I presented earlier.
    Also, once you HAVE choosen your vector, list, heap, map or whatever it may be, document WHY you choose that. This is regardless of wheter you choose it because "you couldn't be bothered to think out which is the best choice" or you made a deep analyzis of the exact pro's and con's, performance benchmarks and measurements on 12 different combinations of processor and OS's. This could be in a separate document or as a short comment in the code. But it's always good to understand the decision and the thoughts behind it, both if it was hard thought out, or just lazily choose the first matching solution. Because you or some of your collegues may later on decide that it's time to change the code, and in the process perhaps need to look at the choice again.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #23
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    This thread has been great!

    I really appreciate all the posts and hope they keep coming. I feel the classes I have taken so far, and I have just 8 left before I earn my degree, have been lacking in this kind of education. But, maybe it can't be until you get into a work environment. It would be nice to have some kind of class that mimics the work environment where you have to actually apply what you've learned, though.

    As far as documenting what you have done and why - that is a given! For me anyway. I have worked in finance for 25 years (accounting, not programming) and I have developed a 'habbit' of documenting the beegeebers out of everything I do, how I came up with the figures, what other methods I used and discarded with a why, and why I made specific adjustments and where the offset is and why. In the beginning, there were many times I went back to what I did and didn't have a clue why or how. No any more! And, I have carried that habbit into other things as well - my code included. But it is a great to have a reminder to DO IT!!!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Noob STL question about Containers.
    By Swerve in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2009, 12:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21