關聯容器

除了已排序的容器外，fbl:: 提供兩種「關聯」容器：

• HashTable 是未排序的關聯容器。
• WAVLTree 是已排序的關聯容器。

關聯容器將容器中的每個物件與 使用者可以指定類型和屬性可以找到元素或 現已使用此金鑰移除；在 WAVLTree 的情況下， 列舉將由這個鍵及其屬性決定。開始時間 HashTable 是未排序的容器，列舉的順序不是 一定是任何特定事物

詳情請參閱設定版本 依附元件。 ，才能使用各種容器類型。

本指南的章節將說明

1. 定義物件的索引鍵，並教導容器如何存取物件
2. 使用特徵類別控管容器使用金鑰的方式
3. 在容器中加入元素
4. 移除容器中的元素
5. 尋找容器中的元素
6. 新增元素時處理衝突
7. 更新容器中元素的鍵

定義金鑰類型並提供容器存取權

與節點狀態相同，儲存在關聯容器中物件的索引鍵具有乾擾性 物件本身的屬性這些並非節點狀態的靜態成員 而且不必在物件中加入額外的儲存空間，只要使用 能以一致且確定的方式從物件中計算 如要對容器公開金鑰，最簡單的方法就是讓容器使用 和實作 GetKey 函式。範例如下：

class Obj : public fbl::WAVLTreeContainable<Obj*>  {
 public:
  explicit Obj(uint32_t awesomeness) : awesomeness_(awesomeness) {}
  uint32_t GetKey() const { return awesomeness_; }

 private:
  const uint32_t awesomeness_;
};

using ObjSortedByAwesomeness = fbl::WAVLTree<uint32_t, Obj*>;

這裡已定義容器，該容器使用 32 位元無正負號整數 且最後會保留一組 Obj，並按遞增順序排序 大家都很期待你需要遵守規則。

1. GetKey 方法須為 const。
2. 每當物件位於關聯容器中時，GetKey 方法就必須 保持一致每次呼叫時都必須傳回相同的值。

在此範例中，我們保證規則 2 符合規則 2，將 物件 const 的 awesomeness_ 成員。這個簡單的做法 對某些程式碼來說，這不一定是實際的做法。

鍵有時必須可以變動，請參閱 更新物件在容器中的金鑰， 瞭解如何正確處理此模式。

以主要特性控管按鍵行為

根據預設，鍵必須是可複製的類型，且具有定義的 == 運算子。 HashTable，以及為 WAVLTree 定義 < 和 == 運算子。用於 已排序的容器 (WAVLTree)，物件將以遞增順序儲存 順序。如果想進一步控管這項功能，該怎麼做？如果您的類型是 無法複製，或者您希望以遞減方式排序而非遞增順序？

為此，您可以使用自訂索引鍵特徵類別。和自訂節點特徵一樣 您需定義結構體或類別來公開三種公開的靜態方法， 可用來擷取物件的鍵，並比較這些鍵。這裡是 範例：

struct Endpoint {
  // Move only, for some reason
  Endpoint() = default;
  Endpoint(const Endpoint&) = delete;
  Endpoint& operator=(const Endpoint&) = delete;
  Endpoint(Endpoint&&) = default;
  Endpoint& operator=(Endpoint&&) = default;

  uint32_t ipv4_addr_{0};
  uint16_t ipv4_port_{0};
};

class Obj : public WAVLTreeContainable<Obj*> {
 public:
  // ...

 private:
  struct EndpointKeyTraits {
    static const Endpoint& GetKey(const Obj& obj) const { return obj.ep_; }
    static bool LessThan(const Endpoint& ep1, const Endpoint& ep2) {
        return (ep1.ipv4_addr_ > ep2.ipv4_addr_) ||
               ((ep1.ipv4_addr_ == ep2.ipv4_addr_) &&
                (ep1.ipv4_port_ > ep2.ipv4_port_));
    }

    static bool EqualTo(const Endpoint& ep1, const Endpoint& ep2) {
        return (ep1.ipv4_addr_ == ep2.ipv4_addr_) &&
               (ep1.ipv4_port_ == ep2.ipv4_port_);
    }
  };

  friend struct EndpointKeyTraits;

  Endpoint ep_;

 public:
  using ByEndpointMap = fbl::WAVLTree<Endpoint, Obj*, EndpointKeyTraits>;
};

Obj::ByEndpointMap objs_by_descending_endpoint_;

特徵會指示容器要在哪裡找到金鑰以及如何 排序鍵在這個範例中，Endpoint 傳回 GetKey 而非副本，以免發生 Endpoint 的問題 只能在移動作業中使用。此外，LessThan 運算的意義是反轉的 導致保留物件的樹狀結構，改為按遞減 Endpoint 順序保留物件 遞增排序。使用者定義的 LessThan 和 EqualTo 作業會 都必須具有確定性、遞移性和可交換性也就是說：

• 對同一組鍵多次執行比較作業 一律必須傳回相同的結果。
• LessThan(A, B) 和 LessThan(B, C) 表示 LessThan(A, C)
• EqualTo(A, B) 和 EqualTo(B, C) 表示 EqualTo(A, C)
• EqualTo(A, B) if-and-only-if EqualTo(B, A)
• LessThan(A, B) if-and-only (非 LessThan(B, A))
• 而非 LessThan(A, B) if-and-only (EqualTo(B, A) 或 LessThan(B, A))

新增元素至關聯容器

由於關聯容器不會維護由 為使用者的作業 (在關聯容器中加入元素)。 本質上較為直接瞭解只要在容器上呼叫 insert， 適當的指標類型和有序的容器一樣，代管指標 可用於複製或移動指標的擁有權

class Obj : public fbl::RefCounted<Obj>,
            public fbl::WAVLTreeContainable<fbl::RefPtr<Obj>> {
 public:
  explicit Obj(int val) : val_(val) {}
  int val() const { return val_; }
  int GetKey() const { return val(); }
 private:
  const int val_;
};

fbl::WAVLTree<int, fbl::RefPtr<Obj>> objects;

for (int i = 0; i < 100; ++i) {
  fbl::RefPtr<Obj> obj_ref = fbl::MakeRefPtr<Obj>(i);
  if (i % 2) {
    // For odd numbered elements, move our reference directly into the
    // collection of objects.
    objects.insert(std::move(obj_ref));
  } else {
    // For even number elements, make a copy of our pointer (so, another
    // AddRef), and then give away our reference to someone else.
    objects.insert(obj_ref);
    TakeEvenElementReference(std::move(obj_ref));
  }
}

從關聯容器中移除元素

如先前所述，關聯容器中的元素 由金鑰 (WAVLTree) 決定的列舉順序，或是並未提供保證結果 列舉順序 (HashTable)。不過，它們仍具有列舉順序 進而定義 front() 和 back()因此 fbl:: 關聯集合中的移除元素 DoublyLinkedList，如果沒有 erase_next。

• pop_front()
• pop_back()
• erase(Iter or Obj&)
• clear()

這裡的用法與 序列容器 為求簡潔，所有這些註解已省略。

在關聯容器中尋找元素

當關聯容器的成員出現在 使用 find(Key) 方法建構容器。尋找字串的複雜運算 作業為 WAVLTree 的 O(log n)。雜湊資料表使用已連結的清單鏈結 解決衝突，因此他們的尋找作業就技術上為 O(n) 不過，如果值區數量足夠，效能可以約略等於 O(1) 相對於 N，雜湊函式是扁平的

如果容器中沒有包含所需鍵的元素，則 end() 的值 。

void PrintValueForKey(const SomeAssociativeContainerType& container, KeyType key) {
  auto iter = container.find(key);
  if (iter.IsValid()) {
    cout << "Found val (" << iter->val() << "for Key (" << key << ") in the container.\n";
  } else {
    cout << "Key (" << key << ") was not found in the container.\n";
  }
}

是已排序的關聯容器，因此 WAVLTree 也支援 upper_bound(Key) 和 lower_bound(Key) 作業，以遵循 std:: API。

• lower_bound(Key) 尋找容器中第一個索引鍵較大的元素 大於或等於提供的鍵。
• upper_bound(Key) 嚴格尋找容器中第一個含有索引鍵的元素 大於提供的鍵。

// Given a set of objects whose keys are initially
// "1 5 25 67 100"
fbl::WAVLTree<uint32_t, std::unique_ptr<Obj>> objects;
fbl::WAVLTree<uint32_t, std::unique_ptr<Obj>>::iterator iter;

iter = objects.lower_bound(5);    // iter->GetKey() == 5
iter = objects.upper_bound(5);    // iter->GetKey() == 25
iter = objects.lower_bound(26);   // iter->GetKey() == 67
iter = objects.upper_bound(26);   // iter->GetKey() == 67
iter = objects.lower_bound(100);  // iter->GetKey() == 100
iter = objects.upper_bound(100);  // (iter == objects.end()) && !iter.IsValid()
iter = objects.lower_bound(101);  // (iter == objects.end()) && !iter.IsValid()

處理關聯容器的衝突

和 std::map 一樣，fbl:: 中的關聯容器需要一組索引鍵 且不允許碰撞。如果發生衝突 插入作業期間，就會觸發 ZX_DEBUG_ASERT 或結果 未啟用未定義的偵錯斷言行為。

因此，如何在發生衝突的環境中插入裝置 處理？透過現在的兩種方法，我們能有效控制 碰撞發生時，插入的行為如下所示：

• insert_or_find
• insert_or_replace

如果未發生衝突，這兩者就相當於簡易插入。 否則 insert_or_find 不會執行插入作業，且會傳回 疊代子新增至插入物件時，會視需要與物件搭配使用。函式 傳回布林值，表示如果為 true，則成功插入 (無衝突)。

insert_or_replace 會直接替換容器中的元素，並 會反轉至您設定的物件參照物件或 nullptr 版本的參照 在沒有衝突的情況下使用指標類型在程式碼中 包括：

// Attempt to insert an object into the container, but do nothing in the case of
// a collision.
Obj* ptr = GetAnObj();
container.insert_or_find(ptr);

// Attempt to insert an object into the container.  In the case of collision,
// the reference stored in ptr will not be consumed.  Put it back and log a
// message about the collision.
ContainerType::iterator collided;
std::unique_ptr<Obj> ptr = GetAnObj();
if (!container.insert_or_find(std::move(ptr), &collided)) {
  ASSERT(ptr.get() != nullptr);
  ASSERT(collided.IsValid());
  printf("Collided with obj \"%s\" when trying to insert obj \"%s\"\n",
         collided->name(), ptr->name());
  PutAnObjBack(std::move(ptr));
}

// Attempt to insert an object into the container, replacing whatever was there
// before and letting the reference to the replaced object drop on the ground,
// destroying the object if this was a managed pointer and the last reference to
// the object.
std::unique_ptr<Obj> ptr = GetAnObj();
container.insert_or_replace(std::move(ptr));

// Attempt to insert an object into the container, recovering the object
// replaced in the case of a collision.
std::unique_ptr<Obj> ptr = GetAnObj();
std::unique_ptr<Obj> replaced = container.insert_or_replace(std::move(ptr));
if (replaced != nullptr) {
  // We collided and replaced the element we collided with. Put this object
  // back.
  PutAnObjBack(std::move(replaced));
}

更新容器中物件的金鑰

請參閱「範例」，瞭解如何定義 鍵的特性，物件的美觀性是 物件。有一個索引鍵時無法變更該鍵的值 不會違反容器的不變體 未定義的行為如果物件不在物件中，金鑰「可以」變更 就不會出現任何問題請更新上一個範例，以允許 可變的優異性 看看會如何更新 容器中的 Obj。

class Obj : public fbl::WAVLTreeContainable<Obj*>  {
 public:
  explicit Obj(uint32_t awesomeness) : awesomeness_(awesomeness) {}
  uint32_t GetKey() const { return awesomeness; }

  void UpdateAwesomeness(uint32_t awesomeness) {
    ZX_DEBUG_ASSERT(!InContainer());
    awesomeness_ = awesomeness;
  }

 private:
  uint32_t awesomeness_;
};

fbl::WAVLTree<uint32_t, Obj*> all_objs;

void UpdateAwesomeness(Obj& obj, uint32_t new_val) {
  ZX_DEBUG_ASSERT(obj.InContainer());
  all_objs.erase(obj);
  UpdateAwesomeness(new_val);
  all_objs.insert(*obj);
}

請注意，為避免發生意外，此範例會宣告 則在鍵的值為 已變更。InContainer 是由物件的 WAVLTreeContainable 實作 並可透過 UpdateAwesomeness() 直接 InContainer()。

而且，不需要在樹狀結構中找出這個物件，才能將其移除。 鑒於要更新物件的參照，因為已有已知該物件的參照 其中物件會位於容器的內部結構中 容器的干擾性