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;
};

“value”是共享指针的实例，因此 而在列表中添加或移除指向 LargeObject 的指针仍然需要 用于存储节点状态的分配管理，对象本身没有 需要复制。此外， 方法允许 LargeObject 的单个实例存在于多个 而这些节点只是跟踪 而不是对象的副本。一种简单实施 这会将 next/prev 指针放在 LargeObject 中，直接意味着 LargeObject 的实例可以恰好是 0 或 1 的成员 侵扰性列表，但不是更多。

侵入性容器与非侵入性容器

侵入式容器方法用于跟踪对象的主要优势是 向容器添加元素/从容器中移除元素时缺少分配。在 某些（通常是专用）环境，则堆交互可能会导致 它最好不存在任何潜在故障路径。此外， 与堆的交互通常涉及锁/互斥锁， 则可能会导致非自愿屏蔽这可能会带来不需要的时间 例如，如果代码运行的是不确定性， 在不允许屏蔽的情况下出现。

例如，如果代码需要向清单添加簿记结构，该怎么办？ 内核中发生硬中断处理程序时， 簿记结构无法分配，或簿记结构 会要求 IRQ 处理程序因锁争用（可能造成 不能出现在异常处理程序中）？通过分配容器 作为对象本身的一部分进行记录、侵入式容器 可以避免这些问题。

一般来说，在 系统设计允许实现人员在编译时知道所有 以及对象所在的各种容器这并不意味着 始终是最佳选择，因为它们也有一定的局限性。

最后，对于许多类型的侵入性容器，保留对 表示您在所有容器类型中找到了该对象 当对象被跟踪某个对象时， 引用多个非干扰性容器实例。例如，一个对象 它可能存在于平衡二元搜索树和双重关联中， 可以在树中的 O(log n) 时间找到，然后 从列表中删除对象，而无需在 在 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:: vs. std::

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

如果您需要一个非干扰式容器，那就该找准了。

虽然有提案草稿，但 C++ 标准库不 提供任何侵扰性容器实现方案。与boost::类似， fbl:: 会尝试弥补这一缺口，但所采用的方式要更具局限性和重点。 为 fbl:: 提供的容器类型提供支持的算法为 并且已明确嵌入到容器类型本身的名称中。API 的灵感来自于并试图模仿 std:: 提供的功能， 二者的根本区别在于 侵扰性和非干扰性容器。目前有 3 个主要容器 一个由 fbl:: 定义的容器类型和一个组合容器类型。它们是：

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

fbl::HashTable<> 被视为组合容器类型，因为它提供 固定存储分区计数哈希表，该哈希表使用 存储分区类型可以是 fbl::SinglyLinkedList<> 或 fbl::DoublyLinkedList<>。请参阅设置 build 依赖项 要使用各种容器类型，必须添加该文件

术语

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

  • 容器：使用容器跟踪对对象的引用集合的对象 特定算法。
  • 节点存储或节点存储：一组数据，用于提供 允许对象存在于特定的容器类型中。
  • 可列出、可包含、混入：可用作基类的对象 可以轻松地将对象存储在特定类型的容器中。
  • 原始指针：指向对象的非托管 T* 样式指针。