[haeffin]

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.

[panic]

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.

[barrkel]

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;
    };

With the STL implementation, only one list can have the item inlined; all the other linked lists need two indirections to get to the next element.