fbl 干扰容器简介

侵入式容器（即侵入性数据结构）是 Fuchsia 基础库 (fbl::) 提供的容器类型。

此文档将：

  1. 定义什么是侵入式容器。
  2. 比较入侵式容器和非干扰性容器之间的区别。
  3. 讨论 fbl:: 容器和 std:: 容器之间的异同。
  4. 介绍本指南中会用到的一些基本术语。

什么是干扰性容器？

侵入式容器是一种数据结构，可用于存放对象集合。在这种容器中，用于跟踪容器中成员资格的簿记活动存储在对象本身中，而不是将对象与簿记在结构中同时存储。为了突出区别，可以考虑使用一个定义二维坐标系中点的结构。

struct Point {
  float x, y;
};

在双重链接列表的传统非干扰性实现中，列表中的节点可能如下所示：

struct ListNode {
  Point val;
  ListNode *next, *prev;
};

而侵入式版本则是

struct Point {
  float x, y;
  Point *next, *prev;
};

最初，这两种方法看起来非常相似。这种区别似乎很像一个问题，即关于哪个对象包含在另一个对象中。不过，随着时间的推移，这种差异会变得越来越明显。

向非干扰点列表添加点意味着：

  1. 分配 ListNode
  2. 将要添加到列表中的 Point 复制到 ListNode 的 val 成员中
  3. 将 ListNode 的 next/prev 指针链接到列表中。

移除该点与相反的过程相同。

  1. 指针已解除关联。
  2. Point 的内容会复制到本地存储空间。
  3. 最后，系统会取消分配 ListNode。

使用干扰性列表时，添加/移除操作会跳过对 Point 成员的分配/取消分配和复制操作。该点对象中已存在的 next/prev 指针会在添加操作期间直接关联到相应列表，在移除期间会解除关联。虽然这种干扰性形式不必执行任何分配或复制任何结构即可将元素添加到列表中，但系统中的每个 Point 都必须承担下一项/上一项簿记的开销，即使不在列表中也是如此。

虽然小结构或原始数据类型可能由无干扰列表中的值保留，但当对象变大时，使用某种适当的指针类型跟踪对象会变得更常见，而不是按值存储对象。例如：

struct ListNode {
  std::shared_ptr<LargeObject> ptr;
  ListNode *next, *prev;
};

存储在此列表中的“值”是共享指针的实例，因此虽然在列表中添加或移除指向 LargeObject 的指针仍然需要管理用于存储节点状态的分配，但将对象本身添加到列表中时，无需再复制对象本身。此外，这种方法使 LargeObject 的单个实例同时存在于多个容器中，因为节点只是跟踪对对象的引用，而不是对象的副本。这种侵入式方法的简单实现会将 next/prev 指针置于 LargeObject 中，这直接意味着 LargeObject 的实例可以正好是 0 个或 1 个侵入式列表的成员，但不是更多。

干扰性容器与非干扰性容器

采用干扰性容器方法跟踪对象的主要优势是在向容器添加元素/从容器中移除元素时缺少分配。在某些（通常是专门的）环境中，堆交互可能会引入潜在故障路径，但理想情况下，此路径不存在。此外，与堆的互动通常涉及与锁/互斥量的交互，这可能会导致非自愿的阻塞。这可能会带来不良的时间不确定性，或者在某些情况下，如果代码在不允许阻塞的上下文中运行，您甚至可能根本无法选择这样做。

例如，如果代码需要在内核中的硬中断处理程序期间向列表添加簿记结构，却无法分配簿记结构的分配，或者簿记的分配需要 IRQ 处理程序因锁争用而进行阻塞，该怎么办？通过提前将容器簿记分配为对象本身的一部分，可以避免这些问题的侵入式容器方法。

一般来说，如果系统设计允许实现者在编译时知道对象将存在于的所有不同容器中，则侵入式容器可以带来性能优势。但是，这并不意味着它们始终是最佳选择，因为它们也存在限制。

最后，对于许多类型的干扰性容器，保留对某个对象的引用意味着您已将该对象置于所有容器类型中，如果在多个非干扰性容器实例中通过引用跟踪某个对象，则它有可能存在于所有容器类型中。例如，某个对象既可能存在于平衡二进制搜索树中也存在于双链接列表（均具有干扰性）中，它可能位于树中的 O(log n) 时间，然后在 O(1) 时从列表中移除，无需在 O(n) 时间后在列表中找到该对象，然后再将其移除。

这两种方法的优缺点简要列表可能如下所示：

无干扰：

  • 优点

    • 可用于按值跟踪简单对象，甚至是 int 或 float 等原始数据类型

    • 不需要更改对象本身的定义，以便在其他容器中管理对象。如果库 A 中定义了对象 O，但用户希望在自己的程序中创建 A::O 的集合，但无法合理地重新定义 O，这种做法尤其有用。

    • 通过引用跟踪的对象可以轻松独立存在于多个容器中。

  • 缺点

    • 需要独立的簿记分配管理（通常在每次添加或移除操作时）。这种管理往往意味着隐藏的堆交互，这可能会引入开销、时间不确定性以及额外的复杂性，因为用户需要管理潜在的故障路径。

    • 查找容器 A 中对象的位置并不会提供有关容器 B 中对象位置的信息。例如，通过 O(log n) 操作查找 std::map 中包含的对象并不能帮助我找到同时包含在 std::deque 中的同一对象。如果要从 std::deque 中移除该对象，必须先通过单独的 O(n) 操作找到它。

干扰性：

  • 优点

    • 加入或离开容器所需的开销最小，并且不存在因锁争用而导致的失败或非自愿退让，因为簿记开销是在对象创建期间预先支付的。

    • 查找某个对象的实例时，会隐式查找该对象存在的所有容器中的实例。

    • 了解某个对象当前是否是容器类型 A 中的容器，它是该对象的一个属性，始终可在 O(1) 时（通过对象）进行测试。

  • 缺点

    • 能够被封装是对象的基本属性。要更改对象中可能存在的容器数量或类型，必须更改对象本身的定义，并且必须重新编译依赖于该定义的所有代码。

    • 只能跟踪对象本身。原始数据类型没有位置存储额外的簿记信息，并且无法以干扰性方式进行跟踪。

fbl:: - std::

C++ 标准库提供了大量与实现无关的非干扰容器。例如，std::map 是一个有序的关联容器，但不要求标准库的实现使用任何特定的数据结构来实现 std::map，只不过，所选的实现可以为标准指定的各种容器操作提供特定保证，例如最糟糕的算法复杂性或迭代器失效方面的保证。

如果您需要一个不会产生干扰的容器，就应如此。

虽然已有草稿提案，但 C++ 标准库目前不会提供任何干扰性容器实现。与 boost:: 类似，fbl:: 会尝试填补此缺口，但方式要受限/更集中。支持 fbl:: 提供的容器类型类型的算法是显式的，并嵌入到容器类型本身的名称中。这些 API 的灵感来自并尝试模拟 std:: 提供的 API，但由于入侵性容器和非干扰性容器之间的根本差异，它们存在一些差异。目前，fbl:: 定义了 3 种主要容器类型，以及 1 种组合容器类型。它们是：

  • fbl::SinglyLinkedList<>
  • fbl::DoublyLinkedList<>
  • fbl::WAVLTree<>
  • fbl::HashTable<>

fbl::HashTable<> 被视为组合容器类型，因为它提供一个固定的存储分区计数哈希表，该表使用链来解决冲突，其中存储分区类型可能是 fbl::SinglyLinkedList<> 或 fbl::DoublyLinkedList<>。如需详细了解为了使用各种容器类型而需要包含哪些文件，请参阅设置 build 依赖项。

术语

以下是本指南中所用术语的一些定义。

  • 容器：使用特定算法跟踪对象的引用集合的对象。
  • 节点存储或节点存储：提供簿记的一组数据集，允许对象存在于特定容器类型中。
  • Listable、Containable、Mix-in：一个对象，可用作基类，让对象能够轻松存储在特定类型的容器中。
  • 原始指针：指向对象的非托管 T* 样式指针。