0

我目前正在学习很多关于侵入式容器的知识。所以我经常将它们与标准容器进行比较。

让我们以 std::list 为例。我读到这个容器通常实现为双向链表。但是我没有详细阅读节点是如何实现的。我假设有一个“上一个”和“下一个”指针，但是属于这样一个节点的对象呢？它是指向对象的指针，还是对象本身，是在节点分配的内存中构造的？

在 Boost.Intrusive 中指出，他们的容器具有更好的局部性（参见此处：https ://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html ，或此处：https:// /www.boost.org/doc/libs/1_72_0/doc/html/intrusive/performance.html）。我不确定为什么会这样。当 std::list 中的节点包含一个对象并且侵入式容器在其对象中包含一个节点时，这如何导致更好的局部性？

4

1 回答 1

1

它是指向对象的指针，还是对象本身，是在节点分配的内存中构造的？

在 Boost.Intrusive 中，容器的元素类型是节点。为了使其与容器兼容，您必须修改元素类型，使其包含容器所需的数据成员 - 通过从基类继承（例如list_base_hook，参见此处）或通过添加特殊数据成员（例如list_member_hook）。这就是为什么它们被称为侵入式容器。相比之下，标准容器不需要您修改类，而是在必要时将它们包装在容器节点中。

当 std::list 中的节点拥有一个对象并且侵入式容器在其对象中拥有一个节点时，这如何导致更好的局部性？

在std::list每个容器节点（包含您的元素）中单独分配，在其自己的动态内存分配中。该节点包含指向列表中前一个和下一个元素的指针。由于每个节点都是单独分配的，因此它们的位置取决于所使用的内存分配器，但通常您可以假设不同的节点位于内存中的任意位置，可能距离较远且不按顺序排列。此外，遍历列表需要在每次迭代时取消引用指向下一个元素的指针，这通常会妨碍 CPU 中的内存缓存算法。

在boost::intrusive::list中，容器不会对用户强加任何内存分配策略。可以为侵入式容器的多个或所有元素拥有一个内存区域，这使得它们在内存中更紧密地打包并可能有序。当然，这需要用户做更多的工作。列表迭代仍然需要指针解引用并损害 CPU 中的预取器，但如果容器元素紧密排列，则每个下一个节点很有可能位于已经从内存中为前一个元素获取的缓存行中。

另一件需要注意的事情是，当您需要一次将元素存储在多个容器中时，侵入式容器会更有用。对于标准容器，您必须使用指针来引用每个容器中的元素。例如：

// Element type
class Foo {};

std::list< std::shared_ptr< Foo > > list;
std::map< int, std::shared_ptr< Foo > > map;

在此示例中，您至少有一个Foo对象分配、一个list节点分配和一个节点分配map。这些分配中的每一个都任意位于内存中。list通过或通过访问元素map需要额外的间接级别。

使用侵入式容器，您可以将其减少到仅一次分配，而无需额外的间接：

// List hook
typedef boost::intrusive::list_base_hook<> FooListHook;
// Map/set hook
typedef boost::intrusive::set_base_hook<
    boost::intrusive::optimize_size< true >
> FooSetHook;

// Node type
class Foo :
    public FooListHook,
    public FooSetHook
{
    ...
};

boost::intrusive::list< Foo, boost::intrusive::base_hook< FooListHook > > list;
boost::intrusive::set< Foo, boost::intrusive::base_hook< FooSetHook >, ... > set;

在这种情况下，它们自己list也不会分配内存，所有必要的数据都已经在您自己分配的节点内。遍历任一容器会自动将钩子和内容（至少部分）获取到缓存中，这使得内存访问更快。这种方法还有其他好处，例如无需昂贵的元素查找即可在两个容器的迭代器之间切换的能力。setFooFoo

于 2020-01-23T14:30:43.557 回答