Earlier quoted context omitted.
> Why doesn’t every language give me a batteries-included digraph ADT? I think such a type would be less useful than you'd think, for precisely the same reason why a linked list in the stdlib is pretty much useless: almost always, you don't want the stdlib allocating nodes; you want an intrusive data structure instead. Really, the problem is that the compiler needs to store extra data with the nodes that the stdlib c…
> you don't want the stdlib allocating nodes; you want an intrusive data structure instead. Don't C++'s std::list and Rust's std::collections::LinkedList effectively implement the moral equivalent (insofar as memory layout is concerned) of an intrusive list, though?
You can't call `std::list::erase()` with a Node* , and you can't write a function that converts from Node* to `std::list::iterator` in standard C++, even though it's really just a matter of subtracting a fixed number of bytes from the pointer value. So you instead need to store the `std::list::iterator` in the `Node`, wasting memory.
You can kind of cheat by always using `std::list::iterator` instead of Node* , but that means you can't use normal methods, because the `this` pointer will lack access to the iterator. And you always need to pass around a pair of `std::list&` and iterator, because the iterator alone isn't sufficient to delete the node or insert elements before/after it. Usually the code ends up being a lot simpler if class Node just reimplements a linked list.
And that's still the simple case where each node is only contained in a single data structure at a time, which (at least in compilers) is rarely sufficient.