将链表嵌入数据结构有什么好处？
What is the advantage of embedding a linked list into a data structure?
在阅读 FreeBSD 中的内核数据结构时，我偶然发现了 MBuf。 MBuf 包含指向 MBuf 链中下一个 MBuf 的指针，实现链表。每个 MBuf 本身还包含特定于链表中该节点的数据。
我更熟悉将容器类型与值类型分开的设计（考虑 std::list，或 System.Collections.Generic.LinkedList）。我正在努力理解将容器语义嵌入到数据类型中的价值主张——获得了哪些效率？真的只是为了消除节点实例指针存储吗？
what efficiencies are gained? Is it really all about eliminating the node instance pointer storage?
我会说更少的缓存未命中，然后更好的整体性能（即使链表通常不是缓存友好的数据结构）。
这样一来，您不必再遵循一个指针来在内存中的某处找到您的数据并将它们带到每个节点的处理器附近。
此外，如果您在连续的内存区域构建节点并使用几个指针管理它们（我们称它们为空闲列表和使用中列表，听起来很熟悉吗？），您可以在以下方面得到提升性能（至少只要列表不包含很多项目，否则风险就是在内存中来回跳转）。在这种情况下，In 和删除具有恒定时间（当然，除非您必须在列表中搜索节点才能插入特定位置），这是另一个优势。
假设您有一个 iterator/pointer 指向列表中的一个节点。为了获取数据，您必须：
- 从节点读取指向数据的指针
- 取消引用您刚刚读取的指针并读取实际数据
另一方面，如果列表概念是 "embedded" 在您的数据结构中，您可以在单个内存操作中读取您的对象，因为它与节点本身一起。
分离列表节点及其数据的另一个问题是列表节点本身很小（通常只有 2 或 3 个指针）。因此，在内存中保留如此小的结构的内存开销可能很重要。您知道——诸如 new 或 malloc 之类的操作实际上消耗的内存比它们分配的要多——系统使用它们自己的树结构来跟踪内存空闲和空闲的位置。
在这种情况下，将事情分组到单个分配操作中是有益的。您可以尝试将多个列表节点保持在小束中，或者您可以尝试将每个节点与其分配的数据连接起来。
侵入式指针（相对于共享指针）或将对象和智能指针数据打包在一起的std::make_shared可以看到类似的策略。
zett42 发表评论说 std::list<T> 将 T 与节点数据放在一起。正如我上面解释的那样，这实现了单个内存块，但有一个不同的问题：T 不能是多态的。如果你有一个 class A 及其导数 B，那么 node<B> 就不是 node<A> 的导数。如果您努力将 B 插入 std::list<A>，您的对象将：
- 在最好的情况下，导致编译错误（没有构造函数
A::A(const B&)）
- 在最坏的情况下，静默地slice
B 仅将代表A 的部分复制到节点中。
如果你想在单个列表中保存多态对象，一个典型的解决方案是实际使用 std::list<A*> 而不是 std::list<A>。但是你最终得到了我上面解释的额外间接。
另一种方法是创建一个侵入式列表（例如 boost::intrusive::list），其中节点信息实际上是 A 对象的一部分。那么每个节点都可以是A的导数没有问题。
侵入式链表的一大优点是您可以创建一个预先存在的对象列表，而无需任何新分配。要使用 std::list 个指针执行此操作将需要分配内存。
Boost 具有侵入式列表实现，并附有使用理由。 http://www.boost.org/doc/libs/1_63_0/doc/html/intrusive.html
侵入式列表的主要优点之一是您可以廉价地让单个节点属于多个列表。
例如，您可以将一组项目按 3 种不同的方式排序，对应于 3 个不同列表中的条目。例如，用 std::list 做起来会很笨拙。
正如@doron 所提到的，我认为的另一大优势是，一旦您自己创建了对象，列表管理就需要 0 次分配。
Boost 对 intrusive vs. non-intrusive data structures 进行了一些不错的讨论，有利有弊。
在阅读 FreeBSD 中的内核数据结构时，我偶然发现了 MBuf。 MBuf 包含指向 MBuf 链中下一个 MBuf 的指针，实现链表。每个 MBuf 本身还包含特定于链表中该节点的数据。
我更熟悉将容器类型与值类型分开的设计（考虑 std::list，或 System.Collections.Generic.LinkedList）。我正在努力理解将容器语义嵌入到数据类型中的价值主张——获得了哪些效率？真的只是为了消除节点实例指针存储吗？
what efficiencies are gained? Is it really all about eliminating the node instance pointer storage?
我会说更少的缓存未命中，然后更好的整体性能（即使链表通常不是缓存友好的数据结构）。
这样一来，您不必再遵循一个指针来在内存中的某处找到您的数据并将它们带到每个节点的处理器附近。
此外，如果您在连续的内存区域构建节点并使用几个指针管理它们（我们称它们为空闲列表和使用中列表，听起来很熟悉吗？），您可以在以下方面得到提升性能（至少只要列表不包含很多项目，否则风险就是在内存中来回跳转）。在这种情况下，In 和删除具有恒定时间（当然，除非您必须在列表中搜索节点才能插入特定位置），这是另一个优势。
假设您有一个 iterator/pointer 指向列表中的一个节点。为了获取数据，您必须：
- 从节点读取指向数据的指针
- 取消引用您刚刚读取的指针并读取实际数据
另一方面，如果列表概念是 "embedded" 在您的数据结构中，您可以在单个内存操作中读取您的对象，因为它与节点本身一起。
分离列表节点及其数据的另一个问题是列表节点本身很小（通常只有 2 或 3 个指针）。因此，在内存中保留如此小的结构的内存开销可能很重要。您知道——诸如 new 或 malloc 之类的操作实际上消耗的内存比它们分配的要多——系统使用它们自己的树结构来跟踪内存空闲和空闲的位置。
在这种情况下，将事情分组到单个分配操作中是有益的。您可以尝试将多个列表节点保持在小束中，或者您可以尝试将每个节点与其分配的数据连接起来。
侵入式指针（相对于共享指针）或将对象和智能指针数据打包在一起的std::make_shared可以看到类似的策略。
zett42 发表评论说 std::list<T> 将 T 与节点数据放在一起。正如我上面解释的那样，这实现了单个内存块，但有一个不同的问题：T 不能是多态的。如果你有一个 class A 及其导数 B，那么 node<B> 就不是 node<A> 的导数。如果您努力将 B 插入 std::list<A>，您的对象将：
- 在最好的情况下，导致编译错误（没有构造函数
A::A(const B&)） - 在最坏的情况下，静默地slice
B仅将代表A的部分复制到节点中。
如果你想在单个列表中保存多态对象，一个典型的解决方案是实际使用 std::list<A*> 而不是 std::list<A>。但是你最终得到了我上面解释的额外间接。
另一种方法是创建一个侵入式列表（例如 boost::intrusive::list），其中节点信息实际上是 A 对象的一部分。那么每个节点都可以是A的导数没有问题。
侵入式链表的一大优点是您可以创建一个预先存在的对象列表，而无需任何新分配。要使用 std::list 个指针执行此操作将需要分配内存。
Boost 具有侵入式列表实现，并附有使用理由。 http://www.boost.org/doc/libs/1_63_0/doc/html/intrusive.html
侵入式列表的主要优点之一是您可以廉价地让单个节点属于多个列表。
例如，您可以将一组项目按 3 种不同的方式排序，对应于 3 个不同列表中的条目。例如，用 std::list 做起来会很笨拙。
正如@doron 所提到的，我认为的另一大优势是，一旦您自己创建了对象，列表管理就需要 0 次分配。
Boost 对 intrusive vs. non-intrusive data structures 进行了一些不错的讨论，有利有弊。