依序播放的容器

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 将其引用转移至容器。

将元素推送到按顺序排列的容器中

推送方法的行为符合预期,会添加新元素并将其设为新元素 序列中的前部或后部元素(即,第一个或 枚举顺序中的最后一个元素)。例如:

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");

将元素插入按顺序排列的容器中

insertinsert_after 均在 排名紧随其前 (insert) 或紧随其后 (insert_after) 迭代器。begin()end() 都可以作为 insert 的迭代器,其功能等同于仅指定 push_frontpush_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();