I was recently listen to a talk that Jonathan Blow gave, you can find it here. In the talk, he was talking about what data structures he (and he seemed to imply many others) use, and why. Which is to say that he simply used arrays to store data, and use the naive approach to find data in it, meaning iterate through the array until you found what you wanted, assuming it wasn't in a performance critical place in the code. He gave the example of loading data from a wad file in doom, which while fast, still took that naive approach (at least according to the talk, I haven't looked at the source code since I have not a clue to where I should begin). The reason he gave for this was because while it may be slightly slower to do things the naive way, it's not much, and in many cases, not noticeable, so it's better to optomize how much work you can get done in your lifetime, than to make things a millisecond faster, again, assuming it's not in your physics engine or something like that.
All this seems well and good, except I have one question, why not linked lists rather than arrays? Sure, if you had to make your own linked list class, I would be on board, but in c++ anyway, assuming your using STL, you only need to declare the type as a list, rather than as a vector, and use iterators to loop over it, rather than looping an index.
The advantages of using a linked list though seem much greater, for example, if you can be guaranteed that nothing is going to be removed from it while your iterating, you don't need to have locks around it, because adding data doesn't have the possibility of moving everything (or is that a bad assumption). Also, in general, moving data is slow, although this could potentially be avoided if you know the size of your data by reserving the space.
Another advantage is when you do remove data, you just tell the list to remove it, and it just needs to change a few pointers, and call a destructor, which can be done pretty quickly. But to remove something from an array/vector, you have to either shift everything back one, or possibly add a flag saying that it has been deleted. (Or, another possibility if you don't care about the order of the data, is move the data at the end index, to the data in the now deleted position). Either way, this seems like it is a lot of extra, unneeded work, or potentially too slow.
I did take a look around and found this, which claimed that a lot of older developers didn't want to use STL because it wasn't mature enough. Also, older games AFAIK, used C rather than C++, which also doesn't have STL. And I could see a case there for using arrays rather than linked lists, because you would have to make your own (which while simple enough to do, could potentially lead to many more errors).
I also read that it's a bad idea to create iterators in Java (due to the garbage collector), but that idea seems moot in languages such as C++, where there isn't a garbage collector, and I would imagine that linked list iterators are pretty lightweight (admittedly probably not as lightweight as vector iterators though). Or is this also a bad assumption, and it's better/faster just to use an index in your loop, and increase that.