Example: Any object shared among multiple lists or other data structures at the same time, or directly pointed to by other objects, such that any of those views must reach the same cheaply mutable state. This includes objects in the object-oriented programing (OOP) model, actors in the actor model, and file objects in a kernel which are in multiple lists.
For those you have to store object pointers in the vector, instead of copies of the objects. That works and is often done, but it defeats or reduces the cache locality perfornance improvement which motivates using a vector in the first place.
On an in-order CPU an intrusive list (pointers inside the objects) can be traversed faster than a vector or B-tree of object pointers, though a non-intrusive list (list of nodes containing object pointers) won't be faster. On an out-order CPU with heavy speculative execution it is less clear cut because the vector allows successive objects to be dereferenced speculatively in parallel to a limited extent, while this is not possible traversing an intrusive list.
If the list is going to be traversed looking for objects based on some filter criterion such as flags or a number comparison, based on non-mutable state (or where it's ok for mutation to be expensive), traversal can be sped up by storing criterion data in the vector alongside the pointers, or in a second vector, to avoid dereferencing every touched object pointer during traversal.
Linked list are indeed great for secondary traversal orders (or for subsets).
But I don't understand your comments re in-order CPUs: vectors will be faster there too as they avoid the load-load dependency. Most modern inorder CPUs are still superscalar and fully pipelined.
If the data is relatively big buffers, you really do not want to copy them. Your memory bandwidth will thank you, and performance will vastly increase.
Cache locality will be good anyway since you're referring to long blocks.
This kind of data structure often has a buffer + associated metadata. If the metadata+pointer fits into 1-2 cache lines, storing it in a vector can give be win vs. storing the next/prev pointers next to data + metadata.
In any case, there is always only one authoritative answer: “perf top”. :)
