Lecture 6:

Iterators and Pointers

Stanford CS106L, Fall 2025
Rachel Fernandez, Thomas Poimenidis
Welcome back! Link to Attendance Form ↓
Pop Quiz: Containers
• Which type(s) lets you insert at the back and front equally efficiently?
• Which type(s) requires a comparison operator on the element type?
• What type(s) can we use to get around this?

• Which is usually faster: unordered_set or set? Why?

Pop Quiz: Containers (Answers)
• Which type(s) lets you insert at the back and front equally efficiently?
• ✅ std::deque

• Which type(s) requires a comparison operator on the element type?

• ✅ std::map, std::set

• Which is usually faster: unordered_set or set? Why?

• ✅ std::unordered_set (Hashing + small load factor)!
What questions do you have?

bjarne_about_to_raise_hand
Last Time: Containers

0 1 2 4

1 2 3 4
1 9 7 3 2 1 2 9

0 “Chris” 31

“CS106L” 42 1

2 “Nick” 51
“Chris” 31 “Nick” 51

3 “Sean” 35

“Keith” 14 “Sean” 35
4
 std::map

std::vector
std::set
std::deque

for (const auto& elem : container)

How does this work?

For-each loops… huh?
std::vector<int> v { 1, 2, 3, 4 };

for (const auto& elem : v) {

0 1 2 4
std::cout << elem << std::endl;
1 2 3 4
}
For-each loops… huh?
std::deque<int> d {
1, 9, 7, 3,
2, 1, 2, 9
};

for (const auto& elem : d) { 1 9 7 3 2 1 2 9

std::cout << elem << std::endl;

}
For-each loops… huh?
std::map<std::string, int> m {
{ "Chris", 31 }, { "CS106L", 42 },
{ "Keith", 14 }, { "Nick", 51 },
“CS106L” 42

{ "Sean", 35 },
}; “Chris” 31 “Nick” 51

“Keith” 14 “Sean” 35
for (const auto& pair : m) {
std::cout << [Link] << " ";
std::cout << [Link];
}
For-each loops… huh?
std::unordered_map<string, int> m
{
{ "Chris", 31 }, { "Nick", 51 }, “Chris” 31
0
{ "Sean", 35 },
1
};
2 “Nick” 51

for (const auto& pair : m) { 3 “Sean” 35

std::cout << [Link] << " "; 4

std::cout << [Link];

}
for (const auto& elem : container)

How does this work?

Lecture 7: Iterators
CS106L, Fall 2025
The Standard Template Library (STL)

Containers Iterators
How do we store groups of things? How do we traverse containers?

Functors Algorithms
How do we transform and modify containers
How can we represent functions as objects?
in a generic way?
Today’s Agenda
• Iterator Basics
• What even is an iterator?

• Iterator Types
• Iterators are organized by their properties

• Pointers and Memory

• What is a pointer? What is memory?
What questions do you have?

bjarne_about_to_raise_hand
Iterator Basics
Question: How do we iterate?
std::vector<int> v {1,2,3,4};
for (size_t i = 0; i < [Link](); i++) {
const auto& elem = v[i];
std::cout << elem;
}
Question: How do we iterate?
std::vector<int> v {1,2,3,4};
for (size_t i = 0; i < [Link](); i++) {
const auto& elem = v[i];
std::cout << elem;
}

for (var-init; condition; increment) {

const auto& elem = /* grab element */;
/* do something with elem */
}
Question: How do we iterate?
for (auto e : s) is not
allowed ...for now
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

std::set<int> s {1,2,3,4};
for (uhhh; ummm; what?) {
const auto& elem = /* haeelp 🥺🥺 */;
}
We need something to track where we are
in a container… sort of like an index
Introducing iterators 😎😎
C++ iterators are like a “claw” in a claw machine

The claw can: The machine can:

1. Grab a toy 1. Tell us where to

2. Move forward start
3. Check if we’re done 2. Tell us when to stop
C++ Iterators Example
++it;
++it;

++it;

++it; ++it;
auto elem = *it; it == [Link]()

auto it = [Link](); ++it;

Containers and iterators work together to allow iteration
Container Interface
[Link]()

Gets an iterator to
the first element
of the container
(assuming non-empty)

‘d’ ‘a’ ‘w’ ‘g’ ‘s’

Container Interface
[Link]() [Link]()

Gets an iterator to Gets a past-the-end iterator

the first element
of the container That is, an iterator to
(assuming non-empty) one element after the
end of the container
‘d’ ‘a’ ‘w’ ‘g’ ‘s’ ‘d’ ‘a’ ‘w’ ‘g’ ‘s’
end() never points to an element!

Instead, it points one

[Link]() past the end of the [Link]()
container
end() never points to an element!

If c is empty, then
begin() and end() are
equal!

[Link]() == [Link]()
Iterator Interface
// Copy construction
auto it = [Link]();
Iterator Interface
// Copy construction
auto it = [Link]();

// Increment iterator forward

++it;
Iterator Interface
// Copy construction
auto it = [Link]();

// Increment iterator forward

++it;

// Dereference iterator -- undefined if it == end()

auto& elem = *it;
Iterator Interface
// Copy construction
auto it = [Link]();

// Increment iterator forward

++it;

// Dereference iterator -- undefined if it == end()

auto& elem = *it;

// Equality: are we in the same spot?

if (it == [Link]()) ...
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for ( ; ; ){
const auto& elem = /* grab element */;
}
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); ; ){

const auto& elem = /* grab element */;
}
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); it != [Link](); ) {

const auto& elem = /* grab element */;
}
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); it != [Link](); ++it) {

const auto& elem = /* grab element */;
}
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); it != [Link](); ++it) {

const auto& elem = *it;
}
When you write… It’s actually this:
for (auto elem : s) auto b = [Link]();
{ auto e = [Link]();
std::cout << elem;
for (auto it = b; it != e; ++it) {
} auto elem = *it;
std::cout << elem;
}
What questions do you have?

bjarne_about_to_raise_hand
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); it != [Link](); ++it) {

const auto& elem = *it;
}
Guess we’re done here!
We have an answer now!
for (auto e : s) is not
allowed ...for now
std::set<int> s {1,2,3,4};
for (var-init; condition; increment) {
const auto& elem = /* grab element */;
}

for (auto it = [Link](); it != [Link](); ++it) {

const auto& elem = *it;
}
What type is this?
What are the types?
Using auto avoids spelling out long iterator types

std::map<int, int> m { {1, 2}, {3, 4}, {5, 6}};

auto it = [Link]();
auto elem = *it; // {1, 2}

std::map<int, int> m { {1, 2}, {3, 4}, {5, 6}};

std::map<int, int>::iterator it = [Link]();
std::pair<int, int> elem = *it;
Remember: using makes a type alias
// Inside <map> header
template <typename K, typename V>
class std::map {
using iterator = /* some iterator type */;
};

// Outside <map> header (e.g. [Link])

std::map<int, int>::iterator it = [Link]();

Iterator types are really long, so we

like to use auto with iterators
Aside: Why do we use ++it instead of it++?
++it avoids making an unnecessary copy

// Prefix form - ++it

// Increments it and returns a reference to same object
Iterator& operator++();

// Postfix form - it++

// Increments it and returns a copy of the old value
Iterator operator++(int);

Remember: an iterator is a fully-fledged object, so it’s often more expensive to copy than, say, an int
Does it actually make a difference?
Bjarne’s Thoughts

yup
“
++i is sometimes faster than, and is never slower
than, i++. ... So if you’re writing i++ as a statement
rather than as part of a larger expression, why not
just write ++i instead? You never lose anything, and
you sometimes gain something.
[source]
What questions do you have?

bjarne_about_to_raise_hand
Your Turn
Trace this code with a partner to find out where each iterator points

std::map<int, int> m { [Link]() [Link]()

{1, 2}, {3, 4}, {5, 6}
};
auto a = [Link](); 1 2 3 4 5 6
++a;
auto b = a;
++a;
a b c
auto c = ++a;
Iterator Types
Not all iterators are made equal
 All iterators provide these four operations

auto it = [Link](); ++it;

*it; it == [Link]()

But most provide even more

--it; // Move backwards *it = elem; // Modify

it += n; // Rand. access it1 < it2 // Is before?

Iterator types determine their functionality

Input Output

Forward

Bidirectional
Let’s unpack this!

Random Access
Input Iterators
• Most basic kind of iterator INPUT
• Allows us to read elements
auto elem = *it;
OUTPUT

Vivid Venn Diagram of

Vexing Iterators
Input Iterators
• Most basic kind of iterator
• Allows us to read elements
Input Iterators: operator->
If the element is a struct, we can access its members with ->

struct Bibble { Bibble, v.

“To eat and/or drink noisily”
int zarf;
};

std::vector<Bibble> v {...};
auto it = [Link]();
int m = (*it).zarf;
int m = it->zarf; // Exactly the same as prev!
Input Iterators
• Most basic kind of iterator INPUT
• Allows us to read elements
auto elem = *it;
OUTPUT

Output Iterator
Allows us to write elements
Vivid Venn Diagram of
*it = elem; Vexing Iterators
Output Iterator
Allows us to write elements
Forward Iterator
• An input iterator that allows us to INPUT
FORWARD
make multiple passes
• All STL container iterators fall here
OUTPUT
Multi-pass guarantee
it1 == it2

What kind of data structure might not want a

++it1 == ++it2 multi-pass iterator?
Vivid Venn Diagram of
Streams!!!
Vexing Iterators
Bidirectional Iterators
• Allows us to move forwards and INPUT
FORWARD
backwards
Bio-
• std:map, std::set directional
OUTPUT
auto it = [Link]();

// Get last element

--it;
auto& elem = *it; Vivid Venn Diagram of
Vexing Iterators
Random Access Iterators
• Allows us to quickly skip forward and INPUT
FORWARD
backward
Random
Bio-
• std::vector, std::deque directional
Access
OUTPUT
auto it2 = it + 5; // 5 ahead
auto it3 = it2 - 2; // 2 back

// Get 3rd element

auto& second = *(it + 2);
Vivid Venn Diagram of
auto& second = it[2]; Vexing Iterators
Be careful not to go out of bounds
std::vector<int> v { 1, 2, 3 };
auto it = [Link]();
it += 3;
int& elem = *it; // Undefined behaviour

0 1 2

1 2 3

it
STL Iterator Types

INPUT
FORWARD

Random
Bio-
directional
Access
OUTPUT
Why does it matter?
Why does it matter?
As we’ll soon see, some algorithms require a certain iterator type!

std::vector<int> vec{1,5,3,4};
std::sort([Link](), [Link]());
// ✅ begin/end are random access

std::unordered_set<int> set {1,5,3,4};

std::sort([Link](), [Link]());
// ❌ begin/end are bidirectional
Why have multiple iterator types?
• Goal: provide a uniform abstraction over all containers
• Caveat: the way that a container is implemented affects how you
iterate through it
• Skipping ahead 5 steps (random access) is a lot easier/faster when you have a
sequence container (vector, deque) than associative (map, set)
• C++ generally avoids providing you with slow methods by design, so that’s why
you can’t do random access on a map::iterator
What questions do you have?

bjarne_about_to_raise_hand
STL Iterator Types

map
istream set

unordered_map deque
unordered_set vector

ostream
Pointers and Memory
An iterator points to a container element
A pointer points to any object
Memory Basics
Memory Basics
• Every variable lives somewhere in memory
• All the places something could live form the address space
OS Shared
Variables (Stack)

Your Program’s Memory

Variables (Heap)
Global Variables
Text (Instructions)
Memory Basics
• Memory is usually byte-addressable, with each byte numbered from 0
• 1 byte = 8 bits
2^64 – 1
OS Shared (on a 64-bit system)
Variables (Stack)

Your Program’s Memory

Variables (Heap)
Global Variables
Text (Instructions)
0x0
Memory Basics
• The address of an object is the location of its lowest byte
• For example, an integer always uses 32 bits = 4 bytes

int x = 106; // 32 bits

x’s memory
0x10 is the
address of x 00000000 00000000 00000000 01101010

0x10 0x11 0x12 0x13

What questions do you have?

bjarne_about_to_raise_hand
How do we get the address of a variable in C++?
Pointers! 👉 👉 👉
A pointer is the address of a variable
int* means px is a & is the address
int x = 106;
pointer to an int of operator
int* px = &x;

std::cout << x << std::endl; // 106

std::cout << *px << std::endl; // 106
std::cout << px << std::endl; // 0x50527c
A pointer is just a number!

int* px int x
0x50527c 00000000 00000000 00000000 01101010

0x50527c 0x50527d 0x50527e 0x50527f

What questions do you have?

bjarne_about_to_raise_hand
 int* px

int x
We can have pointers to all kinds of things!

int x = 106; StanfordID id { “jtrb” };

int* px = &x; StanfordID* p = &id;
auto name = p->name;

std::vector<int> v; std::vector<int> v {
std::vector<int>* p = &v; 1, 2, 3, 4, 5
};
int* arr = &v[0];
Recall: a vector is a contiguous array

1 9 7 3 2 1 2 9

A vector is a single chunk of

memory
Array pointer
std::vector<int> v {1,2,3,4,5};

int* arr = &v[0]; std::cout << *arr << " ";

arr += 1; std::cout << *arr << " ";
++arr; std::cout << *arr << " ";
arr += 2; std::cout << *arr << " ";
if (arr == &v[4]) std::cout << ”At last index";

0 1 2 3 4
1 2 3 4 5 Output:
1 2 3 5 At last index
arr
Notice anything?
std::vector<int> v {1,2,3,4,5};

int* arr = &v[0]; // Copy construction

arr += 1; // Random access
++arr; // Move pointer forward
arr += 2; // Random access
if (arr == &v[4]) // Pointer comparison
We could do the same thing with iterators!

auto it = [Link](); std::cout << *it << " ";

it += 1; std::cout << *it << " ";
++it; std::cout << *it << " ";
it += 2; std::cout << *it << " ";
if (it == --[Link]()) std::cout << "At last element";
Recall: iterator is a type alias
template <typename T>
class vector {
using iterator = /* some iterator type */;;

// Implementation details...
};
Iterators have a similar interface to pointers
T* is the backing type for vector<T>::iterator
template <typename T>
class vector {
using iterator = T*;

// Implementation details...
};

In the real STL implementation, the actual type is not T*.

But for all intents and purposes, you can think of it this way.
What questions do you have?

bjarne_about_to_raise_hand
Recap
What we covered
• Iterator Basics
• An iterator allows us to step forward through a container

• Iterator Types
• Input, Output, Forward, Bidirectional, Random Access

• Pointers and Memory

• A pointer points to an arbitrary C++ object in memory
• Pointers and iterators have the same interface
So how do we implement other iterators?

template <typename K, typename V>

class map { “CS106L” 42

using iterator = ???????; “Chris” 31 “Nick” 51

// Implementation details... “Keith” 14 “Sean” 35

};
 Classes

We’ll learn about them next time