> 1: you care about ordering - often you don't care about ordering and in that case, there is no need for a linked list because you can achieve O(1) insertion & removal then too: insertion can always be at the end, removal can be a "swap with end element, remove end element" operation.
Whether you care about ordering or not, linked lists work great. Adding to an array is only amortized O(1). It is worst-case O(N). Why pay O(N) for the worst case when you can pay a cheap O(1) always?
> 2: inserting and/or removing from the middle of the list is a common operation, if it is not a common operation, then the added cost of doing so with a vector may still be outweighed by a vectors other advantages
Deleting from the middle of the list is an extremely common requirement, when you have objects that need to be enumerable in some order[s] and sometimes deleted.
> 3: you do not require random access - lists do not provide random access and lookup is O(n). At the expense of additional complexity in implementation and more memory overhead, you could reduce lookup to, OTOH, O(log n) by using a skip-list
Here is a false dichotomy dictated by the STL. With intrusive lists, you can have both your vector and lists of various orders. There is no contradiction.
When you need indexing, use a vector. When you need quick add/remove, use lists. When you need both, use both.
> 4: you do not iterate through the list often - if you do, you are likely going to blow the cache and mess up prefetching due to poor cache locality. Iterating through an array-based data structure can be much faster in this case.
Yes, if you want quick (repeated) enumeration, put it in a vector. Again, this doesn't contradict also putting it in lists.
> The biggest issue they seemed to mention, though, was cache locality - I fail to see how intrusive linked lists solve this.
Cache locality is based on your use pattern. When enumeration isn't your common operation, vectors don't have better locality than lists. For example, a sorted list of requests where you may want to time out the oldest one will only refer to the head and tail of the whole list. Cache locality is great.
> then you end up jumping around the preallocated nodes anyway and after a while will lose any cache-friendliness you may have had.
You don't need to jump around. Say you have a request object you found via a hash table. After handling it you decide to destroy it. You now want to delete it from various lists it is in. You can do it on all lists in O(1) for each list. This is relatively cache-local (only need 2 extra random accesses, potential misses, for each list).
> C programmers are trained to use linked lists. They are the first variable-length containers most programmers come into contact with and so C programmers tend to be imprinted on them like ducklings. Linked lists are a poor general purpose container.
I think the false premise here, espoused by the STL, is that a data structure is a "container" at all. Your data can be "contained" by anything (the stack, the heap, a vector, ...). The data structures involved (linked lists, hash tables, search trees) all do not contain the data. They organize the data.
When using vectors as containers STL-style -- you cannot really have your data organized by multiple data structures efficiently.
I regularly have my data objects within a hash table, a list, and a search tree simultaneously and efficiently, with no dynamic allocation to sustain any of that.
STL cannot do this because of the data-structure as "container" philosophy.
EDIT: Also read my other comment detailing why std::list is lacking the most fundamental properties expected of a linked list: https://news.ycombinator.com/item?id=6830526