Adapter Containers

Adapter containers are specialized interfaces built on top of other STL containers, providing specific data access patterns. They implement common data structures like stacks, queues, and priority queues while hiding the complexity of the underlying container implementation.

What are Adapter Containers?

Adapter containers use the adapter pattern to provide a specific interface while delegating the actual storage and operations to an underlying container. They:

• Restrict access: Only allow operations that make sense for the data structure
• Provide semantics: Enforce LIFO (stack), FIFO (queue), or priority-based access
• Hide complexity: Abstract away the underlying container implementation
• Maintain efficiency: Operations are as fast as the underlying container allows

std::stack (LIFO)

Basic Usage

#include <stack>
#include <iostream>

// Create a stack (defaults to std::deque)
std::stack<int> number_stack;

// Push elements onto the stack
number_stack.push(1);
number_stack.push(2);
number_stack.push(3);

// Access the top element
std::cout << "Top element: " << number_stack.top() << std::endl;  // 3

// Remove the top element
number_stack.pop();  // Removes 3

// Check size and emptiness
std::cout << "Size: " << number_stack.size() << std::endl;  // 2
std::cout << "Empty: " << number_stack.empty() << std::endl;  // false

// Continue popping
number_stack.pop();  // Removes 2
number_stack.pop();  // Removes 1
std::cout << "Empty: " << number_stack.empty() << std::endl;  // true

Underlying Container and Customization

#include <stack>
#include <deque>
#include <list>

// Default: uses std::deque
std::stack<int> default_stack;

// Custom underlying container: std::deque
std::stack<int, std::deque<int>> deque_stack;

// Custom underlying container: std::list
std::stack<int, std::list<int>> list_stack;

// Why std::deque is the default:
// - O(1) push_back (stack push)
// - O(1) pop_back (stack pop)
// - O(1) back access (stack top)
// - No need for linked list overhead

Stack Operations

std::stack<std::string> name_stack;

// Push elements
name_stack.push("Alice");
name_stack.push("Bob");
name_stack.push("Charlie");

// Access top without removing
std::string top_name = name_stack.top();  // "Charlie"

// Safe access with bounds checking
if (!name_stack.empty()) {
    std::string safe_top = name_stack.top();
    std::cout << "Top name: " << safe_top << std::endl;
} else {
    std::cout << "Stack is empty" << std::endl;
}

// Pop all elements
while (!name_stack.empty()) {
    std::cout << "Popping: " << name_stack.top() << std::endl;
    name_stack.pop();
}

std::queue (FIFO)

Basic Usage

#include <queue>
#include <iostream>

// Create a queue (defaults to std::deque)
std::queue<int> number_queue;

// Enqueue elements
number_queue.push(1);
number_queue.push(2);
number_queue.push(3);

// Access front and back
std::cout << "Front: " << number_queue.front() << std::endl;  // 1
std::cout << "Back: " << number_queue.back() << std::endl;    // 3

// Dequeue elements
number_queue.pop();  // Removes 1
std::cout << "Front after pop: " << number_queue.front() << std::endl;  // 2

// Check size
std::cout << "Size: " << number_queue.size() << std::endl;  // 2

std::priority_queue (Heap)

Basic Usage

#include <queue>
#include <iostream>

// Create a priority queue (defaults to max-heap)
std::priority_queue<int> max_heap;

// Insert elements
max_heap.push(3);
max_heap.push(1);
max_heap.push(4);
max_heap.push(2);

// Access the maximum element
std::cout << "Maximum: " << max_heap.top() << std::endl;  // 4

// Remove the maximum element
max_heap.pop();  // Removes 4
std::cout << "New maximum: " << max_heap.top() << std::endl;  // 3

// Continue processing
while (!max_heap.empty()) {
    std::cout << "Processing: " << max_heap.top() << std::endl;
    max_heap.pop();
}

Custom Comparators and Containers

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

// Min-heap (smallest element first)
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

// Custom comparator for custom types
struct Task {
    std::string name;
    int priority;

    bool operator<(const Task& other) const {
        return priority < other.priority;  // Lower priority = higher in queue
    }
};

// Priority queue of tasks
std::priority_queue<Task> task_queue;

task_queue.push({"Low priority task", 1});
task_queue.push({"High priority task", 10});
task_queue.push({"Medium priority task", 5});

// Process tasks in priority order
while (!task_queue.empty()) {
    Task task = task_queue.top();
    std::cout << "Processing: " << task.name << " (priority: " << task.priority << ")" << std::endl;
    task_queue.pop();
}

// Custom underlying container
std::priority_queue<int, std::deque<int>> deque_heap;

Performance Comparison

Time Complexity

Container	Push	Pop	Top/Front/Back	Underlying Container
std::stack	O(1)	O(1)	O(1)	std::deque (default)
std::queue	O(1)	O(1)	O(1)	std::deque (default)
std::priority_queue	O(log n)	O(log n)	O(1)	std::vector (default)

Memory Overhead

// Compare memory usage
std::stack<int> stack;
std::queue<int> queue;
std::priority_queue<int> priority_queue;

// Add 1000 elements
for (int i = 0; i < 1000; ++i) {
    stack.push(i);
    queue.push(i);
    priority_queue.push(i);
}

// Memory overhead:
// - stack: minimal (just deque overhead)
// - queue: minimal (just deque overhead)
// - priority_queue: minimal (just vector overhead)
// - All adapters add negligible overhead beyond underlying container

When to Use Each Adapter

Use std::stack when:

• LIFO access needed: Last element added should be processed first
• Depth-first algorithms: DFS, backtracking, undo/redo systems
• Function call stacks: Recursion, call stack simulation
• Simple push/pop operations: No need for random access

Use std::queue when:

• FIFO access needed: First element added should be processed first
• Breadth-first algorithms: BFS, level-order traversal
• Task scheduling: Process tasks in order of arrival
• Buffering: First-come-first-served processing

Use std::priority_queue when:

• Priority-based processing: Highest priority element first
• Task scheduling: Process most important tasks first
• Event handling: Handle high-priority events first
• Heap operations: Need efficient max/min element access

Summary

Adapter containers provide specialized interfaces for common data structures:

std::stack (LIFO):

• Use for: Undo/redo, function calls, depth-first algorithms
• Operations: push(), pop(), top()
• Performance: O(1) for all operations
• Underlying: std::deque (default)

std::queue (FIFO):

• Use for: Task scheduling, breadth-first algorithms, buffering
• Operations: push(), pop(), front(), back()
• Performance: O(1) for all operations
• Underlying: std::deque (default)

std::priority_queue (Priority-based):

• Use for: Task scheduling, event handling, heap operations
• Operations: push(), pop(), top()
• Performance: O(log n) push/pop, O(1) top access
• Underlying: std::vector (default)

Key Benefits:

• Semantic clarity: Clear intent in code
• Restricted interface: Prevents misuse
• Efficient operations: Optimized for specific access patterns
• Flexible underlying: Can customize underlying container

When to Choose:

• Need LIFO: Use std::stack
• Need FIFO: Use std::queue
• Need priority-based: Use std::priority_queue
• Need random access: Use underlying container directly

Adapter containers are excellent examples of how the STL provides both efficiency and expressiveness by building specialized interfaces on top of general-purpose containers.

Questions

Q: What is the underlying container used by default in std::stack?

std::stack uses std::deque as its default underlying container. This choice provides O(1) push/pop operations at the top of the stack, which corresponds to the back of the deque. std::deque is ideal because it offers efficient back operations without the overhead of maintaining a linked list structure.

Q: What is the time complexity of finding the maximum element in std::priority_queue?

std::priority_queue provides O(1) access to the maximum element (top element) because it's implemented as a max-heap. The maximum element is always at the root of the heap, allowing constant-time access. However, insertion and removal operations are O(log n) due to heap rebalancing.

Q: Which container adapter would you use to implement a breadth-first search (BFS) algorithm?

std::queue is the correct choice for BFS because it follows the First-In-First-Out (FIFO) principle. In BFS, you process nodes in the order they were discovered (level by level), which requires a queue. std::stack would give you depth-first search (DFS), and std::priority_queue would process nodes by priority rather than discovery order.

Q: What happens when you try to access the top element of an empty std::stack?

Accessing the top element of an empty std::stack causes undefined behavior. Unlike std::vector's at() method which throws an exception, std::stack's top() method provides no bounds checking. It's the programmer's responsibility to check if the stack is empty using empty() before calling top().

Q: How can you change the underlying container of std::priority_queue to use std::vector instead of std::vector?

You can specify a custom underlying container as the second template parameter. std::priority_queue<int, std::vector<int>> creates a priority queue that uses std::vector as its underlying container. However, note that std::vector is actually the default, so this is equivalent to std::priority_queue<int>.