Containers Internals

By the end of this lesson you'll understand what really happens when a vector grows, why map and unordered_map have completely different performance, how list and deque store their data, and how to pick the right container by its Big-O cost instead of guessing.

Learn Python, JavaScript, Java and more with free interactive lessons, real projects and AI-powered help. Beginner-friendly.

Part of the free C++ course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Think of a vector as a row of seats bolted to the floor . When the row fills up you can't just add one more seat on the end — you rent a bigger room, carry everyone over, and throw away the old room. That "carry everyone over" is a reallocation , and it's why anyone holding a ticket to "seat 3 in the old room" (an iterator or pointer) is suddenly pointing at nothing. A std::map is more like a library card catalogue : drawers kept in strict alphabetical order, so finding a card means a few quick narrowing steps ( O(log n) ). An unordered_map is a coat check : your ticket number is hashed straight to a hook, so retrieval is instant on average ( O(1) ) — but the coats hang in no particular order.

* vector push_back is amortised O(1) — most pushes are instant, but the occasional grow copies everything. ** list O(1) insert/erase needs an iterator already pointing at the spot.

1. Inside vector : size, capacity & growth

A vector keeps its elements in one contiguous block of memory. Two numbers describe it: size() is how many elements you've added, and capacity() is how many it can hold before it must grab a bigger block. When you push_back past the capacity, the vector reallocates : it allocates a larger buffer (most implementations double it), copies or moves every element across, and frees the old one. Run this and watch capacity jump 1 → 2 → 4 → 8 → 16 instead of climbing by one.

Because the buffer doubles, the rare expensive copy is spread thin across many cheap pushes — so the average cost per push_back is constant. That's what amortised O(1) means. If you already know how many elements are coming, reserve(n) grabs the whole buffer once, so there are zero reallocations while you fill it.

Your turn. Fill in the three blanks marked ___ using the hints in the comments. The goal: pre-allocate for 50 elements so the capacity never has to grow.

Because a reallocation moves the entire buffer , every iterator, pointer, and reference you were holding into the vector now points at freed memory . Using one after the vector grows is undefined behaviour — often a crash, sometimes a silent wrong answer.

Rule of thumb: never hold a raw pointer or iterator across an operation that can grow the vector. Either reserve() first, or re-fetch afterwards.

2. map (tree) vs unordered_map (hash)

Both store key → value pairs, but their internals are nothing alike. std::map is a balanced binary search tree (a red-black tree): keys are always kept sorted , so iterating gives you them in order, and every lookup is O(log n) — a handful of comparisons even for millions of keys. std::unordered_map is a hash table : it runs the key through a hash function to pick a bucket , giving O(1) average lookup, but iteration comes out in no useful order.

The load factor ( size / bucket_count ) measures how crowded the buckets are. When it rises past max_load_factor (default 1.0 ), the table rehashes into more buckets — the hash-table version of a vector reallocation. Choose unordered_map for raw lookup speed; choose map when you need sorted order or range queries.

Now you choose. You need to count word frequencies — fast lookups, order doesn't matter. Fill in the blanks to use the right container and increment each count:

3. Inside list and deque

A std::list is a doubly-linked list : each element is a separate node holding a value plus pointers to its neighbours. That makes inserting or erasing anywhere O(1) — if you already hold an iterator there — but there's no list[i] random access, and the scattered nodes hurt cache performance. A std::deque stores data in a sequence of fixed-size chunks, which buys you O(1) push at both ends plus O(1) random access — the one thing a vector can't do cheaply at the front.

* vector push_back is amortised O(1); a single grow copies all elements.

No blanks this time — just a brief and an outline. Push 100 elements and count how many times the capacity actually changes. If push_back were O(n) you'd see 100 reallocations; with doubling you'll see only a handful. Run it and check the count against the expected note in the comments.

Practice quiz

What does a vector do when you push_back past its capacity?

  • Adds one slot
  • Throws an exception
  • Allocates a bigger block (often double), copies/moves all elements over, frees the old block
  • Switches to a linked list

Answer: Allocates a bigger block (often double), copies/moves all elements over, frees the old block. It reallocates a larger buffer and moves everything across — which is why capacity jumps in big steps.

Why is vector push_back called amortised O(1)?

  • The rare expensive grow-and-copy is spread thinly across many cheap pushes, so the average is constant
  • Every push is exactly one step
  • It is actually O(n)
  • Because reserve is always called

Answer: The rare expensive grow-and-copy is spread thinly across many cheap pushes, so the average is constant. Doubling means N push_backs cost O(N) total, so each is O(1) on average — amortised O(1).

What does reserve(n) do to a vector?

  • Adds n zero-initialized elements
  • Shrinks the buffer
  • Sorts the elements
  • Pre-allocates capacity for n elements without adding any (size stays 0)

Answer: Pre-allocates capacity for n elements without adding any (size stays 0). reserve grabs the buffer up front so filling causes zero reallocations; resize, by contrast, actually adds elements.

After a vector reallocates to grow, what happens to existing iterators, pointers, and references into it?

  • They stay valid
  • They are invalidated (dangling) — they point at freed memory
  • Only iterators break
  • They auto-update

Answer: They are invalidated (dangling) — they point at freed memory. The whole buffer moves, so any saved iterator/pointer/reference now points at freed memory — undefined behaviour to use.

How is std::map implemented, and what is its lookup complexity?

  • Balanced binary search tree (red-black), O(log n), keys kept sorted
  • Hash table, O(1)
  • Array, O(1)
  • Linked list, O(n)

Answer: Balanced binary search tree (red-black), O(log n), keys kept sorted. map is a red-black tree: keys are sorted and every lookup/insert is O(log n).

When should you choose std::unordered_map over std::map?

  • When you need sorted keys
  • When you need range queries
  • When you only need fast key→value lookup and don't care about order (O(1) average)
  • When keys are strings

Answer: When you only need fast key→value lookup and don't care about order (O(1) average). unordered_map is a hash table with O(1) average lookup; pick map when you need ordering or range queries like lower_bound.

What is the load factor of an unordered_map?

  • bytes per element
  • number of elements / number of buckets
  • buckets / elements
  • the hash seed

Answer: number of elements / number of buckets. Load factor = size / bucket_count; past max_load_factor (default 1.0) the table rehashes into more buckets.

What is std::list internally, and what does it lack compared to vector?

  • A contiguous array; lacks push_back
  • A hash table; lacks ordering
  • A tree; lacks insertion

list is doubly-linked nodes — O(1) insert/erase at a held iterator, but no index access and poor cache locality.

What can a std::deque do that a std::vector cannot do cheaply?

  • Random access by index
  • O(1) push at the FRONT (as well as the back)
  • Sort itself
  • Hash its keys

Answer: O(1) push at the FRONT (as well as the back). A deque stores data in chunks, giving O(1) push at both ends plus O(1) random access; vector front-insert is O(n).

Why does a std::vector often beat std::list even for middle insertions in practice?

  • vector insertion is O(1)
  • list is deprecated
  • Contiguous memory is cache-friendly, while scattered list nodes cause cache misses
  • vector never reallocates

Answer: Contiguous memory is cache-friendly, while scattered list nodes cause cache misses. Despite O(n) middle inserts, the vector's contiguous layout is cache-friendly; list nodes are scattered. Measure before choosing list.