Courses/C++/Standard Template Library

Lesson 12 • Expert

Standard Template Library

By the end of this lesson you'll be able to pick the right STL container for any job — vector, string, map/unordered_map, set/unordered_set, pair — and insert, look up, and iterate over each one with iterators and range-for.

What You'll Learn

Store and grow lists with std::vector and read them by index
Map keys to values with std::map and std::unordered_map
Keep a collection of unique items with std::set / std::unordered_set
Bundle two values together with std::pair
Iterate any container with begin/end, range-for, and auto
Choose ordered vs unordered containers by their cost trade-off

Before you start: you should be comfortable with C++ Templates, since every STL container is a template like vector<int>. You'll also use auto and range-for loops a lot here.

💡 Real-World Analogy

The STL is a professional toolbox. You don't whittle your own hammer — you reach for the right tool. A vector is a numbered shelf you can add to. A map is a dictionary: look up a word (the key) to get its definition (the value). A set is a guest list where each name appears once. A pair is a luggage tag tying a name to a number. Picking the wrong container is like using a wrench to hammer a nail — it works badly. This lesson is about choosing the right tool.

📦 The Core Containers

Container	Holds	Analogy	Reach for it when…
vector<T>	Ordered list of T	Numbered shelf	You want a resizable array (the default choice)
string	Text	Sentence	You're working with characters/words
map<K,V>	Sorted key→value	Dictionary	You look things up by key AND want sorted keys
unordered_map<K,V>	Hashed key→value	Hash table	You want the fastest lookups, order doesn't matter
set<T>	Unique, sorted	Sorted guest list	No duplicates allowed and you want them sorted
pair<A,B>	Two values	Luggage tag	You need to return/keep two things as one

1. `std::vector` — the resizable array

A vector is a list that grows and shrinks automatically, so it's the container you reach for 90% of the time. You add to the end with push_back, read any item by position with [] (indexes start at 0), and walk through it with a range-for. To insert or erase in the middle you give a position — an iterator like begin() + 1. Read this worked example, run it, then you'll write one.

Worked example: vector — insert, lookup, iterate

Read every comment, run it, and check the output matches.

Try it Yourself »

C++

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

int main() {
    // A vector is a list that grows and shrinks for you.
    // vector<T> holds many values of ONE type T.
    vector<string> fruits = {"Apple", "Banana", "Cherry"};

    // INSERT at the end — the cheap, normal way to add.
    fruits.push_back("Date");          // {Apple, Banana, Cherry, Date}

    // LOOKUP by position with [] — indexes start at 0.
    cout << "First: " << fruits[0] << endl;        // F
...

Your turn. The program below is almost complete — fill in the two blanks marked ___ using the hints, then run it.

🎯 Your turn: build a vector of scores

Fill in the ___ blanks, then check your output against the expected lines.

Try it Yourself »

C++

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

int main() {
    // 🎯 YOUR TURN — replace each ___ then press "Try it Yourself".

    // 1) Make a vector<int> called "scores" with 90, 85, 95
    vector<int> scores = ___;     // 👉 use { } braces, e.g. {90, 85, 95}

    // 2) Add the score 70 to the END of the vector
    scores.___(70);               // 👉 the method that appends is push_back

    // These lines already work once your code above is right:
    int total = 0;
    for (
...

2. `std::map` & `std::unordered_map` — key → value

A map stores key → value pairs, like a dictionary where you look up a word to get its meaning. std::map<K,V> keeps keys sorted (lookups cost O(log n)); std::unordered_map has the same interface but hashes keys for O(1) average lookups with no order. The big gotcha: myMap[key] inserts a default value when the key is missing, so to merely check a key use .count() or .find() — they never insert.

Worked example: map — insert, lookup, iterate

See [] vs insert vs find, and ordered vs hashed lookups.

Try it Yourself »

C++

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    // A map stores KEY -> VALUE pairs. Here: name (string) -> age (int).
    // std::map keeps keys SORTED; lookups cost O(log n).
    map<string, int> ages;

    // INSERT — two ways:
    ages["Alice"] = 25;          // [] assigns (or creates) a key
    ages.insert({"Bob", 30});    // insert() won't overwrite an existing key

    // LOOKUP. WARNING: ages["Eve"] would CREATE Eve with
...

Now you try. Build a tiny phone book and check a key safely — fill in the two blanks:

🎯 Your turn: a safe phone book

Add an entry, then check existence without creating a key.

Try it Yourself »

C++

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

int main() {
    // 🎯 YOUR TURN — a phone book: name -> extension number.
    map<string, int> phonebook;

    // 1) Add "Sam" with extension 101 using []
    phonebook["Sam"] = ___;       // 👉 the number 101

    // 2) Check whether "Sam" exists WITHOUT creating a new key.
    //    Fill in the method that counts a key but never inserts.
    if (phonebook.___("Sam")) {   // 👉 use count
        cout << "Sam is at exten
...

3. `std::set`, `std::pair` & iterators

A set holds unique values — try to add a duplicate and it's silently ignored — and std::set keeps them sorted (std::unordered_set is the hash-based, unordered twin). A pair glues two values into one object you reach with .first and .second. Underneath every container are iterators: begin() points at the first element, end() points one past the last (a stop sign, not a value), and *it reads what the iterator points at. auto spares you from spelling out the iterator's type.

Worked example: set, pair & iterators

Unique values, two-value pairs, and walking a container by hand.

Try it Yourself »

C++

#include <iostream>
#include <set>
#include <unordered_set>
#include <utility>   // for std::pair
#include <string>
using namespace std;

int main() {
    // === SET — a collection of UNIQUE values (no duplicates) ===
    // std::set keeps them SORTED; duplicates are silently dropped.
    set<int> seen = {5, 3, 8, 3, 5};   // stored as: 3 5 8
    seen.insert(4);                    // INSERT -> 3 4 5 8
    seen.insert(3);                    // already there -> ignored

    cout << "Set: ";
    fo
...

🔎 Deep Dive: ordered vs unordered cost

The map/set pair are built on balanced trees: every insert, erase, and lookup costs O(log n), and you get sorted order for free. The unordered_ pair use a hash table: O(1) average, but the elements come out in no useful order.

Rule of thumb: if you need the keys sorted (printing alphabetically, range queries), use the ordered version. If you just need fast membership tests or lookups and don't care about order, the unordered version is usually faster.

map<string,int>           ordered, O(log n)  -> sorted iteration
unordered_map<string,int> hashed,  O(1) avg   -> no order, faster
// same trade-off for set vs unordered_set

Pro Tips

💡 Default to vector: it's contiguous and cache-friendly. Only switch containers when you have a reason (unique items → set, key lookups → map).
💡 Structured bindings read maps cleanly: for (const auto &[k, v] : m) unpacks each pair (C++17).
💡 Counting with a map is a one-liner: counts[word]++; — a missing key starts at 0, so ++ makes it 1.
💡 auto for iterators: auto it = m.find(k); beats writing map<string,int>::iterator by hand.

Common Errors (and the fix)

Iterator invalidation (crash / garbage): erasing while iterating leaves your iterator dangling. Use the value erase() returns: it = v.erase(it); and only ++it when you didn't erase.
[] silently inserts into a map: if (m["Eve"]) ... just created Eve with value 0. To check a key, use m.count("Eve") or m.find("Eve") != m.end().
Expecting unordered_map to be sorted: it isn't — it's hashed. If you print it and want order, use map (or copy into a vector and sort).
.find() vs [] confusion: [] returns the value (and may insert); .find() returns an iterator. Compare .find() to .end() to test existence, then read it->second for the value.
Dereferencing end(): end() is one past the last element — *v.end() is undefined behaviour. Always check it != v.end() first.

📋 Quick Reference — which container?

You need…	Use	Insert	Lookup
An ordered, resizable list	vector<T>	v.push_back(x)	v[i]
Key → value, sorted keys	map<K,V>	m[k] = v	m.find(k)
Key → value, fastest	unordered_map<K,V>	m[k] = v	m.count(k)
Unique items, sorted	set<T>	s.insert(x)	s.count(x)
Unique items, fastest	unordered_set<T>	s.insert(x)	s.count(x)
Two values as one	pair<A,B>	{a, b}	p.first / p.second

Frequently Asked Questions

Q: When should I use map vs unordered_map?

Use unordered_map when you only need fast key lookups — it hashes keys for O(1) average access. Use map (a balanced tree, O(log n)) when you also need the keys to stay in sorted order, for example to print them alphabetically or to find ranges. If you don't care about order, unordered_map is usually faster.

Q: What is the difference between .find() and [] on a map?

[] returns the value for a key AND inserts a default-constructed entry if the key is missing — so just reading a missing key silently grows your map. .find() returns an iterator and never inserts: compare it to .end() to test existence. Use [] to assign, .find() or .count() to check.

Q: Why is set sorted but unordered_set is not?

std::set and std::map are built on balanced binary trees, which keep elements in sorted order as a side effect — that ordering is what costs the O(log n) per operation. The unordered_ versions use a hash table, which scatters elements into buckets for O(1) average speed but gives up any meaningful order.

Q: What does end() point to — the last element?

No. begin() points at the first element, but end() points ONE PAST the last — think of it as a stop sign, not a real value. That is why loops run while it != container.end() and why a successful .find() returns something other than end(). Never dereference end().

Q: What is iterator invalidation?

Adding to or erasing from a container can move its internal storage, leaving any iterators (and the range-for loop using them) pointing at freed memory — often a crash. The safe pattern is to use the iterator that erase() returns: it = v.erase(it); and only ++it when you did not erase. For vectors, push_back can also invalidate iterators if it reallocates.

Mini-Challenge: Word Frequency Counter

No blanks this time — just a brief and an outline. Count how many times each word appears using a map<string,int>, then print the tallies. Because std::map sorts keys, your output comes out alphabetically for free. Build it, run it, and check against the expected output.

🎯 Mini-Challenge: count words with a map

Read each word, tally it in a map, and print every word with its count.

Try it Yourself »

C++

#include <iostream>
#include <map>
#include <string>
#include <sstream>
using namespace std;

int main() {
    // 🎯 MINI-CHALLENGE: Word frequency counter
    // 1. Start from this text:
    string text = "red blue red green blue red";
    //
    // 2. Make a  map<string, int> counts;
    // 3. Read each word and do  counts[word]++;
    //    (a brand-new key starts at 0, so ++ makes it 1 — perfect.)
    //    Tip: feed the text into an istringstream and use  while (ss >> word)
    // 4. Iterat
...

🎉 Lesson Complete

✅ vector<T> is your default resizable list — push_back, index with [], range-for to iterate
✅ map/unordered_map store key → value; ordered (O(log n)) vs hashed (O(1) avg)
✅ set/unordered_set keep unique items; pair bundles two values
✅ [] on a map inserts missing keys — use .count()/.find() to just check
✅ Iterators: begin()/end(), *it reads, auto names the type, end() is one-past-last
✅ Next lesson: Memory Management — dynamic allocation with new, delete, and smart pointers

Standard Template Library

What You'll Learn

💡 Real-World Analogy

📦 The Core Containers

1. std::vector — the resizable array

Worked example: vector — insert, lookup, iterate

🎯 Your turn: build a vector of scores

2. std::map & std::unordered_map — key → value

Worked example: map — insert, lookup, iterate

🎯 Your turn: a safe phone book

3. std::set, std::pair & iterators

Worked example: set, pair & iterators

🔎 Deep Dive: ordered vs unordered cost

Pro Tips

Common Errors (and the fix)

📋 Quick Reference — which container?

Frequently Asked Questions

Mini-Challenge: Word Frequency Counter

🎯 Mini-Challenge: count words with a map

🎉 Lesson Complete

Cookie & Privacy Settings

1. `std::vector` — the resizable array

2. `std::map` & `std::unordered_map` — key → value

3. `std::set`, `std::pair` & iterators