Fbl 幹擾性容器簡介

入侵容器 (或侵入式資料結構) 是由 Fuchsia Base Library (fbl::) 提供的容器類型。

這份文件將：

  1. 定義入侵的容器。
  2. 比較幹擾性和非干擾性容器的差異。
  3. 討論 fbl:: 和 std:: 容器的相似之處和差異。
  4. 介紹本指南中會使用的一些基本術語。

什麼是侵入式容器？

入侵容器是一種資料結構，可用來保存物件集合，用於追蹤容器中成員資格的簿記將儲存在物件本身，而不是把物件保留在結構中。為了凸顯這些差異，請考慮在 2 維座標系統中定義點的結構。

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(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:: 提供的屬性，但由於幹擾性和非干擾性容器之間的基本差異，因此有些差異。目前由 fbl:: 定義的主要容器類型有 3 種，還有一種撰寫的容器類型。如下所示：

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

fbl::HashTable<> 可視為組合的容器類型，因為其提供的固定值區數量雜湊資料表，可透過鏈結 (值區類型可能是 fbl::SinglyLinkedList<> 或 fbl::DoublyLinkedList<>) 解決衝突。如要進一步瞭解使用各種容器類型需要納入哪些檔案，請參閱設定建構依附元件。

術語

以下是本指南中所使用的幾個字詞定義。

  • 容器：使用特定演算法追蹤物件參照集合的物件。
  • 節點或節點儲存空間：提供記載作業的一組資料集，可將物件存在特定容器類型中。
  • 可列出、可納入、混合
  • 原始指標：指向物件的非代管 T* 樣式指標。