[gsg]

You forgot insertion and removal, which intrusive lists provide in constant time and vectors do not.

If you can own the objects, linked list (of any kind) is usually not appropriate. The essence of the efficiency of an intrusive linked list is that the same indirection that must point at an object that is not owned is reused to give the list structure. Without this trick, linked lists are not much good.

[phaedrus]

Again, you're not getting the point. Constant time != "fast", it just has to do with how the operation scales with N. The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.

[cygx]

> The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.

Citation needed. The kernel guys in particular would probably be interested in a faster alternative to intrusive linked lists.

Keep in mind that we're talking about vectors of pointers due to the problem domain (multiple lists of potentially large or polymorphic objects), so using vectors won't really help locality.

[gsg]

Given a pointer to an object, remove from an intrusive list is three memory accesses: only tiny vectors will give faster operations than that.

Insertion favors intrusive lists even more: allocation and copy free!