[Uchuujinsan]

Very interesting video about the internal workings and optimizations of the hardware and the compiler, and how it does affect programming in c++/c#/java

http://www.nwcpp.org/Meetings/2007/09.html

Direct link to video:
http://video.google.com/videoplay?docid=-4714369049736584770#

Direct link to the slides:
http://www.nwcpp.org/Downloads/2007/Machine_Architecture_-_NWCPP.pdf

[Bobboau]

very interesting.

never ever ever use anything other than a vector.

[portej05]

very interesting.

never ever ever use anything other than a vector.

whoa there. There are damn good reasons for the existence of other structures.
Just try an algorithm that requires a heck of a lot of non-head or tail insertions.

[Bobboau]

I was being overly simplistic.

[portej05]

*phew*

[Bobboau]

but that does reinforce my existing bias flavouring vectors as a first choice.

[blackhole]

This confirms my instinct of "it's not fast until you test it."

However I want to point out that lists are often significantly faster then vectors for completely different reasons (as well as having O(1) time for insertion and deletion).

[portej05]

Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though

[Aardwolf]

Well yeah, but what's so special about element 10?

That is, while a list can't do the whole random access thing, you don't necessarily need random access anyway. So it may not matter.

[Sushi]

There's also the fact that most of the time, optimizing the way your data is cached to get a speed increase isn't usually super-high priority.

But it is nice to know about cache locality issues so when you *do* for some reason need to be really clever, you can.

[blackhole]

Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though

Actually if you're trying to access list element 10 then you should probably be using a vector. In all of my lists, I only ever need to access all of the elements in order, or the element I need to access has a pointer in some other object.

[Aardwolf]

Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though

Actually if you're trying to access list element 10 then you should probably be using a vector. In all of my lists, I only ever need to access all of the elements in order, or the element I need to access has a pointer in some other object.

I believe that was implied by what he said.