[pdpi]

> 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?

[ynik]

Yes, but they hide the memory layout as an implementation detail, thus negating most advantages of an intrusive list.

You can't call `std::list<Node>::erase()` with a Node* , and you can't write a function that converts from Node* to `std::list<Node>::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<Node>::iterator` in the `Node`, wasting memory.

You can kind of cheat by always using `std::list<Node>::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.

[taejo]

There's boost::intrusive::list which IME actually works quite well. There is a node type which elements derive from or contain, so you can get an iterator from an element, as well as the other way round. To include an element in multiple lists, just aggregate the node type multiple times.

[gpderetta]

Boost.Intrusive is beyond awesome. You can add nodes not only to multiple lists, but also to maps, set, hash_maps to build multi-indexed data structures (and with delete hooks all indices can be kept consistent).