序列容器

fbl:: 提供兩個主要的容器系列：序列容器和關聯容器

序列容器是容器，元素的列舉順序取決於使用者從容器中明確新增和移除元素的方式。fbl:: 會定義兩種排序容器類型。

• SinglyLinkedList 是一個序列容器，支援僅前向疊代。
• DoublyLinkedList 是支援雙向疊代的序列容器。

在容器中加入和移除元素的方式，取決於序列容器和關聯容器的使用方式。本指南的本節將說明如何在序列容器中新增及移除元素。

如要進一步瞭解使用各種容器類型需要納入哪些檔案，請參閱設定建構依附元件。

在序列容器中新增元素

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

將元素插入序列容器

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