关联容器

除了有序容器之外，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 会使对象 const 的 awesomeness_ 成员。虽然这样可以轻松避免出现错误，但对于某些代码而言，这种方法并不总是切实可行。

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

利用关键特征控制关键行为

默认情况下，键必须是可复制类型，对于 HashTable 已定义 == 运算符，对于 WAVLTree 已定义 < 和 == 运算符。在有序容器 (WAVLTree) 中使用时，对象将按升序存储。如果您想进一步掌控这一切，该怎么办？如果您的类型无法复制，或者您希望按降序而不是升序排序，该怎么办？

为此，您可以使用自定义键 trait 类。与自定义节点特征一样，您需要定义一个提供三个公共静态方法的结构体或类，这些方法可用于从对象中提取键并比较这些键。示例如下：

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-only-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)。Hashtables 使用链接列表链来解决冲突，因此其查找操作在技术上属于 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() 调用。

此外，在将其移除之前，无需在树中找到该对象。 给定对要更新的对象的引用，由于容器的干扰性，因此就知道对象在容器内部结构中的位置。