侵入式与非侵入式容器 - Boost C++ 函数库

侵入式和非侵入式容器

侵入式和非侵入式容器之间的区别
Boost.Intrusive 容器的特性

侵入式和非侵入式容器之间的区别

侵入式容器和非侵入式容器之间的主要区别在于，在 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*> 将允许您执行基本相同的操作（维护和遍历一组 T 类型及其派生类型的对象）。

非侵入式容器存在一些限制。

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

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

操作侵入式容器完全不涉及内存管理。与动态内存相关的时间和大小开销可以最小化。
同一个对象可以同时插入到多个容器中，并且对对象大小的开销极小。
遍历侵入式容器比语义上等效的指针容器需要更少的内存访问：遍历速度更快。
侵入式容器比非侵入式容器提供更好的异常保证。在某些情况下，侵入式容器提供非侵入式容器无法实现的无抛出保证。
从指向元素的指针或引用计算到该元素的迭代器是一个常数时间操作（计算 T* 在 std::list<T*> 中的位置具有线性复杂度）。
由于侵入式容器不进行内存管理，因此在插入和删除对象时，侵入式容器提供了可预测性。内存管理通常不是一个可预测的操作，因此非侵入式容器的复杂性保证比侵入式容器提供的保证更宽松。

侵入式容器也有缺点。

存储在侵入式容器中的每种类型都需要额外的内存来保存容器所需的维护信息。因此，每当某种类型将被存储在侵入式容器中时，您必须相应地更改该类型的定义。尽管使用 Boost.Intrusive 可以轻松完成此任务，但修改类型的定义有时是一个关键问题。
在侵入式容器中，您不是存储对象的副本，而是将原始对象与其他对象链接在容器中。对象不需要复制构造函数或赋值运算符即可存储在侵入式容器中。但是，您必须注意可能的副作用，尤其是在修改关联容器的内容时。
用户必须独立于容器管理已插入对象的生命周期。
再次，您必须小心：与 STL 容器不同，即使不直接操作侵入式容器，也很容易使迭代器失效，因为对象可以在从容器中删除之前被销毁。
Boost.Intrusive 容器是不可复制且不可赋值的。由于侵入式容器不具备分配能力，因此这些操作没有意义。但是，可以使用交换来实现移动能力。为了简化存储Boost.Intrusive 容器的类的复制构造函数和赋值运算符的实现，Boost.Intrusive 提供了特殊的克隆函数。有关更多信息，请参阅克隆 Boost.Intrusive 容器部分。
分析使用容器的程序的线程安全性对于侵入式容器来说更加困难，因为容器可能在没有显式调用容器成员的情况下被间接修改。

表 16.1. 侵入式容器的优点和缺点摘要

问题	Intrusive	非侵入式
内存管理	外部	通过分配器内部管理
插入/删除时间	更快	更慢
内存局部性	更好	更糟
可以将同一个对象插入多个容器	是	否
异常保证	更好	更糟
从值计算迭代器	常量	非恒定
插入/删除可预测性	高	低
内存使用	最小	超过最小
通过值插入对象并保留多态行为	是	否（切片）
用户必须修改要插入的值的定义	是	否
容器可复制	否	是
已插入对象的生命周期由...管理	用户（更复杂）	容器（更简单）
容器不变量可以在不使用容器的情况下被破坏	更容易	更难（仅适用于指针容器）
线程安全分析	更难	更容易

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

Boost C++ 库

侵入式和非侵入式容器

侵入式和非侵入式容器之间的区别

Boost.Intrusive 容器的特性