Skip to content

Iterator Types — Input, Output, Forward, Bidirectional, Random Access, Custom

DodaTech Updated 2026-06-28 8 min read

In this tutorial, you will learn about Iterator Types. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ iterators provide a uniform interface for traversing data structures, with five categories — input, output, forward, bidirectional, and random access — determining traversal capabilities and algorithm compatibility.

What You'll Learn

You will understand the five iterator categories and their capabilities, use stream iterators for I/O, write custom iterators for user-defined containers, apply iterator traits and adaptors like reverse_iterator and move_iterator, and choose appropriate iterators for algorithm requirements.

Why It Matters

Iterators are the bridge between containers and algorithms. Understanding iterator categories tells you which algorithms work with which containers. Writing custom iterators allows your data structures to work seamlessly with the entire STL. Iterator adaptors like move_iterator enable powerful transformations without modifying containers.

Learning Path

graph LR
    A["40: Ranges Library"] --> B["41: Iterator Types"]
    B --> C["42: Function Templates"]
    C --> D["43: Class Templates"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

Iterator Categories

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <iterator>
#include <concepts>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {1, 2, 3, 4, 5};
    std::forward_list<int> fl = {1, 2, 3, 4, 5};
    
    // Random access iterator (vector, deque, array, string)
    auto randIt = vec.begin();
    randIt += 3;          // O(1) advance
    auto diff = randIt - vec.begin();  // O(1) distance
    std::cout << "vec[3] = " << randIt[0] << "\n";  // O(1) indexing
    
    // Bidirectional iterator (list, set, map)
    auto biIt = lst.begin();
    ++biIt;
    --biIt;               // can go backwards
    
    // Forward iterator (forward_list, unordered containers)
    auto fwdIt = fl.begin();
    ++fwdIt;
    // --fwdIt;  // Error: cannot decrement forward iterator
    
    // Input iterator (istream_iterator)
    // Output iterator (ostream_iterator)
}

Category Hierarchy

Input                    Output
  |                        |
  v                        |
Forward                    |
  |                        |
Bidirectional              |
  |                        |
Random Access              |
  |
Contiguous (C++17)

Each category includes all capabilities of the categories above it.

Category Read Write Multi-pass ++ -- [] +n
Input Yes No No Yes No No No
Output No Yes No Yes No No No
Forward Yes Yes Yes Yes No No No
Bidirectional Yes Yes Yes Yes Yes No No
Random Access Yes Yes Yes Yes Yes Yes Yes

Stream Iterators

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <sstream>

int main() {
    // Output iterator: writes to stream
    std::ostream_iterator<int> out(std::cout, " ");
    *out = 1;  // writes "1 "
    ++out;
    *out = 2;  // writes "2 "
    std::cout << "\n";
    
    // Using with algorithm
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << "\n";  // 10,20,30,40,50,
    
    // Input iterator: reads from stream
    std::istringstream input("10 20 30 40 50");
    std::vector<int> parsed;
    std::copy(std::istream_iterator<int>(input),
              std::istream_iterator<int>(),  // default = end
              std::back_inserter(parsed));
    
    // Read from cin with iterator
    // std::vector<int> from_cin;
    // std::copy(std::istream_iterator<int>(std::cin),
    //           std::istream_iterator<int>(),
    //           std::back_inserter(from_cin));
}

Iterator Adaptors

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // reverse_iterator: traverse backwards
    std::copy(v.rbegin(), v.rend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";  // 5 4 3 2 1
    
    // back_insert_iterator: push_back
    std::vector<int> dest;
    std::copy(v.begin(), v.end(), std::back_inserter(dest));
    
    // front_insert_iterator: push_front (requires deque or list)
    // insert_iterator: insert at arbitrary position
    
    // move_iterator: move elements instead of copying
    std::vector<std::string> src = {"hello", "world"};
    std::vector<std::string> dst;
    std::copy(std::make_move_iterator(src.begin()),
              std::make_move_iterator(src.end()),
              std::back_inserter(dst));
    // src elements now in moved-from state
}

Custom Iterator

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstddef>

template <typename T>
class StepIterator {
private:
    T* ptr_;
    size_t step_;
    
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    
    StepIterator(T* ptr, size_t step) : ptr_(ptr), step_(step) {}
    
    reference operator*() const { return *ptr_; }
    pointer operator->() const { return ptr_; }
    
    StepIterator& operator++() { ptr_ += step_; return *this; }
    StepIterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }
    StepIterator& operator--() { ptr_ -= step_; return *this; }
    StepIterator operator--(int) { auto tmp = *this; --(*this); return tmp; }
    
    StepIterator& operator+=(difference_type n) { ptr_ += n * step_; return *this; }
    StepIterator& operator-=(difference_type n) { ptr_ -= n * step_; return *this; }
    
    reference operator[](difference_type n) const { return *(*this + n); }
    
    friend bool operator==(const StepIterator& a, const StepIterator& b) {
        return a.ptr_ == b.ptr_;
    }
    friend bool operator!=(const StepIterator& a, const StepIterator& b) {
        return !(a == b);
    }
    friend bool operator<(const StepIterator& a, const StepIterator& b) {
        return a.ptr_ < b.ptr_;
    }
    
    friend difference_type operator-(const StepIterator& a, const StepIterator& b) {
        return (a.ptr_ - b.ptr_) / static_cast<difference_type>(a.step_);
    }
    
    friend StepIterator operator+(const StepIterator& it, difference_type n) {
        auto tmp = it;
        tmp += n;
        return tmp;
    }
    friend StepIterator operator-(const StepIterator& it, difference_type n) {
        auto tmp = it;
        tmp -= n;
        return tmp;
    }
};

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Every 2nd element starting from index 1
    StepIterator<int> start(arr + 1, 2);
    StepIterator<int> end(arr + 10, 2);
    
    std::copy(start, end, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";  // 2 4 6 8 10
}

Iterator Traits

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <type_traits>

template <typename Iter>
void advance(Iter& it, int n) {
    using category = typename std::iterator_traits<Iter>::iterator_category;
    
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, category>) {
        it += n;  // O(1)
    } else if constexpr (std::is_base_of_v<std::bidirectional_iterator_tag, category>) {
        if (n >= 0) while (n--) ++it;
        else while (n++) --it;
    } else {
        while (n--) ++it;  // forward only
    }
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    auto vit = vec.begin();
    advance(vit, 3);  // O(1) for vector
    std::cout << "vec[3]: " << *vit << "\n";
    
    auto lit = lst.begin();
    advance(lit, 3);  // O(n) for list
    std::cout << "list[3]: " << *lit << "\n";
}

Common Mistakes

Mistake 1: Invalidating Iterators

std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // may invalidate it (reallocation)
*it = 5;  // undefined behavior

Mistake 2: Dereferencing End Iterator

auto it = v.end();
// *it = 5;  // undefined behavior

Mistake 3: Using Invalidated insert_iterator

auto ins = std::inserter(v, v.begin());
v.clear();
*ins = 5;  // iterator points to invalid position

Mistake 4: Passing Wrong Iterator Category to Algorithm

std::forward_list<int> fl;
// std::sort(fl.begin(), fl.end());  // Error: needs random access

Mistake 5: Forgetting difference_type for Custom Iterators

Algorithms use difference_type for distance calculations. Always define it.

Mistake 6: Assuming Contiguous Storage

auto it = vec.begin();
int* ptr = &(*it);  // OK for vector, UB for deque

Use vec.data() for guaranteed contiguous access.

Practice Questions

  1. What are the five iterator categories in C++?
  2. Which iterator category does std::list provide?
  3. Write a custom filter_iterator that skips elements not matching a predicate.
  4. What is the difference between std::begin() and std::cbegin()?
  5. How do std::reverse_iterator and std::move_iterator transform iteration?

Challenge

Implement a zip_iterator that iterates over two containers simultaneously, yielding pairs of elements. It should satisfy forward iterator requirements. Test it with std::copy and std::ostream_iterator.

FAQ

What is the 'contiguous iterator' category?

C++17 added contiguous_iterator_tag for iterators where elements are stored contiguously in memory (vector, array, string). This enables optimizations like memcpy.

Can I use range-based for with custom iterators?

Yes. If your type provides begin() and end() that return iterators, range-based for works.

What is the difference between `iterator` and `const_iterator`?

const_iterator does not allow modification of the pointed-to element. It is returned by cbegin() and cend().

What does `std::distance` do?

It computes the number of elements between two iterators. For random access iterators, it is O(1). For others, O(n).

Why does `std::list` not have random access iterators?

Linked list nodes are not stored contiguously. Supporting random access would require a different data structure (like a skip list).

What is the purpose of `std::iterator_traits`?

It allows algorithms to determine properties of an iterator type (category, value_type, difference_type) through a uniform interface, enabling compile-time dispatch.

Mini Project

Build a repeating_view that cycles through elements indefinitely:

#include <iostream>
#include <ranges>
#include <vector>
#include <algorithm>

template <std::ranges::forward_range R>
class RepeatingView : public std::ranges::view_interface<RepeatingView<R>> {
private:
    R base_;
    std::ranges::iterator_t<R> current_;
    std::ranges::iterator_t<R> begin_;
    std::ranges::sentinel_t<R> end_;
    
public:
    struct Sentinel {};
    
    struct Iterator {
    private:
        R* base_;
        std::ranges::iterator_t<R> current_;
        
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = std::ranges::range_value_t<R>;
        using difference_type = std::ptrdiff_t;
        
        Iterator(R& base, std::ranges::iterator_t<R> it)
            : base_(&base), current_(it) {}
        
        auto operator*() const { return *current_; }
        
        Iterator& operator++() {
            ++current_;
            if (current_ == std::ranges::end(*base_)) {
                current_ = std::ranges::begin(*base_);
            }
            return *this;
        }
        
        Iterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }
        
        bool operator==(const Sentinel&) const { return false; }
        bool operator!=(const Sentinel&) const { return true; }
    };
    
    RepeatingView(R base) : base_(std::move(base)),
        current_(std::ranges::begin(base_)),
        begin_(std::ranges::begin(base_)),
        end_(std::ranges::end(base_)) {}
    
    Iterator begin() { return Iterator(base_, begin_); }
    Sentinel end() { return {}; }
};

int main() {
    std::vector<int> v = {1, 2, 3};
    RepeatingView repeated(v);
    
    auto it = repeated.begin();
    for (int i = 0; i < 10; ++i, ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";  // 1 2 3 1 2 3 1 2 3 1
}

What's Next

Iterator categories determine algorithm compatibility. The next lesson begins Module 6 on Templates and Metaprogramming, starting with function templates: template syntax, type deduction, and template overloading.

← Previous Ranges Library — std::ranges, Views, Pipe Operator, Range Adaptors Next → Function Templates — Template Parameters, Type Deduction, Overloading

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp