C++ STL - 容器实现

Question

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

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

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

Answer 1

Is it a Pointer to an object, or the object itself, that is constructed in the nodes allocated memory?

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

When the node in the std::list holds an object and the intrusive container holds a node in their object, how does that lead to better locality?

在 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 和 set 都不会自己分配内存，所有必需的数据都已经在您自己分配的 Foo 节点中。遍历任一容器会自动将钩子和 Foo 内容（至少部分）提取到缓存中，这使得内存访问更快。这种方法还有其他好处，例如无需昂贵的元素查找即可在两个容器的迭代器之间切换的能力。

C++ STL - 容器实现

C++ STL - Containers implementation

c++

containers

boost

intrusive-containers