Aside: Sequence Containers

std::vector is one example of a sequence container in C++. There are 5 such containers that each offer different performance attributes:

• std::array : fixed size contiguous storage.

  Complexity:

  • random access: \(\mathcal{O}(1)\)

  • insertion: not supported

• std::vector : automatically resizing array (as needed).

  Complexity:

  • random access: \(\mathcal{O}(1)\)

  • insertion at end: amortized constant \(\mathcal{O}(1)\)

  • insertion / removal elsewhere: \(\mathcal{O}(N)\) (actually depends on distance to the end)

• std::deque : a double-ended queue—this means that it is easy to add elements to either end. Data is not stored contiguously in memory.

  Complexity:

  • random access: \(\mathcal{O}(1)\)

  • insertion / removal at beginning or end: \(\mathcal{O}(1)\)

  • insertion / removal elsewhere: \(\mathcal{O}(N)\)

• std::list : this is a doubly-linked list. It is an easy operation to insert an element, but there is not random access to a particular element, instead you must walk through the list.

  Complexity:

  • random access: not supported

  • insertion / removal anywhere: \(\mathcal{O}(1)\)

• std::forward_list : this is a singly-linked list. You can only walk through in one direction.

  Complexity:

  • random access: not supported

  • insertion / removal anywhere: \(\mathcal{O}(1)\)