Fbl 幹擾性容器簡介

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

這份文件將：

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

什麼是侵入式容器？

入侵容器是一種資料結構，可用於 物件集合，用於追蹤 是儲存在物件本身，而不是保留物件 還是在結構體中保存記號如要突顯其中差異 並考慮定義在 2D 座標系統中點的結構。

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) 時間， 因而從清單中移除，而不需要在

一份簡短的清單，列出這兩種方法的優缺點 輸入：

不會造成乾擾：

• 優點

  • 可用來依值追蹤簡易物件，甚至是原始資料類型 例如 int 或 float

  • 不必變更物件本身的定義， 然後在不同的容器中管理物件這對物件來說特別有用 O 已在程式庫 A 中定義，但使用者想建立 A::O 在自己的程式中，且無法合理地重新定義 O。

  • 透過參照追蹤的物件很容易存在於多個容器中 以便獨立作業

• 缺點

  • 需要獨立管理簿記，通常為 每個新增或移除作業此管理經常隱含隱藏堆積 這可能會增加開銷、時間不確定等 更加複雜。

  • 在容器 A 中尋找物件的位置，系統不會提供任何資訊 容器 B 中物件的位置舉例來說，您可以找出 std::map 中包含的物件具有 O(log n) 作業，則不會 協助我找出同時包含 std::deque。如果要從 std::deque 中移除物件，必須找到 並先執行獨立的 O(n) 作業

幹擾性：

• 優點

  • 將加入或離開容器的負擔降至最低，而且沒有失敗的機會 或個人自營收益，因為記帳費用遭鎖定 需要預先付費

  • 尋找物件的例項以隱含方式找出 物件

  • 瞭解物件目前是否位於容器 A 類型 是物件的屬性，且可隨時在 O (1) 中測試(透過物件) 讓應用程式從可以最快做出回應的位置 回應使用者要求

• 缺點

  • 是否能夠包含是物件的基本屬性。於 來變更物件可能所屬的容器數量或類型； 您必須變更物件本身的定義，且所有 取決於該定義必須重新編譯。

  • 您只能追蹤物件本身。基本資料類型沒有 任何位置儲存額外記帳資訊，且無法追蹤 幹擾性時尚

fbl::對戰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<>。詳情請參閱設定版本 依附元件。 ，才能使用各種容器類型。

術語

以下是相關字詞定義 指南。

• 容器 ：一種物件，可追蹤使用 採用特定演算法
• 節點儲存空間或節點儲存空間 ：提供資料的簿記資料組 可讓物件存在於特定類型的容器中
• 可列出、可包含、混合： 可作為基本類別使用 可輕鬆將物件儲存在特定類型的容器中
• 原始指標：非代管的 T* 樣式指標，指向物件。