grandempire 6 days ago

I see. I am noticing the main difference is that forward_list manages the lifetime and allocation of nodes and that having a pointer to an object is equivalent to a pointer to the node (could be implemented as a helper).

The layouts look the same?

1
_huayra_ 6 days ago

At the byte level, it's quite possible the layouts are the same. However, an "intrusive data structure" means that the nodes themselves are the data.

In other words, intrusive is like this:

struct T : NodeType<T> { // T data NodeType<T> next, prev; };

whereas non-intrusive data structures the T's are not the nodes themselves

struct NodeType<T> { NodeType<T> next, prev; T t; };

Doing non-intrusive means you need to own the lifecycle of the nodes (and make them copyable, move-constructible, or some combo thereof). Intrusive means that the caller can manage the nodes' lifecycles and just say "here's a node, I promise it'll live while the list is still alive" and have that node be on the stack, heap, static, etc.