依序播放的容器

fbl:: 提供两大类容器：顺序容器和关联容器

顺序容器是指元素的枚举顺序由用户向容器中添加和从容器中移除元素的方式决定的容器。fbl:: 定义了两种有序容器。

  • SinglyLinkedList 是一个有序容器，支持单向迭代。
  • DoublyLinkedList 是一个支持双向迭代的有序容器。

顺序容器和关联容器的使用方式之间的主要区别在于向容器中添加和从容器中移除元素的方式。本指南的这一部分将向您介绍如何向排序容器添加和从中移除元素。

如需详细了解需要包含哪些文件才能使用各种容器类型，请参阅设置 build 依赖项。

向排序容器添加元素

SinglyLinkedList 提供了两种向容器添加元素的方法。它们是：

  1. push_front(Ptr)
  2. insert_after(Iter, Ptr)

DoublyLinkedList 也支持这些方法，但还添加了以下方法。

  1. push_back(Ptr)
  2. insert(Iter, Ptr)
  3. splice(Iter, List)

与往常一样，如果该容器类型使用的节点状态已是容器的成员，则尝试向容器添加元素会出错。使用受管理的指针类型时，用户可以通过按值提供指针实例，将自己的对象引用提供给容器，也可以使用 std::move 将其引用转移到容器。

将元素推送到顺序容器中

push 方法会按预期运行，添加新元素并将其设为序列中的新前端或后端元素（换句话说，枚举顺序中的第一个或最后一个元素）。例如：

struct Tag1 {};
struct Tag2 {};
class Obj : public fbl::RefCounted<Obj>,
            public fbl::ContainableBaseClasses<
              fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Obj>, Tag1>,
              fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Obj>, Tag2>
            > {
 public:
  explicit Obj(int val) : val_(val) {}
  int val() const { return val_; }
 private:
  const int val_;
};

TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag1> stack_like;
TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag2> queue_like;

for (int i = 0; i < 5; ++i) {
  fbl::RefPtr<Obj> obj_ref = fbl::AdoptRef(new Obj(i));
  stack_like.push_front(obj_ref);            // Copy our reference
  queue_like.push_back(std::move(obj_ref));  // Transfer our reference
}

// Prints "4 3 2 1 0 "
for (const auto& obj : stack_like) { printf("%d ", obj.val()); }
printf("\n");

// Prints "0 1 2 3 4 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");

将元素插入到排序容器中

insert 和 insert_after 都会将元素插入到迭代器的紧前 (insert) 或紧后 (insert_after) 的位置。您可以将 begin() 或 end() 作为 insert 的迭代器提供，这在功能上等同于直接使用 push_front 或 push_back。使用不引用元素的迭代器调用 insert_after 是错误的，因此 insert_after 仅在容器不为空时接受容器的 begin()，并且绝不接受 end()。继续上例：

queue_like.insert(queue_like.begin(), fbl::MakeRefCounted<Obj>(100));
queue_like.insert(queue_like.end(), fbl::MakeRefCounted<Obj>(500));
for (auto iter = queue_like.begin(), iter != queue_like.end(); ++iter) {
  if (iter->val() == 2) {
    queue_like.insert(iter, fbl::MakeRefCounted<Obj>(200));
    queue_like.insert_after(iter, fbl::MakeRefCounted<Obj>(300));
    break;
  }
}

// Prints "100 0 1 200 2 300 3 4 500 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");

使用 splice 组合已排序的容器

最后，splice 会获取所提供列表的内容，并将其接合到另一个列表中迭代器前面的位置。完成后，源列表将变为空列表，因为其所有元素都已转移到目标列表。源列表和目标列表必须是不同的列表实例，但也必须是同一类型的列表（例如，它们必须使用相同的节点存储）。begin() 和 end() 都是目标列表中的有效目标。前者会将源中的元素附加到目标的开头，而后者会附加到目标的末尾。完成上一个示例：

TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag2> tmp;

tmp.push_front(fbl::MakeRefCounted<Obj>(-1));
tmp.push_front(fbl::MakeRefCounted<Obj>(-2));
queue_like.splice(queue_like.begin(), tmp);

tmp.push_back(fbl::MakeRefCounted<Obj>(1000));
tmp.push_back(fbl::MakeRefCounted<Obj>(2000));
queue_like.splice(queue_like.end(), tmp);

tmp.push_back(fbl::MakeRefCounted<Obj>(50));
tmp.push_back(fbl::MakeRefCounted<Obj>(60));
for (auto iter = queue_like.begin(), iter != queue_like.end(); ++iter) {
  if (iter->val() == 300) {
    queue_like.splice(iter, tmp);
    break;
  }
}

// Prints "-2 -1 100 0 1 200 2 50 60 300 3 4 500 1000 2000 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");

从排序容器中移除元素

SinglyLinkedList 提供了三种从容器中移除元素的方法。它们是：

  • pop_front()
  • erase_next(Iter)
  • clear()

DoublyLinkedList 也支持这些方法，但还添加了以下方法。

  • pop_back(Ptr)
  • erase(Iter or Obj&)

除了 clear() 之外，所有这些方法都会向用户返回容器的指针类型的指针，并在此过程中向用户返回用户对对象的引用（使用受管理的指针时）。如果指定位置没有元素，则改为返回 nullptr。在 erase_next 的具体示例中，传递无效的迭代器是非法的。迭代器必须至少引用容器中的某些元素。最后，擦除操作可与指向列表成员的元素的迭代器或指向对象本身的 T& 风格引用搭配使用。您不必使用迭代器发现对象，即可直接将其擦除。

接续上一部分中开始的示例：

// Remove the object with val "-2" and hold a reference to it in |removed|.
auto removed = queue_like.pop_front();

// Remove the object with val "2000" and drop the reference, allowing the object
// to destruct.
queue_like.pop_back();

// Begin refers to the "-1" element, so erase_next will remove the "100" element
queue_like.erase_next(queue_like.begin());

// remove all of the elements in the list that are not in ascending order,
// relative to the previous element. Hold a reference to element 200 as we pass
// it.
fbl::RefPtr<Obj> e200;
for (auto iter = queue_like.begin(); iter.IsValid(); ) {
  auto tmp = iter++;

  if (iter->IsValid() && (tmp->val() > iter->val())) {
    queue_like.erase(iter);
    iter = tmp;
  } else if (tmp->val() == 200) {
    e200 = tmp.CopyPointer();
  }
}

// List is now "-1 0 1 200 300 500 1000". Remove 200 from the list using the
// object reference we held instead of an iterator.
queue_like.erase(*e200);

// Finally, just clear the list.
queue_like.clear();