LearnFrenzy
Sign in Take a free test

C++ Programming · Topic 19 of 27

STL Containers

  • 4 exercises
  • 60 questions
  • ~60 min
  • Answers explained

Introduction & Syntax

STL Containers · Study material

STL containers are the ready-made data structures of the C++ Standard Library: dynamic arrays, linked lists, balanced trees, hash tables, stacks, queues and heaps, all as class templates that work with any element type. Choosing the right container is one of the most important decisions in a C++ program – it decides whether a lookup takes a microsecond or a second – and it is a favourite topic in coding interviews and competitive programming. This page explains every standard container with programs you can run: vector, deque, list, array, set, map, unordered_map, stack, queue, priority_queue and the modern span and flat_map, with complexities, traps and a guide to choosing. Then test yourself with 60 practice questions – 20 MCQs, 20 predict-the-output puzzles, 10 find-the-error programs and 10 complete programs – verified on a real C++ compiler.

On this page

  • The four families: sequence, associative, unordered and adapters
  • vector, deque, list, forward_list and array
  • set, multiset, map, multimap and their unordered versions
  • stack, queue and priority_queue
  • Complexities, insert vs emplace, the operator[] trap, erasing safely, iterator invalidation
  • C++20/23: contains, erase_if, span, flat_map

The container families

FamilyContainersOrganised by
Sequencevector, deque, list, forward_list, arrayposition (the order you insert)
Ordered associativeset, multiset, map, multimapsorted key (balanced tree)
Unordered associativeunordered_set, unordered_multiset, unordered_map, unordered_multimaphash of the key
Adaptersstack, queue, priority_queuea restricted interface over another container
Views / flat (C++20/23)span, flat_map, flat_setcontiguous storage

Sequence containers

std::vector is the default choice: contiguous memory, cache-friendly, O(1) access and amortised O(1) push_back. deque adds fast insertion at the front; list and forward_list insert and remove anywhere in O(1) given an iterator, and never move their elements; array is a fixed-size wrapper around a C array.

#include <array>
#include <deque>
#include <forward_list>
#include <iostream>
#include <list>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4};          // contiguous, fast at the back, random access
    v.push_back(1);
    v.insert(v.begin() + 1, 9);           // O(n): shifts later elements

    std::deque<int> d{2, 3};              // fast at BOTH ends, random access
    d.push_front(1);
    d.push_back(4);

    std::list<int> l{1, 2, 4};            // doubly linked: O(1) insert anywhere you have an iterator
    auto it = l.begin();
    ++it; ++it;
    l.insert(it, 3);

    std::forward_list<int> f{2, 3};       // singly linked, smallest overhead
    f.push_front(1);

    std::array<int, 3> a{7, 8, 9};        // fixed size, no heap allocation

    for (int x : v) std::cout << x << ' ';
    std::cout << "| " << d.front() << d.back() << d[1] << " | ";
    for (int x : l) std::cout << x;
    std::cout << " | ";
    for (int x : f) std::cout << x;
    std::cout << " | " << a.size() << a[2] << '\n';
    return 0;
}

Output

3 9 1 4 1 | 142 | 1234 | 123 | 39

Ordered associative containers: set and map

Implemented as balanced binary search trees (usually red-black trees), they keep keys sorted and give O(log n) insert, find and erase. set/map keep unique keys; multiset/multimap allow duplicates.

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::set<std::string> tags{"cpp", "stl", "cpp", "algo"};      // unique, sorted
    std::multiset<int> scores{70, 85, 70, 92};                     // sorted, duplicates kept

    std::map<std::string, int> stock{{"pen", 40}, {"book", 12}};  // key -> value, sorted by key
    stock["bag"] = 5;                                              // insert or overwrite
    stock.at("pen") -= 10;                                         // at(): throws if the key is missing

    for (const auto& t : tags) std::cout << t << ' ';
    std::cout << "| " << scores.count(70) << ' ' << *scores.rbegin() << " | ";
    for (const auto& [item, qty] : stock) std::cout << item << '=' << qty << ' ';
    std::cout << "| " << stock.contains("ink") << tags.contains("stl") << '\n';   // C++20
    return 0;
}

Output

algo cpp stl | 2 92 | bag=5 book=12 pen=30 | 01

Unordered containers: hash tables

unordered_map and unordered_set give O(1) average lookup by hashing keys into buckets, at the cost of no ordering and O(n) worst case. Custom key types need a hash function and ==.

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point&) const = default;
};
struct PointHash {                                        // needed to use Point as a key
    std::size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) * 31 + std::hash<int>{}(p.y);
    }
};

int main() {
    std::unordered_map<std::string, int> freq;           // hash table: O(1) average lookup
    for (std::string w : {"to", "be", "or", "not", "to", "be"}) ++freq[w];
    std::cout << freq["to"] << freq["be"] << freq["not"] << ' ' << freq.size() << '\n';

    std::unordered_set<Point, PointHash> visited{{0, 0}, {1, 2}};
    visited.insert({1, 2});                              // duplicate: ignored
    std::cout << visited.size() << visited.contains({1, 2}) << visited.contains({2, 1}) << '\n';
    // Iteration order of unordered containers is unspecified – never rely on it
    return 0;
}

Output

221 4
210

Container adapters

Adapters expose a restricted interface over another container: stack (LIFO, default deque), queue (FIFO, default deque) and priority_queue (a binary heap over vector, largest element on top by default). They have no iterators.

#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

int main() {
    std::stack<int> st;                                   // LIFO
    for (int x : {1, 2, 3}) st.push(x);
    std::cout << "stack top " << st.top();
    st.pop();
    std::cout << " then " << st.top() << '\n';

    std::queue<int> q;                                    // FIFO
    for (int x : {1, 2, 3}) q.push(x);
    q.pop();
    std::cout << "queue front " << q.front() << " back " << q.back() << '\n';

    std::priority_queue<int> maxq;                        // largest on top (a heap)
    std::priority_queue<int, std::vector<int>, std::greater<>> minq;   // smallest on top
    for (int x : {5, 1, 8, 3}) { maxq.push(x); minq.push(x); }
    std::cout << "max " << maxq.top() << ", min " << minq.top() << ", size " << maxq.size() << '\n';
    return 0;
}

Output

stack top 3 then 2
queue front 2 back 3
max 8, min 1, size 4

Complexity of common operations

ContainerAccess by indexInsert/erase at endInsert/erase at frontInsert/erase in middleFind by value/key
vectorO(1)amortised O(1)O(n)O(n)O(n) (O(log n) if sorted)
dequeO(1)O(1)O(1)O(n)O(n)
list–O(1)O(1)O(1) with iteratorO(n)
set / map–O(log n)O(log n)
unordered_set / map–O(1) average, O(n) worstO(1) average
priority_queuetop O(1)push/pop O(log n)–

insert, emplace, try_emplace and the operator[] trap

map[key] inserts a default-constructed value when the key is missing – even when you only meant to read it. Use find, contains or at for lookups. insert and emplace never overwrite; try_emplace builds the value only if needed; insert_or_assign always writes.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> m{{"asha", 91}};

    // operator[] INSERTS a default value when the key is missing
    if (m["ravi"] == 0) std::cout << "size after lookup: " << m.size() << '\n';

    // insert / emplace never overwrite; they report whether insertion happened
    auto [it1, ok1] = m.insert({"asha", 50});
    auto [it2, ok2] = m.emplace("meena", 85);
    std::cout << ok1 << ' ' << it1->second << ' ' << ok2 << '\n';

    // try_emplace: constructs only if absent; insert_or_assign: always writes
    m.try_emplace("asha", 10);
    m.insert_or_assign("ravi", 78);

    // find: look up without inserting
    if (auto it = m.find("john"); it == m.end()) std::cout << "john not found\n";
    for (const auto& [k, v] : m) std::cout << k << '=' << v << ' ';
    std::cout << '\n';
    return 0;
}

Output

size after lookup: 2
0 91 1
john not found
asha=91 meena=85 ravi=78

Erasing elements and iterator invalidation

Erasing from a container while iterating needs care: an erased iterator is invalid, so use the iterator returned by erase. For vectors, C++20 std::erase_if replaces the erase-remove idiom.

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

int main() {
    // C++20: std::erase / std::erase_if replace the erase-remove idiom
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
    std::erase_if(v, [](int x) { return x % 2 == 0; });
    for (int x : v) std::cout << x << ' ';

    // The classic erase-remove idiom (still everywhere in older code)
    std::vector<int> w{5, 0, 5, 1, 5};
    w.erase(std::remove(w.begin(), w.end(), 5), w.end());
    std::cout << "| " << w.size() << '\n';

    // Erasing while looping: use the iterator returned by erase
    std::map<int, char> m{{1, 'a'}, {2, 'b'}, {3, 'c'}, {4, 'd'}};
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2) it = m.erase(it);     // never ++ an erased iterator
        else ++it;
    }
    for (const auto& [k, c] : m) std::cout << k << c << ' ';
    std::cout << '\n';
    return 0;
}

Output

1 3 5 7 | 2
2b 4d
ContainerWhat invalidates iterators/references
vectorinsertion that reallocates (all); insert/erase (at and after the point)
dequeinsert in the middle (all); push at the ends (iterators, not references)
list, set, maponly the erased element
unordered_*rehashing (iterators, not references); the erased element

Modern additions: span and flat_map

std::span (C++20) is a cheap non-owning view of contiguous elements – the modern replacement for "pointer + size" parameters. std::flat_map (C++23) is a sorted map stored in contiguous arrays: slower inserts, but faster lookups and iteration than a tree.

#include <array>
#include <flat_map>
#include <iostream>
#include <span>
#include <string>
#include <vector>

// std::span: a non-owning view of contiguous elements – works for arrays, vectors, std::array
int total(std::span<const int> s) { int t = 0; for (int x : s) t += x; return t; }

int main() {
    int raw[] = {1, 2, 3};
    std::vector<int> v{10, 20, 30, 40};
    std::array<int, 2> a{100, 200};
    std::cout << total(raw) << ' ' << total(v) << ' ' << total(a) << ' ' << total(std::span(v).subspan(1, 2)) << '\n';

    // C++23 std::flat_map: a sorted map stored in two contiguous vectors – cache-friendly lookups
    std::flat_map<std::string, int> fm{{"pune", 411}, {"delhi", 110}, {"agra", 282}};
    fm["mumbai"] = 400;
    for (const auto& [city, pin] : fm) std::cout << city << ':' << pin << ' ';
    std::cout << '\n';
    return 0;
}

Output

6 100 300 50
agra:282 delhi:110 mumbai:400 pune:411

Which container should I use?

NeedUse
A list of items, mostly appended and readvector (the default)
Fixed number of elements known at compile timearray
Add/remove at both ends (sliding window, BFS)deque
Many insertions/erasures in the middle, stable referenceslist
Unique items, need sorted order or range queriesset
Key → value, need order (lower_bound, smallest key)map
Key → value, fastest lookup, order irrelevantunordered_map
Always process the largest/smallest nextpriority_queue
Undo history, bracket matchingstack
Process in arrival orderqueue

Common mistakes

  • Reading with map[key] – silently inserts entries.
  • Keeping iterators or references to vector elements across push_back.
  • Erasing inside a range-for loop – invalidates the hidden iterator.
  • Relying on unordered_map order – it can change between runs and compilers.
  • Using list for speed – vector is usually faster even for middle inserts on small data.
  • Calling top()/front() on an empty adapter – undefined behaviour.
  • Forgetting the comparator meaning – priority_queue with std::greater gives a min-heap.

Key points to remember

  • Default to vector; choose others for a specific reason.
  • set/map: sorted, O(log n). unordered_*: hashed, O(1) average, no order.
  • Adapters (stack, queue, priority_queue) restrict another container's interface.
  • map[key] inserts; use find/contains/at to read.
  • Use the iterator returned by erase; prefer std::erase_if in C++20.
  • Know which operations invalidate iterators for each container.

Frequently asked questions

What is the difference between map and unordered_map?

map is a balanced tree: keys sorted, O(log n) operations, needs <. unordered_map is a hash table: no order, O(1) average operations, needs a hash and ==.

What is the difference between vector and list?

vector stores elements contiguously with O(1) indexing; list is a doubly linked list with O(1) insertion anywhere (given an iterator) but no indexing and poor cache locality.

What are the three components of the STL?

Containers, algorithms and iterators (plus function objects); iterators connect algorithms to containers.

Where can I learn more?

Read C++ vector, C++ map and unordered_map and C++ set, then practise with the exercises below.

Ready to test your Programming?

Timed online tests with instant scores and explanations.

About this section

About C++ Programming

C++ adds object-oriented programming, templates and the powerful Standard Template Library (STL) to C. It powers game engines, browsers, trading systems and most competitive programming. This section takes you from basic syntax to classes, inheritance, polymorphism, modern C++ (C++11 to C++23) and the STL – every concept with runnable examples and practice questions checked on a real compiler.

Why it matters

  • OOP concepts – classes, inheritance, polymorphism, encapsulation – are asked in almost every interview
  • C++ with the STL is the most popular language for competitive programming and DSA rounds
  • Questions on constructors, virtual functions, references and smart pointers decide technical rounds
  • Modern C++ skills are in demand at product companies, fintech and game studios

Who it is for

  • School students (Class 11–12 computer science with C++) preparing for board exams and practicals
  • College students (B.Tech, BCA, MCA) learning OOP and data structures for semester exams and labs
  • Freshers preparing for placements, coding tests and C++ technical interviews
  • Competitive programmers who want to master the STL

What every topic gives you

  • Study material in five tabs: concepts with runnable examples, coding techniques, programs, interview questions and a cheat sheet
  • MCQs that check your understanding of every concept
  • "Predict the output" puzzles – the trickiest part of written tests
  • "Find the error" programs that train you to spot bugs quickly
  • Complete programs with solutions and real output, verified on a compiler

Asked in

  • Campus placements
  • Product company interviews
  • Coding rounds & DSA
  • Competitive programming
  • GATE CS
  • University exams

How to use this section

  1. Read the study material of a topic and run the examples yourself.
  2. Practise the four exercises – MCQs, output, errors, programs – and read every explanation.
  3. Test yourself with the timed online test, then revise the topics you got wrong.

Search LearnFrenzy

Esc

Quick links