Container adapters

std::stack, std::queue, and std::priority_queue are container adaptors. The standard uses the word "adaptor" rather than "adapter", but the idea is the same. Each one takes an existing sequence container and exposes a narrower interface with a different contract.

The shape

A container adaptor owns the underlying container and forwards a small set of operations. It does not inherit from the container, and it does not expose the container's iterators or the rest of its interface.

#include <deque>
#include <stack>
#include <vector>

std::stack<int> stack;                  // std::deque<int> by default
std::stack<int, std::vector<int>> fast; // std::vector<int>

The default container is std::deque<T>. You can supply another one as the second template argument if it meets the adaptor's requirements.

A stack built by hand

The standard std::stack is a good model for your own adapters. It wraps a container, exposes only the operations that make sense for a stack, and lets the caller choose the storage.

#include <cstddef>
#include <deque>
#include <utility>

template<typename T, typename Container = std::deque<T>>
class Stack {
public:
    void push(const T& value) {
        data_.push_back(value);
    }

    void push(T&& value) {
        data_.push_back(std::move(value));
    }

    void pop() {
        data_.pop_back();
    }

    T& top() {
        return data_.back();
    }

    const T& top() const {
        return data_.back();
    }

    bool empty() const {
        return data_.empty();
    }

    std::size_t size() const {
        return data_.size();
    }

private:
    Container data_;
};

Usage is the same as with the standard type:

Stack<int> values;
values.push(1);
values.push(2);
values.push(3);

while (!values.empty()) {
    std::cout << values.top() << ' ';
    values.pop();
}

Output:

3 2 1

Why not inherit from the container

Deriving from std::vector looks shorter, but it exposes the whole vector interface:

class BadStack : public std::vector<int> {
public:
    void push(int value) { push_back(value); }
    int pop() { int value = back(); pop_back(); return value; }
};

A caller can now call insert, erase, operator[], or take iterators and break the stack invariant. The adapter has stopped adapting anything. It is just a vector with two extra methods. Composition keeps the invariant enforceable.

The three standard adaptors

std::stack gives last-in, first-out access. It needs back, push_back, and pop_back. std::deque is the default because it grows at both ends without invalidating references as often as a vector can.

std::queue gives first-in, first-out access. It needs front, back, push_back, and pop_front. std::deque is again the default. std::list also works.

std::priority_queue keeps the largest element on top by default. It needs random access, front, push_back, pop_back, and the heap operations. std::vector is the default, and a custom comparator changes the order:

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

Writing your own container adapter

Keep the wrapper thin and the contract explicit:

• Store the container by value unless you have a reason to borrow it.
• Accept the container as a template parameter with a sensible default.
• Expose only the operations that preserve the adaptor's invariant.
• Do not hand out iterators unless the adapted interface actually needs them.
• Document what happens when the container throws, especially if the adaptor holds a lock.

The last point matters when the adaptor does more than forward calls. A thread-safe queue, for example, cannot hold a mutex across a call that may block or throw without thinking about ownership and lock order.

When to use a container adapter

Use one when an existing container has the storage you need but the interface is too wide. A stack, a queue, or a bounded buffer should not let callers erase from the middle or walk the storage. The adapter makes that impossible.

Avoid it when callers need the full container interface. Wrapping a vector in a class that exposes begin, end, operator[], insert, and erase gives you the cost of a wrapper with none of the restriction. Use the container directly.

Summary

Container adaptors are object adapters with value semantics. They own a container, forward a small set of operations, and hide the rest. The standard library's stack, queue, and priority queue are good templates for your own wrappers because they show where to stop: expose the contract, not the storage.