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?
There may be such a time, but I 've never heard of such a case.
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?
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.
Originally Posted by clegs
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.
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.
>> 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).
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.
Originally Posted by Daved
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!!!