侵入式容器和非侵入式容器

侵入式容器和非侵入式容器

原文：https://www.boost.org/doc/libs/1_75_0/doc/html/intrusive/intrusive_vs_nontrusive.html

侵入式容器和非侵入式容器之间的差异

侵入性容器和非侵入式容器之间的主要区别在于，在C++中，非侵入式容器存储用户传递的值的副本。 非侵入式容器使用Allocator模板参数分配存储的值：

#include <list>
#include <assert.h>

int main()
{
   std::list<MyClass> myclass_list;

   MyClass myclass(...);
   myclass_list.push_back(myclass);

   //The stored object is different from the original object
   assert(&myclass != &myclass_list.front());
   return 0;
}

要存储新分配的myclass的副本，容器需要额外的数据：std::list通常分配包含指向下一个节点和上一个节点以及值本身的指针的节点。类似于：

//A possible implementation of a std::list<MyClass> node
class list_node
{
   list_node *next;
   list_node *previous;
   MyClass    value;
};

另一方面，侵入性容器不存储传递对象的副本，但它存储对象本身。在容器中插入对象所需的其他数据必须由对象本身提供。例如，要插入MyClass到一个实现为链表的侵入性容器中，MyClass必须包含所需的next和previous指针：

class MyClass
{
   MyClass *next;
   MyClass *previous;
   //Other members...
};

int main()
{
   acme_intrusive_list<MyClass> list;

   MyClass myclass;
   list.push_back(myclass);

   //"myclass" object is stored in the list
   assert(&myclass == &list.front());
   return 0;
}

正如我们所看到的，知道类应该包含哪些附加数据并非易事。 Boost.Intrusive提供了多个侵入性容器，以及使用户类与这些容器兼容的一种简单方法。

Boost.Intrusive的属性

在语义上**，Boost.intrusive**容器类似于包含指向对象的 STL 容器。也就是说，如果您有一个包含T类型的对象的侵入性列表，则std::list<T*>允许您执行与STL容器完全相同的操作（维护和导航一组类型为 T 的对象和从它派生的类型）。

非侵入式容器有一些限制：

• 对象只能属于一个容器：如果要在两个容器之间共享对象，则必须存储这些对象的多个副本，或者需要使用指针的容器：std::list<Object*> 。
• 在某些应用程序中，使用动态分配创建传递值的副本可能是性能和大小的瓶颈。通常，动态分配会为每个分配施加大小开销，以存储簿记信息，并同步用于从不同线程进行受保护的并发分配。
• 在C++11 之前，只能将对象的副本存储在非侵入式容器中。仍需要复制或移动构造函数以及复制或移动赋值运算符，并且不可复制和不可移动的对象不能存储在某些容器中。在任何情况下，必须使用构造函数在容器内创建新对象，并且不能在两个容器之间共享同一对象。
• 无法将派生对象存储在 STL 容器中，同时保留其原始类型。

侵入式容器具有一些重要优势：

• 使用侵入性容器操作不会调用任何内存管理。可以最大限度地减少与动态内存关联的时间和大小开销。
• 同一对象可以同时插入多个容器中，对象大小中具有很小的开销。
• 迭代入侵式容器所需的内存访问量比指针的语义等效容器要少：迭代更快。
• 与非侵入式容器，侵入式容器提供更好的异常保证。在某些情况下，侵入式容器提供非侵入式容器无法实现的不抛异常的保证。
• 从指针到元素的引用到元素的计算是一个恒定的时间操作（计算std::list<T*>中T*的位置具有线性复杂性）。
• 侵入性容器在插入和擦除对象时提供可预测性，因为对侵入性容器没有进行内存管理。内存管理通常不是一个可预测的操作，因此来自非侵入式容器的复杂性保证比侵入式容器提供的保证更宽松。

侵入式容器也有缺点：

• 存储在侵入性容器中的每种类型的存储需要额外的内存来保存容器所需的维护信息。因此，每当某个类型存储在侵入性容器中时，您必须适当地更改该类型的定义。虽然这个任务对Boost.Intrusive来说很easy，但接触类型的定义有时也是一个关键问题（可能无法修改的意思）。
• 在侵入性容器中，不存储对象的副本，而是将原始对象与容器中的其他对象链接。对象不需要复制构造函数或赋值运算符存储在侵入性容器中。但是，每当您更改对象的内容时，您都必须注意可能的副作用（这对于关联容器尤其重要）。
• 用户必须独立管理容器中的插入对象的生存期。
• 同样，您必须小心：与 STL 容器相比，无需直接接触侵入性容器即可轻松地使遍该程序无效，因为对象可以在从容器中擦除之前释放。
• Boost.Intrusive不可复制，不可分配。由于侵入性容器没有分配功能，因此这些操作没有意义。但是，交换可用于实现移动功能。为了便于实现存储Boost.Intrusive容器的类的复制构造函数和赋值运算符**，Boost.intrusive**提供了特殊的克隆函数。有关详细信息Cloning Boost.Intrusive containers容器部分。
• 对使用侵入型容器的程序进行线程安全分析更加困难，因为容器可能会间接修改，而无需显式调用容器成员。

表 19.1.侵入性容器的优点和缺点摘要

有关入侵和非侵入容器之间的性能比较，请参阅性能部分。