3 ms·
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 u
by gsg 14y ago
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 14y agoAgain, 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 14y ago> 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 14y agoGiven 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!