Sequence Containers

Sequence containers are linear collections of elements

Sequence containers are linear collections of elements. Conceptually, these are the equivalent of lists in other languages: list in Python or ArrayList in Java.

std::vector<T>

The most common kind of sequence container—indeed, probably the most common container type—is std::vector<T> which represents a list of elements of a type T.

Common operations

Pay special attention to v[i], which does not perform bounds checking on the vector. Attempting to index out of bounds results in undefined behaviour: simply put, your program may crash or silently continue in a seemingly random fashion.

The reason for this is that v[i] is an extremely common operation. Assuming that we write correct code, we should never attempt to access out-of-bounds elements. Checking if i is in-bounds would incur a small and unnecessary performance penalty which would be undesirable in performance-sensitive applications. If we need the extra peace-of-mind, however, we can opt into this by using the otherwise equivalent v.at(i).

Behind the scenes

At any point in time, std::vector manages a single block of memory large enough to hold all of its elements, and allocates a new block of memory (and frees the old one) when it requires more space. For example, consider this block of code:

std::vector<int> v { 1, 2, 3, 4 }; L1
v.push_back(5); L2
v.push_back(6); L3

std::deque<T>

An std::deque<T> (pronounced "deck") represents a double-ended queue of elements that supports efficient insertion/removal at both the front and back of the container.

Motivation

Sometimes using an std::vector<T> is just not fast enough. Suppose that you are working for an algorithmic finance company, and you must keep track of the last $100,000$ movements of a stock price that changes rapidly. Every time the price changes, you call the receive_price function with the latest price. Naturally, you decide to use an std::vector<T> to store the prices:

void receive_price(std::vector<double>& prices, double price) {
  prices.push_front(price);
  if (prices.size() > 100000)
    prices.pop_back();
}

This code as it's written wouldn't compile, since std::vector<T> doesn't have a push_front method. But let's imagine that it did:

void std::vector<T>::push_front(const T& value) {
  resize(size() + 1); L1
  for (size_t i = size() - 1; i > 0; --i) L2
    (*this)[i] = (*this)[i - 1];
  (*this)[0] = value; L3
}

L1 ensures the vector has extra space for the element, the loop at L2 moves every element in the vector forward by one, and finally L3 inserts the new value at the beginning of the vector.

You try deploying the receive_price function to track price changes and... you observe a massive spike in latency. The code simply takes too long to run! You speculate that it has something to do with the way push_front works, specifically the for loop at L2 which must shift all the elements forward by one. In fact, this is exactly the reason why C++ doesn't natively support a push_front method: if it were to exist, it would be egregiously slow.

A performant alternative

As it turns out, if you need to support efficient insertion at the front of a sequence container, std::vector<T> is just not the right tool for the job. This is a consequence of how std::vector<T> is implemented: since it maintains a single contiguous chunk of memory at all times, attempting to insert at the front requires advancing every element forward to make space for the new one.

std::deque<T> solves this problem by laying out its elements in a slightly different way that is more amenable to front-insertion. In our receive_price function, we can use an std::deque<double> instead:

void receive_price(std::deque<double>& prices, double price) {
  prices.push_front(price);
  if (prices.size() > 100000)
    prices.pop_back();
}

Now, the code not only compiles, but is lightning fast!

Common operations

std::deque<T>, despite being a "double-ended queue", is still a sequence container. In fact, it supports all of the operations that std::vector<T> supports, plus a few more:

Behind the scenes

The issue with std::vector<T> was its use of a single allocation: all of the elements must move after the point of insertion. std::deque<T> solves this by splitting up the allocation into multiple fixed-size allocations. To keep track of where the in-use region begins and ends, std::deque<T> uses a start and finish index (in reality, these are iterators, which are discussed in a later chapter, not indexes as shown below). Consider the following example:

std::deque<int> d { 4, 5, 6, 7, 8, 9 }; L1
d.push_front(3); L2
d.push_front(2); L3
d.push_front(1);
d.push_front(0);
d.push_front(-1);
d.push_front(-2); L4

An astute reader may wonder: if an std::deque<T> must double its blocks array (as shown at L3 above) when it runs out of space, how is this more performant than an std::vector<T>? In practice, the size of each block in a deque will range from several hundred to several thousand elements, depending on the type T. This effectively means that resizing the blocks array is hundreds to thousands of times faster than resizing the data array in a vector.

Despite splitting elements up across multiple allocations, std::deque<T> still supports getting elements by index, just like an std::vector<T>. In this example, to get d[i], one could look at the block in blocks at index (start + i) / 4 (using integer division), and then index (start + i) % 4 within that block. In actual practice, start and finish effectively store pointers directly to the first and last elements in the deque and so the implementation details may differ, but the same principles apply.

As a result, indexing into an std::deque<T> is slightly slower than an std::vector<T>, since it must follow two pointers (as opposed to one) to find an element. While a deque is more powerful than a vector in the sense that it supports all the operations of a vector and more, a vector should still be preferred over a deque unless your use-case requires efficient front insertion/removal.