Containers: Stacks, Queues, & Deques

What are containers?

Containers are objects, classes, or a data structure that stores a collection of other objects/elements, and manages the operations and memory associated with them.

There are a couple of different types of containers, and a couple of distilled data structure descriptions that correspond with them. You don’t necessarily need to know what all of these are, just know that they exist & that they will be revisited.

1. Sequence Containers (Linear Data Structures)

Sequence containers, as the name implies, stores data in a linear pattern such that all of the elements can be accessed sequentially. Examples:

• Arrays: A fixed-sized contiguous block of memory.
• Vectors: A resizable array.
• Linked Lists: A chain of nodes containing data and pointers to the next [and/or previous] node.
• Deques: Fast insertions and deletions at the front & back of the data structure.

2. Ordered Associative Containers (Sorted/Key-Based)

Associative containers store data in some sorted order. They usually provide fast search, insertion, & deletion in O(log n) time. Usually, associative containers are implemented as balanced binary search trees, most commonly Red-Black trees. Examples:

• Sets: Collection of unique elements sorted by their values.
• Multiset: Same thing as a set, but allows multiple copies of the same value
• Maps: Collection of key-value pairs sorted in which no two pairs have the same key.
• Multimap: Same thing as a map except that multiple pairs can have the same keys.

3. Unordered Associative Containers (Hashed)

Unordered associative containers implement unsorted hashed data structures that can be searched quickly. I.e. O(1) on average, and O(n) worst case. Examples:

• Unordered Set: Collection of unique elements hashed by their values.
• Unordered Map: Collection of key-value pairs that are hashed by their keys, where no two pairs have the same key.

And the same goes for unordered multisets & multimaps: their implementation uses hashing instead of trees to organize their data.

Most of these definitions come directly from GeeksForGeeks article on containers

Stacks

A stack operates under the “Last in, first out” (LIFO) rule. The traditional analogy is “a stack of plates” (i.e. you take a plate from the top, not generally the middle). A couple of other examples include web browser’s “back” feature and the undo buttons in text editors.

The ADT for stacks is the following:

Let’s visualize this, though:

Implementations

Stacks are, by default, implemented with a std::deque (we’ll come back deques later). However, you can also pass in std::list (i.e. the STL’s doubly linked list), or std::vector (among others, also to be covered later.)

If we were to implement a stack ourselves, our complexity analysis would look something like this table:

*Averages out to constant with many pushes (amortized constant)

Keep in mind that linked lists will usually have higher memory overhead, so they’re not usually ideal.

Queues

Queues operate under the “First in, First out” (FIFO) principle. This is simple. If you’re the first in line, then you’re the first person “to be dealt with” (First item added, first one removed). Common examples are office hour queues, a fast food drive-through, or printer spooling (remember waiting for that dickhead to print 85 pages 3 minutes before your Lab starts? Your single sheet of paper was in the queue behind him.)

The ADT for queues is the following:

Let’s visualize this one too:

Implementations

At the University of Michigan, they showed an implementation of a circular (also called a ring) buffer that doubles when it fills up as a potential implementation for a queue. The usefulness of this example sort of runs out quickly because it produces neither a clean ring buffer nor a clean dynamic array, which makes it hard to learn the idioms of dynamic arrays AND circular buffers.

Fun Facts: Real ring buffers are fixed-capacity. Being bounded to a fixed size is the whole point of a ring buffer. Growing an array by doubling the capacity & copying the contents to a new array is the ‘dynamic-array’ idiom.

In practice you’d reach for std::deque for a growable queue, and if you want to understand ring buffers, study the fixed-capacity version where the interesting question is what happens when it fills.

But anyways, here is our complexity analysis of implementations (a std::queue defaults to a std::deque underneath, same as a stack):

*Averages out to constant with many pushes (amortized constant)

Deques

Deques aren’t really covered too heavily in EECS 281, but they’re used quite often. My opinion is that if you’re using something often, you should understand what it does.

So, let’s start here:

Why do stacks & queues use deques as their default implementations?

The answer… is container adapters!

Container adapters are wrappers around one of the sequence containers above that hide most of its interface and expose only the operations that make sense for a particular abstract data type. Importantly, stacks and queues are NOT sequence containers, but rather container adapters for a deque. For example, a stack is just a sequence where you’re only allowed to touch one end.

This makes a bit more sense when you actually look at a stripped down implementation for a std::stack:

template<class T, class Container = std::deque<T>>
class stack {
    protected:
        Container c;   // the ONLY data member

    public:
        void push(const T& x) { c.push_back(x); }
        void pop()            { c.pop_back(); }
        T& top()              { return c.back(); }
        bool empty() const    { return c.empty(); }
        size_t size() const   { return c.size(); }
    };

You can see it’s literally just a deque wrapped up and called a stack, and the stack class only exposes the methods it wants you to use (push, pop, top, empty, size)

The STL has three container adapters: std::stack, std::queue, and std::priority_queue. C++23 added std::flat_map/std::flat_set and their multi variants, which adapt a sorted vector into a map/set interface.

The key idea: the ADT (what operations exist) is separated from the implementation (how the data is actually laid out). You pick the underlying container; the adapter supplies the interface. Stacks and queues, rather than write their own implementations, just use deques as they’re already optimal for fast insertion & removal from the front & back.

So, why is this the default?

A stack only touches the back. A queue touches the front & the back. A vector has no pop_front at all (erasing the front shifts everything down, and std::queue on top of a vector won’t even compile), and a linked list can pop the front, but it pays a malloc & a couple of pointers for every single element. A deque does one malloc per 128 ints & never moves an element, so both ends are constant time. On top of that, pointers & references to elements stay valid when you push at either end (iterators don’t, since the map can move).

How does a deque work tho?

So this is how the ADT gives a deque to you functionally:

Here is the more clinically accurate visualization of a deque, however:

Now, we’ll dig into the specifics of that visual.

Map & Chunks

The shit going on under the hood is actually pretty clever. It starts with a plain array of pointers, your map (no relation to std::map, it’s literally just an array). Each pointer in the map points at a chunk (also called a block). libstdc++ itself calls them nodes, & calls the chunk size the buffer size, so if you go digging through the header, grep for node & buf, not chunk.

These chunks are created dynamically in memory. Usually, they will be about 512 bytes in size (so they can store about 128 integers, which are 4 bytes each, per chunk). The 512 is libstdc++‘s number (GCC’s standard library), & it isn’t uniform across implementations: libc++ uses 4096 bytes & MSVC uses 16, for example.

Ermmm what if we have an item over 512 bytes that we need to store in a chunk????

Well, the chunk size isn’t always 512 bytes. Technically, it’s “however many items fit in 512 bytes, but at least 1.” That’s actually this bit of code from the STL:

#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512 // chunk size: 512 bytes
#endif

  _GLIBCXX_CONSTEXPR inline size_t
  __deque_buf_size(size_t __size)
  { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
            ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

// that return statement is hard to read because of ternary operators, so this is expanded version of that code:
if (item_size < 512) {
  // fit as many as possible into 512 bytes.
  return 512 / item_size;
} else { // one item per chunk.
  return 1;
}

So a rough table for chunk sizing & items per chunk:

The chunk is always items_per_chunk × item_size, so a 2000-byte item gets a 2000-byte chunk. Nothing gets split or cut off. In reality, though, if you’re exceeding that 512 bytes, it might be worth considering storing pointers to items within the deque rather than the raw items themselves.

Front & back?

A deque only has to remember two spots: start (the front element) & finish (the cell after the back element, where the next push_back lands). Each one is just a map slot plus a cell inside that chunk, and front(), back() & size() all fall out of those two. Both are drawn in the figure, with their two numbers printed under the map.

A push writes into the next free cell at its end: finish’s cell for push_back, the cell before start for push_front. When that chunk has no cell left to give, the deque grabs one new chunk, drops its pointer into the next map slot, & carries on. (finish always has to point at a real cell, so the push_back that fills a chunk’s last cell grabs the next chunk right then.) A pop does the reverse & frees a chunk once nothing is left in it. Nothing already in the deque ever moves, which is the whole trick.

Try it in the figure: push_back three times & watch chunk c appear the moment b fills, with finish parked on it. Then push_front once & watch a chunk appear above a, filled from its far end. That’s why the first chunks start in the middle of the map, there’s room to grow both ways.

When one end hits the edge of the map, the deque slides its pointers back to the middle if the map is mostly empty, or allocates a bigger map & copies the pointers across. Pointers, never elements. A million ints is under 8,000 pointers, so even that copy is nothing. Hit at() in the figure for the indexing: map slot, then cell, two hops, constant time.