Sequenced containers

fbl:: offers two main families of containers, sequenced containers and associative containers

Sequenced containers are containers where the enumeration order of elements is determined by by how a user specifically added and removed elements to and from the container. fbl:: defines two types of sequenced containers.

SinglyLinkedList is a sequenced container that supports forward-only iteration.
DoublyLinkedList is a sequenced container that supports bi-directional iteration.

The main differences between how sequenced containers and associative containers are used comes down to how elements are added to and removed from the container. This section of the guide will show you how you can add and remove elements to and from sequenced containers.

Please refer to Setting up build dependencies for details on which files need to be included in order to use the various container types.

Adding elements to a sequenced container

SinglyLinkedList provides two methods for adding elements to the container. They are:

push_front(Ptr)
insert_after(Iter, Ptr)

DoublyLinkedList supports these methods as well, but also adds the following methods.

push_back(Ptr)
insert(Iter, Ptr)
splice(Iter, List)

As always, it is an error to attempt to add an element to a container if the node state used by that container type is already a member of a container. When using managed pointer types, users may either give a container its own reference to an object by providing the pointer instance by value, or may transfer their reference to the container using std::move.

Pushing elements into a sequenced container

The push methods behave as expected, adding a new element and making it the new front or or back element in the sequence (in other words, either the first or the last element in the enumeration order). For example:

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

Inserting elements into a sequenced container

insert and insert_after both insert an element into the container in a position either immediately before (insert) or immediately after (insert_after) the iterator. Either begin() or end() may be provided as the iterator for insert, which is functionally equivalent to saying simply push_front or push_back. It is an error to call insert_after with an iterator that does not reference an element, therefore insert_after will only accept a container's begin() when the container is non-empty, and will never accept end(). Continuing the previous example:

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

Combining sequenced containers using `splice`

Finally, splice will take the contents of a provided list and splice them into a position immediately before an iterator in another list. After finishing, the source list will be empty, having transferred all of its elements to the destination list. The source and destination lists must be different list instances, but must also be the same type of list (e.g. they must use the same node storage). begin() and end() are both valid targets in the destination list. The former will prepend the elements from the source to the destination, while the latter will append. Finishing the previous example:

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

Removing elements from a sequenced container

SinglyLinkedList provides three methods for removing elements from a container. They are:

pop_front()
erase_next(Iter)
clear()

DoublyLinkedList supports these methods as well, but also adds the following methods.

pop_back(Ptr)
erase(Iter or Obj&)

With the exception of clear(), all of these methods return a pointer of the container's pointer type to the user, returning the user's reference to the object (when using managed pointers) to the user in the process. In the event that there is no element at the specified position, nullptr is returned instead. In the specific case of erase_next, it is illegal to pass an invalid iterator. The iterator must refer to at least some element in the container. Finally, the erase operation works with either a iterator to an element, which is a member of the list, or with a T& style reference to the object itself. Objects do not have to be discovered using iterators in order to be directly erased.

Continuing from the example stared in the previous section:

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

Sequenced containers

Adding elements to a sequenced container

Pushing elements into a sequenced container

Inserting elements into a sequenced container

Combining sequenced containers using splice

Removing elements from a sequenced container

Combining sequenced containers using `splice`