「生活可以更简单, 欢迎来到我的开源世界」
  1. 侵入式容器和非侵入式容器之间的差异
  2. Boost.Intrusive的属性
侵入式容器和非侵入式容器
2020-12-23
C++

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

原文: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必须包含所需的nextprevious指针:

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 的对象和从它派生的类型)。

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

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

侵入式容器也有缺点:

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

问题 侵入 非侵入式
内存管理 外部 内部通过分配器
插入/擦除时间 更快
内存区域 更好 糟糕
可以在多个容器中插入同一对象 是的
异常保证 更好 糟糕
根据值计算迭代器 常数 非常数
插入/擦除可预测性
内存使用 最小 超过最小
按值保留多态行为插入对象 是的 否(切片)
用户必须修改要插入的值的定义 是的
容器是可复制的 是的
管理插入对象的生命周期 用户(更复杂) 容器(不太复杂)
容器不变量可以不使用容器就损坏 容易 困难(仅使用指针容器)
线程安全分析 困难 容易

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

<⇧>