Re:Linked List Problems (2002) [pdf]
by panic on Saturday November 25, 2017 @04:00AM
(#15775123)
C++ folks tend to dislike linked lists because it's awkward to make C++ lists intrusive. The STL list containers store the pointers in a separate allocation from the object itself, so they're slower than they ought to be.
[ Parent
| on HN ]
Where did you get that? The STL implementations I know definitely don't. See https://github.com/llvm-mirror/libcxx/blob/master/include/li... for an example - __list_node_base contains the pointers, __list_node contains the object and derives from __list_node_base, so allocating the node with object and pointers is one allocation.
Yeah, that's true for values you're willing to allocate inline. The key advantage of intrusive linked lists is being able to add and remove normally allocated objects without having to construct separate list nodes. The STL does have splice(), but it's awkward -- you always have to keep the object in a list and refer to it using iterators instead of normal references.
A data structure with the linked list inline is the other way around, e.g.:
class Foo {
Foo *m_next;
Foo *m_next_mru;
Foo *m_next_sibling;
};