← C++ roadmap

Topic 7 of 27 · Intermediate

STL Containers

vector, map, unordered_map, set, deque, stack, queue, priority_queue.

Concept

The STL provides tested containers. vector is the default choice: contiguous, cache-friendly, amortised O(1) push_back.

map/set are red-black trees (sorted, O(log n)); unordered_map/unordered_set are hash tables (average O(1)).

Adapters: stack, queue and priority_queue (max-heap by default; use greater<> for min-heap).

Cheat sheet

ContainerLookupOrdered?
vectorO(1) indexInsertion order
map / setO(log n)Sorted
unordered_mapO(1) avgNo
dequeO(1) both endsInsertion order
priority_queueO(1) top, O(log n) pushHeap

Code (C++20)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v{5, 3, 8};
    v.push_back(1);

    unordered_map<string, int> freq;
    for (string w : {"a", "b", "a"}) freq[w]++;

    map<int, string> ranks{{2, "Ravi"}, {1, "Asha"}};   // sorted by key
    set<int> uniq(v.begin(), v.end());

    priority_queue<int, vector<int>, greater<int>> minHeap(v.begin(), v.end());
    cout << minHeap.top() << ' ' << freq["a"] << ' ' << ranks.begin()->second << '\n';
}

Remember

  • vector by default.
  • operator[] on map inserts missing keys — use find/contains to check.
  • reserve() avoids repeated reallocations.

Interview questions

map vs unordered_map?

map is a sorted red-black tree with O(log n) operations; unordered_map is a hash table with average O(1) but no order and worst case O(n).

How does vector grow?

When full it allocates a bigger block (usually 1.5–2×), moves elements over and frees the old block, giving amortised O(1) push_back.

Practise C++ with the AI mentor

Lesson test

Take an 8-question test on “STL Containers” — concepts, output prediction, bug spotting and interview questions.

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.