Container Adapters

The adapter pattern is a widely used, categorized design pattern for reusable code that converts one class's interface into a different interface expected by client code.

In the C++ STL standard library, stack and queue can store elements just like native containers, but they are not classified as full containers. Instead, they are called container adapters, because they only wrap the interface of another existing underlying container. By default, STL stack and queue use deque as their underlying implementation.

Deque Double-Ended Queue

Deque is a hybrid data structure that combines the advantages of both vector and linked list.

• Vector advantages: Fast subscript random access, high efficiency
• Vector disadvantages: High resizing overhead, very poor efficiency for insertions and deletions at the head
• Linked list advantages: Allocates and frees memory on demand, good efficiency for insertions and deletions anywhere in the sequence
• Linked list disadvantages: Low efficiency for subscript random access

Deque supports subscript access, which is acceptably efficient for small data volumes. For large amounts of random access however, its performance drops significantly. Insertions and deletions in the middle of a deque are also inefficient because they require shifting existing data. Deque excels at insertions and deletions at both the head and tail, making it an ideal default adapter container for stack and queue.

Why Deque is Selected as the Default Underlying Container

1. Stack and queue do not need to support traversal (so neither stack nor queue expose iterators), they only require operasions at one or both fixed ends of the sequence.
2. When a stack grows in size, deque is more efficient then vector because it does not need to move large amounts of existing data during expansion. When a queue grows, deque delivers both higher efficiency and better memory utilization than alternative containers.

Simulated Stack Implementation

// Neither stack nor queue expose iterators, to block unsupported random access
// Adapters provide a uniform interface for accessing containers, encapsulating and hiding underlying implementation details
template<class T, class UnderlyingContainer = deque<T>>
class stack
{
public:
    bool empty() const
    {
        return _container.empty();
    }
    size_t size() const
    {
        return _container.size();
    }
    T& top()
    {
        return _container.back();
    }
    const T& top() const
    {
        return _container.back();
    }
    void push(const T& value)
    {
        _container.push_back(value);
    }
    void pop()
    {
        _container.pop_back();
    }
private:
    UnderlyingContainer _container;
};

Simulated Queue Implementation

// Vector is unsuitable as underlying container here because front deletion is very inefficient
template<class T, class UnderlyingContainer = deque<T>>
class queue
{
public:
    bool empty() const
    {
        return _container.empty();
    }
    size_t size() const
    {
        return _container.size();
    }
    T& front()
    {
        return _container.front();
    }
    const T& back() const
    {
        return _container.back();
    }
    void push(const T& value)
    {
        _container.push_back(value);
    }
    void pop()
    {
        _container.pop_front();
    }
private:
    UnderlyingContainer _container;
};

Implementing stack and queue is far simpler than implementing standalone containers like list or vector, thanks to the adapter pattern that reuses existing tested container functionality.