在阅读 FreeBSD 中的内核数据结构时，我偶然发现了 MBuf。 MBuf 包含一个指向下一个 MBuf 的指针，在 MBuf 链中，实现了一个链表。每个 MBuf 本身也包含特定于链表中该节点的数据。
我更熟悉将容器类型与值类型分开的设计(考虑 std::list 或 System.Collections.Generic.LinkedList)。我正在努力理解将容器语义嵌入到数据类型中的值(value)主张——获得了哪些效率？真的只是为了消除节点实例指针存储吗？
最佳答案
假设您有一个指向列表中节点的迭代器/指针。为了获取数据，您必须:
- 从节点读取指向数据的指针
- 解引用刚刚读取的指针并读取实际数据
另一方面，如果列表概念“嵌入”在您的数据结构中，您可以在单个内存操作中读取您的对象，因为它与节点本身一起。
分离列表节点及其数据的另一个问题是列表节点本身很小(通常只有 2 或 3 个指针)。因此，在内存中保留如此小的结构的内存开销可能很重要。你知道——诸如 new 之类的操作或 malloc实际上消耗的内存比分配的多——系统使用自己的树结构来跟踪内存空闲和空闲的位置。
在这种情况下，将事物分组到单个分配操作中是有益的。您可以尝试将多个列表节点保存在小包中，或者您可以尝试将每个节点与其分配的数据连接起来。
侵入式指针(相对于共享指针)或 std::make_shared 可以看到类似的策略将对象和智能指针数据打包在一起。
zett42 发表评论 std::list<T>保持T连同节点数据。这实现了我上面解释的单个内存块，但有一个不同的问题:T不能是多态的。如果你有一个类 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的导数没有问题。
关于c++ - 将链表嵌入数据结构有什么好处？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42599095/