關聯容器

除了已排序的容器外，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，使其成為物件的 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_;

特徵會告知容器可以在哪裡找到索引鍵，以及排序鍵的方式。在這個範例中，系統會傳回 GetKey 中 Endpoint 的常數參照，而非副本，以免 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) (僅限 EqualTo(B, A) 時)
• LessThan(A, B) (僅限 if-and-if (非 LessThan(B, A)))
• 僅限 EqualTo(B, A) 或 LessThan(B, A) 時使用 LessThan(A, B)

在關聯容器中新增元素

由於關聯容器不會維護使用者作業定義的特定序列，因此在關聯容器中加入元素是更為簡單明瞭的程序。只要在容器上呼叫 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) 作業。不過，如果與 N 有足夠的值區，且雜湊函式是平的，效能便可接近 O(1)。

如果容器中沒有包含所需金鑰的元素，系統會改為傳回容器的 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 混合實作，可藉由說出 InContainer() 從 UpdateAwesomeness() 叫用。

此外，您不需要在移除之前在樹狀結構中找到物件。由於參照要更新的物件，由於容器具有侵入性，所以該物件已經知道物件位於容器內部結構的哪個位置。