Iterators

Iterators

---

Prerequisites

---

1. What is an Iterator

An iterator is a generalized pointer that allows you to access elements inside a container.

2. Iterators Core

Iteration

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3};

    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << *it << " ";
}

begin() and end()

v.begin();  // first element
v.end();    // one past the last element

• end() is not valid to dereference
• it marks the stopping condition

Reverse Iteration

for (auto it = v.rbegin(); it != v.rend(); ++it)
    std::cout << *it << " ";

rbegin() and rend()

v.rbegin();  // last element
v.rend();    // before first element

Iterators unify access across containers:

• vector
• list
• set
• map

3. Iterator Adapters

Adapters modify iterator behavior

back_insert_iterator

#include <iterator>

std::vector<int> v;

auto it = std::back_inserter(v);
*it = 10;  // v.push_back(10)

front_insert_iterator

#include <list>

std::list<int> l;

auto it = std::front_inserter(l);
*it = 10;  // l.push_front(10)

insert_iterator

auto it = std::inserter(v, v.begin());
*it = 5;  // insert at position

reverse_iterator

for (auto it = v.rbegin(); it != v.rend(); ++it)
    std::cout << *it;

Traverses container in reverse

move_iterator

#include <iterator>

std::vector<std::string> src = {"a", "b"};
std::vector<std::string> dst;

std::copy(
    std::make_move_iterator(src.begin()),
    std::make_move_iterator(src.end()),
    std::back_inserter(dst)
);

Moves elements instead of copying

4. Iterator Utilities

Utilities simplify iterator movement

next

auto it = std::next(v.begin(), 2);

Returns a new iterator moved forward

prev

auto it = std::prev(v.end());

Returns a new iterator moved backward

advance

auto it = v.begin();
std::advance(it, 2);

Moves iterator in-place

Function	Behavior
next	returns new iterator
prev	returns new iterator
advance	modifies existing iterator

5. Check

❌ Not all iterators support backward movement

std::forward_list → no prev()

❌ advance depends on iterator type

• Random access → fast
• Forward → linear time

Iterator categories matter

Type	Complexity
Random access (vector)	O(1)
Bidirectional (list)	O(n)
Forward (forward_list)	O(n)