关联容器

除了有序容器之外，还有 fbl:: 提供了两种类型的“关联”容器：

• HashTable 是一个无序的关联容器。
• WAVLTree 是一个有序关联容器。

关联容器会将容器中的每个对象与一个键相关联，该键的 类型和属性均可由用户指定。这些元素可以找到 使用此键移除，而对于 WAVLTree，则 枚举将由此键及其属性确定。开始时间 HashTable 是一个无序容器，枚举的顺序不是 只要是特别的东西

请参阅设置 build 依赖项 要使用各种容器类型，必须添加该文件

本指南的这一部分将向您介绍

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_ 成员。虽然这样就能轻松 但对某些代码而言，这种方法并不总是可行的方法。

键有时可能需要可变，请参阅 更新位于容器中的对象键 了解如何正确处理此模式的信息。

利用关键 trait 控制关键行为

默认情况下，键必须是可复制类型，并针对== 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) 为条件时（非 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) 操作，但如果有足够的分桶，性能可能接近 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() 中调用 mix-in，只需说 InContainer()。

此外，在移除对象之前无需在树中找到该对象。 给定要更新的对象的引用，即是已知的 其中对象位于容器的内部结构中， 具有干扰性。