Bytebook Compiler

Beyond the Basics

STL Containers

The Standard Template Library's ready-made data structures: vector, list, deque, stack, queue, priority_queue, set, map and their unordered versions — with costs.

4 min read4 runnable examples4-question quiz

The Standard Template Library (STL) gives you tested, fast implementations of every structure from the Data Structures course. It has three parts: containers (data structures), iterators (a uniform way to walk through containers) and algorithms (sort, search and more — next lesson).

vector: the default container

A vector is a dynamic array: contiguous memory that grows as needed (the realloc doubling trick from C, done for you).

C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 3, 8};
    v.push_back(1);                       // add at the end: amortised O(1)
    v.push_back(9);
    cout << "size " << v.size() << ", front " << v.front() << ", back " << v.back() << endl;
    v.insert(v.begin() + 1, 42);          // insert at index 1: O(n)
    v.pop_back();                         // remove the last element
    v.erase(v.begin());                   // remove the first element: O(n)
    for (int x : v) cout << x << " ";
    cout << endl;

    vector<vector<int>> grid(3, vector<int>(4, 0));   // 3x4 matrix of zeros
    grid[1][2] = 7;
    cout << "grid[1][2] = " << grid[1][2] << ", rows " << grid.size() << endl;
    return 0;
}
Output
size 5, front 5, back 9
42 3 8 1 
grid[1][2] = 7, rows 3
Try it Yourself

Stack, queue and priority_queue

These are container adapters with a restricted interface — exactly the ADTs from Data Structures:

C++
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    stack<int> s;
    for (int i = 1; i <= 3; i++) s.push(i);
    cout << "stack pops:";
    while (!s.empty()) { cout << " " << s.top(); s.pop(); }

    queue<string> q;
    q.push("first"); q.push("second"); q.push("third");
    cout << "\nqueue pops:";
    while (!q.empty()) { cout << " " << q.front(); q.pop(); }

    priority_queue<int> maxHeap;                                  // largest on top
    priority_queue<int, vector<int>, greater<int>> minHeap;       // smallest on top
    for (int x : {40, 10, 70, 30}) { maxHeap.push(x); minHeap.push(x); }
    cout << "\nmax-heap top: " << maxHeap.top() << ", min-heap top: " << minHeap.top() << endl;
    return 0;
}
Output
stack pops: 3 2 1
queue pops: first second third
max-heap top: 70, min-heap top: 10
Try it Yourself

set and map

set stores unique keys in sorted order; map stores sorted key → value pairs. Both are balanced binary search trees (red-black trees): O(log n) insert, find and erase.

C++
#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;

int main() {
    set<int> s = {5, 1, 5, 3, 1, 9};          // duplicates ignored
    s.insert(4);
    cout << "set:";
    for (int x : s) cout << " " << x;          // always sorted
    cout << "\ncontains 3? " << (s.count(3) ? "yes" : "no") << endl;

    map<string, int> marks;
    marks["Asha"] = 91;
    marks["Ravi"] = 78;
    marks["Meera"] = 85;
    marks["Ravi"] += 5;                        // update
    for (const auto &[name, m] : marks)        // sorted by key
        cout << name << ": " << m << endl;
    if (marks.find("Zoya") == marks.end()) cout << "Zoya not found" << endl;
    return 0;
}
Output
set: 1 3 4 5 9
contains 3? yes
Asha: 91
Meera: 85
Ravi: 83
Zoya not found
Try it Yourself

unordered_map: hash tables

unordered_map and unordered_set are hash tables: O(1) average lookup, but no ordering. Perfect for counting:

C++
#include <iostream>
#include <unordered_map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string text = "the cat and the dog and the bird";
    unordered_map<string, int> freq;
    stringstream ss(text);
    string word;
    while (ss >> word) freq[word]++;           // missing keys start at 0
    for (string w : {"the", "and", "cat", "fish"})
        cout << w << ": " << freq[w] << endl;
    return 0;
}
Output
the: 3
and: 2
cat: 1
fish: 0
Try it Yourself

Choosing a container

Container Underlying structure Access Insert/erase Find
vector dynamic array O(1) by index O(1) at end, O(n) elsewhere O(n)
deque blocks of arrays O(1) by index O(1) at both ends O(n)
list doubly linked list O(n) O(1) with an iterator O(n)
stack / queue adapter (deque by default) top / front only O(1) —
priority_queue binary heap top only O(log n) —
set / map red-black tree — O(log n) O(log n), sorted
unordered_set / unordered_map hash table — O(1) average O(1) average

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    Which container is a dynamic array?

  2. 2

    What does iterating over a std::map<string, int> produce?

  3. 3

    What is the average lookup cost in unordered_map?

  4. 4

    Which declaration creates a min-heap of ints?

Esc
↑↓ move↵ open