序列容器

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