C++ Boost Intrusive库示例精讲

目录

• 一、说明
• 二、示例

一、说明

Boost.Intrusive 是一个特别适合在高性能程序中使用的库。该库提供了创建侵入式容器的工具。这些容器替换了标准库中的已知容器。它们的缺点是它们不能像 std::list 或 std::set 那样容易使用。但它们有以下优点：

• 侵入式容器不会动态分配内存。对 push_back() 的调用不会导致使用 new 进行动态分配。这是侵入式容器可以提高性能的一个原因。
• 侵入式容器不会动态分配内存。对 push_bacIntrusive 容器的调用存储原始对象，而不是副本。毕竟，它们不会动态分配内存。这带来了另一个优势：诸如 push_back() 之类的成员函数不会抛出异常，因为它们既不分配内存也不复制对象。k() 不会导致使用 new 进行动态分配。这是侵入式容器可以提高性能的一个原因。

这些优势通过更复杂的代码得到了回报，因为必须满足先决条件才能将对象存储在侵入式容器中。您不能将任意类型的对象存储在侵入式容器中。例如，您不能将 std::string 类型的字符串放入侵入式容器中；相反，您必须使用标准库中的容器。

二、示例

示例 18.1 准备了一个类动物，以允许将此类对象存储在侵入式列表中。

示例 18.1。使用 boost::intrusive::list

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal a3{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(a3);
  a1.name = "dog";
  for (const animal &a : animals)
    std::cout << a.name << '\n';
}

在列表中，总是从另一个元素访问一个元素，通常使用指针。如果侵入式列表要在没有动态内存分配的情况下存储动物类型的对象，则指针必须存在于某处以连接元素。

要将动物类型的对象存储在侵入式列表中，该类必须提供侵入式列表所需的变量以连接元素。 Boost.Intrusive 提供了钩子——从这些类中继承了所需的变量。要允许将动物类型的对象存储在侵入列表中，动物必须从类 boost::intrusive::list_base_hook 派生。

钩子可以忽略实现细节。但是，可以安全地假设 boost::intrusive::list_base_hook 至少提供了两个指针，因为 boost::intrusive::list 是一个双向链表。多亏了基类 boost::intrusive::list_base_hook，animal 定义了这两个指针以允许连接这种类型的对象。

请注意 boost::intrusive::list_base_hook 是一个带有默认模板参数的模板。因此，不需要显式传递任何类型。

Boost.Intrusive 提供类 boost::intrusive::list 来创建一个侵入式列表。此类在 boost/intrusive/list.hpp 中定义，并像 std::list 一样使用。可以使用 push_back() 添加元素，也可以迭代元素。

重要的是要了解侵入式容器不存储副本；他们存储原始对象。示例 18.1 将狗、鲨鱼和蜘蛛写入标准输出，而不是猫。对象 a1 链接到列表中。这就是为什么当程序遍历列表中的元素并显示名称时名称的更改是可见的。

因为侵入式容器不存储副本，所以必须在销毁它们之前从侵入式容器中移除对象。

示例 18.2。删除和销毁动态分配的对象

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  animals.pop_back();
  delete a3;
  for (const animal &a : animals)
    std::cout << a.name << '\n';
}

Example18.2

example18.2 使用 new 创建一个动物类型的对象并将其插入到动物列表中。如果您想在不再需要时使用 delete 来销毁该对象，则必须将其从列表中删除。确保在销毁之前从列表中删除该对象——顺序很重要。否则，侵入式容器元素中的指针可能会引用不再包含动物类型对象的内存位置。

因为侵入式容器既不分配也不释放内存，所以当侵入式容器被破坏时，存储在侵入式容器中的对象继续存在。

由于从侵入式容器中删除元素不会自动破坏它们，因此容器提供了非标准扩展。 pop_back_and_dispose() 就是这样的成员函数之一。

示例 18.3。使用 pop_back_and_dispose() 删除和销毁

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  animals.pop_back_and_dispose([](animal *a){ delete a; });
  for (const animal &a : animals)
    std::cout << a.name << '\n';
}

pop_back_and_dispose() 从列表中删除一个元素并销毁它。因为侵入式容器不知道应该如何销毁元素，所以您需要向 pop_back_and_dispose() 传递一个知道如何销毁元素的函数或函数对象。 pop_back_and_dispose() 将从列表中删除对象，然后调用函数或函数对象并将指向要销毁的对象的指针传递给它。示例 18.3 传递了一个调用 delete 的 lambda 函数。

在示例 18.3 中，只有动物中的第三个元素可以使用 pop_back_and_dispose() 删除。列表中的其他元素尚未使用 new 创建，因此不得使用 delete 销毁。

Boost.Intrusive 支持另一种机制来链接元素的删除和销毁。

示例 18.4。使用自动取消链接模式删除和销毁

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
typedef link_mode<auto_unlink> mode;
struct animal : public list_base_hook<mode>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef constant_time_size<false> constant_time_size;
  typedef list<animal, constant_time_size> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  delete a3;
  for (const animal &a : animals)
    std::cout << a.name << '\n';
}

Hooks 支持一个参数来设置链接模式。链接模式使用类模板 boost::intrusive::link_mode 设置。如果 boost::intrusive::auto_unlink 作为模板参数传递，则选择自动取消链接模式。

自动取消链接模式会在破坏容器时自动从侵入式容器中删除元素。示例 18.4 仅将 cat 和 Shark 写入标准输出。

仅当所有侵入式容器提供的成员函数 size() 没有恒定的复杂性时，才能使用自动取消链接模式。默认情况下，它具有恒定的复杂性，这意味着：size() 返回元素数量所花费的时间不取决于容器中存储了多少元素。打开或关闭恒定复杂性是优化性能的另一种选择。

要更改 size() 的复杂性，请使用类模板 boost::intrusive::constant_time_size，它需要 true 或 false 作为模板参数。 boost::intrusive::constant_time_size 可以作为第二个模板参数传递给侵入式容器，例如 boost::intrusive::list，以设置 size() 的复杂度。

现在我们已经看到侵入式容器支持链接模式，并且可以选择设置 size() 的复杂度，看起来似乎还有很多东西需要发现，但实际上并没有。例如，仅支持三种链接模式，而自动取消链接模式是您唯一需要了解的一种。如果您不选择链接模式，则使用的默认模式足以满足所有其他用例。

此外，没有其他成员函数的选项。除了 boost::intrusive::constant_time_size 之外，没有其他类是您需要了解的。

示例 18.5 引入了使用另一个侵入式容器的挂钩机制：boost::intrusive::set。

示例 18.5。将 boost::intrusive::set 的钩子定义为成员变量

#include <boost/intrusive/set.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal
{
  std::string name;
  int legs;
  set_member_hook<> set_hook;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
  bool operator<(const animal &a) const { return legs < a.legs; }
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal a3{"spider", 8};
  typedef member_hook<animal, set_member_hook<>, &animal::set_hook> hook;
  typedef set<animal, hook> animal_set;
  animal_set animals;
  animals.insert(a1);
  animals.insert(a2);
  animals.insert(a3);
  for (const animal &a : animals)
    std::cout << a.name << '\n';
}

有两种方法可以将钩子添加到类：从钩子派生类或将钩子定义为成员变量。虽然前面的示例从 boost::intrusive::list_base_hook 派生了一个类，但示例 18.5 使用类 boost::intrusive::set_member_hook 来定义一个成员变量。

请注意，成员变量的名称无关紧要。但是，您使用的钩子类取决于侵入式容器。例如，要将挂钩定义为侵入式列表的成员变量，请使用 boost::intrusive::list_member_hook 而不是 boost::intrusive::set_member_hook。

侵入式容器有不同的钩子，因为它们对元素有不同的要求。但是，您可以使用不同的几个挂钩来允许将对象存储在多个侵入式容器中。 boost::intrusive::any_base_hook 和 boost::intrusive::any_member_hook 让您可以将对象存储在任何侵入式容器中。多亏了这些类，您不需要从多个钩子派生或将多个成员变量定义为钩子。

默认情况下，侵入式容器期望在基类中定义挂钩。如果将成员变量用作挂钩（如示例 18.5），则必须告知侵入式容器使用哪个成员变量。这就是为什么动物和类型挂钩都被传递给 boost::intrusive::set 的原因。 hook 使用 boost::intrusive::member_hook 定义，每当成员变量用作 hook 时都会使用它。 boost::intrusive::member_hook 期望元素类型、钩子类型和指向成员变量的指针作为模板参数。

示例 18.5 按此顺序将鲨鱼、猫和蜘蛛写入标准输出。

除了本章介绍的类 boost::intrusive::list 和 boost::intrusive::set 之外，Boost.Intrusive 还提供了例如单链表的 boost::intrusive::slist 和 boost::intrusive ::unordered_set 用于哈希容器。

原文地址：https://yamagota.blog.csdn.net/article/details/127416960