50. STL Adapter Containers

Definition

STL adapter containers are containers that wrap another container to provide a more limited but more appropriate interface for certain use cases. The three main adapters are stack (LIFO), queue (FIFO), and priority_queue (heap-based).

Adapters don't store data directly — they use an underlying container (default: deque for stack/queue, vector for priority_queue) and restrict access to only certain operations. This restriction ensures correct usage and prevents bugs caused by unintended access.

stack — Last In, First Out (LIFO)

stack is an adapter container that only allows access from one end (the top). The LIFO principle: the last element inserted is the first one removed.

Code Example

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> tumpukan;

    // Push — add an element on top
    tumpukan.push("File A");
    tumpukan.push("File B");
    tumpukan.push("File C");

    // Top — look at the top element
    cout << "Top: " << tumpukan.top() << endl;

    // Pop — remove the top element
    tumpukan.pop();
    cout << "After pop: " << tumpukan.top() << endl;

    // Size — number of elements
    cout << "Size: " << tumpukan.size() << endl;

    // Check if empty
    cout << "Empty: " << (tumpukan.empty() ? "Yes" : "No") << endl;

    // Iteration (requires a copy because stack has no iterators)
    stack<string> temp = tumpukan;
    cout << "\nIsi stack:" << endl;
    while (!temp.empty()) {
        cout << "  " << temp.top() << endl;
        temp.pop();
    }

    return 0;
}

Code Explanation

• push() adds an element to the top position.
• top() returns a reference to the top element without removing it.
• pop() removes the top element — it does not return a value.
• empty() checks whether the stack is empty — always check this before top() or pop().

Everyday Use Cases: Undo System

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class TextEditor {
    stack<string> undoStack;
    stack<string> redoStack;
    string current = "";

public:
    void type(const string& text) {
        undoStack.push(current);
        current += text;
        redoStack = stack<string>(); // clear redo
        cout << "Text: " << current << endl;
    }

    void undo() {
        if (!undoStack.empty()) {
            redoStack.push(current);
            current = undoStack.top();
            undoStack.pop();
            cout << "Undo -> " << current << endl;
        } else {
            cout << "Nothing to undo" << endl;
        }
    }

    void redo() {
        if (!redoStack.empty()) {
            undoStack.push(current);
            current = redoStack.top();
            redoStack.pop();
            cout << "Redo -> " << current << endl;
        } else {
            cout << "Nothing to redo" << endl;
        }
    }
};

int main() {
    TextEditor editor;
    editor.type("Hello");
    editor.type(" World");
    editor.undo();
    editor.redo();
    editor.type("!");
    editor.undo();
    editor.undo();
    editor.undo();

    return 0;
}

Conclusion

A stack is ideal for undo/redo systems, expression evaluation, browser history navigation, and bracket-matching parsing.

queue — First In, First Out (FIFO)

queue is an adapter container that adds elements at the back and removes them from the front. The FIFO principle: the first element in is the first one out.

Code Example

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> antrian;

    // Push — add an element to the back
    antrian.push("Pelanggan 1");
    antrian.push("Pelanggan 2");
    antrian.push("Pelanggan 3");

    // Front — look at the front element
    cout << "Served: " << antrian.front() << endl;

    // Back — look at the back element
    cout << "Last: " << antrian.back() << endl;

    // Pop — remove the front element
    antrian.pop();
    cout << "After service: " << antrian.front() << endl;

    cout << "Remaining queue: " << antrian.size() << endl;

    return 0;
}

Code Explanation

• push() adds an element to the back of the queue.
• front() returns the front element (first in).
• back() returns the back element (last in).
• pop() removes the front element — it does not return a value.

Everyday Use Cases: Print Queue

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct PrintJob {
    string fileName;
    int pageCount;
};

class PrintQueue {
    queue<PrintJob> jobs;

public:
    void addJob(const string& file, int pages) {
        jobs.push({file, pages});
        cout << "Added: " << file << " (" << pages << " pages)" << endl;
    }

    void processNext() {
        if (!jobs.empty()) {
            PrintJob job = jobs.front();
            jobs.pop();
            cout << "Printing: " << job.fileName
                 << " (" << job.pageCount << " pages)..." << endl;
        } else {
            cout << "No such job" << endl;
        }
    }

    int pendingJobs() {
        return jobs.size();
    }
};

int main() {
    PrintQueue pq;
    pq.addJob("Report.pdf", 5);
    pq.addJob("Invoice.docx", 2);
    pq.addJob("Presentasi.pptx", 15);

    while (pq.pendingJobs() > 0) {
        pq.processNext();
    }

    return 0;
}

Conclusion

A queue is suitable for printer queues, ordering systems, BFS traversal, and the producer-consumer pattern.

priority_queue — Heap-Based

priority_queue is a heap-based adapter container. The element with the highest priority (default: largest value) is always at the top position.

Code Example

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Max heap (default)
    priority_queue<int> maxHeap;
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(50);
    maxHeap.push(20);
    maxHeap.push(40);

    cout << "Max Heap (largest first):" << endl;
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    // Min heap
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(50);
    minHeap.push(20);
    minHeap.push(40);

    cout << "Min Heap (smallest first):" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

Code Explanation

• priority_queue<int> uses a max heap — the largest element is on top.
• priority_queue<int, vector<int>, greater<int>> uses a min heap.
• top() returns the element with the highest priority.
• pop() removes the top element.
• There is no front() or back() — only top().

Everyday Use Cases: Task Scheduler

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Task {
    string name;
    int priority; // 1-10, 10 = most important

    // Operator for priority_queue (max heap based on priority)
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

int main() {
    priority_queue<Task> scheduler;

    scheduler.push({"Backup database", 3});
    scheduler.push({"Fix critical bug", 10});
    scheduler.push({"Update documentation", 1});
    scheduler.push({"Deploy hotfix", 9});
    scheduler.push({"Code review", 5});

    cout << "Task execution order:" << endl;
    int order = 1;
    while (!scheduler.empty()) {
        Task t = scheduler.top();
        scheduler.pop();
        cout << order++ << ". [" << t.priority << "] " << t.name << endl;
    }

    return 0;
}

Conclusion

A priority_queue is ideal for schedulers, Dijkstra's algorithm, median finding, and priority-based systems.

Adapters and Underlying Containers

Each adapter uses an underlying container by default, but it can be configured:

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <list>
using namespace std;

int main() {
    // Stack with vector as the underlying container
    stack<int, vector<int>> stackVec;
    stackVec.push(10);
    stackVec.push(20);
    cout << "Stack (vector): " << stackVec.top() << endl;

    // Queue with list as the underlying container
    queue<string, list<string>> queueList;
    queueList.push("A");
    queueList.push("B");
    cout << "Queue (list): " << queueList.front() << endl;

    // Priority queue with deque as the underlying container
    priority_queue<int, deque<int>> pqDeque;
    pqDeque.push(100);
    pqDeque.push(50);
    cout << "Priority Queue (deque): " << pqDeque.top() << endl;

    return 0;
}

Code Explanation

• The adapter's second template parameter determines the underlying container:
• Stack default: deque
• Queue default: deque
• Priority queue default: vector
• The choice of underlying container affects performance and memory usage.

Comparing Adapter Containers

When to Use an Adapter?

Summary

Adapter containers provide the right abstraction for specific data access patterns. Stack enforces LIFO, queue enforces FIFO, and priority_queue guarantees access by priority. By limiting the available operations, adapters prevent bugs and make code easier to understand. Choosing the underlying container allows optimization based on specific needs.