STL Iterators

Not all iterators are created equal. C++ defines five iterator categories, each with different capabilities. Understanding these categories helps you choose the right algorithms and write more efficient code.

The Iterator Hierarchy

Iterator categories form a hierarchy where each level inherits capabilities from the level below and adds new ones. Random Access iterators can do everything, while Input iterators are the most limited. The category determines which algorithms can use that iterator.

Input Iterator

Input iterators are read-only and single-pass - you can read each element only once as you move forward. Think of reading from a keyboard or network stream where data comes in sequentially and cannot be re-read. They support *it (read), ++it, and ==/!= comparison.

#include <iostream>
#include <iterator>
#include <sstream>
using namespace std;

int main() {
    // Input iterator from a string stream
    istringstream input("10 20 30 40 50");
    
    istream_iterator<int> it(input);  // Points to first value
    istream_iterator<int> end;         // End-of-stream iterator
    
    cout << "Reading with input iterator: ";
    while (it != end) {
        cout << *it << " ";  // Read value
        ++it;                // Move to next (single-pass!)
    }
    cout << endl;
    // Output: Reading with input iterator: 10 20 30 40 50
    
    return 0;
}

Input iterators are the most restricted type. Once you move past an element with ++it, you cannot go back to read it again. This models streams like keyboard input or file reading. The istream_iterator is a classic example - it reads values from an input stream one at a time.

Output Iterator

Output iterators are write-only and single-pass - you can write to each position only once. They're like writing to a printer or network connection. They support *it = value (write) and ++it, but you cannot read from them or compare them.

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

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    
    // Output iterator to cout
    cout << "Output to console: ";
    ostream_iterator<int> out(cout, " ");
    
    for (int n : source) {
        *out = n;  // Write value
        ++out;     // Move to next position
    }
    cout << endl;
    // Output: Output to console: 1 2 3 4 5
    
    // back_inserter is also an output iterator
    vector<int> dest;
    copy(source.begin(), source.end(), back_inserter(dest));
    
    cout << "Copied to vector: ";
    for (int n : dest) cout << n << " ";
    cout << endl;
    // Output: Copied to vector: 1 2 3 4 5
    
    return 0;
}

Output iterators write values but cannot read them back. The ostream_iterator writes to output streams, and back_inserter appends to containers. These are commonly used with algorithms like copy() to output results.

Forward Iterator

Forward iterators combine input and output capabilities and allow multiple passes through the data. You can read, write, and traverse forward multiple times. However, you still cannot move backward. forward_list and unordered containers provide forward iterators.

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

int main() {
    forward_list<int> flist = {10, 20, 30, 40, 50};
    
    // Forward iterator - can only move forward
    auto it = flist.begin();
    
    cout << "First pass: ";
    while (it != flist.end()) {
        cout << *it << " ";
        ++it;  // Only ++ is available, not --
    }
    cout << endl;
    // Output: First pass: 10 20 30 40 50
    
    // Multi-pass: can traverse again
    cout << "Second pass: ";
    for (auto it2 = flist.begin(); it2 != flist.end(); ++it2) {
        *it2 *= 2;  // Can read AND write
        cout << *it2 << " ";
    }
    cout << endl;
    // Output: Second pass: 20 40 60 80 100
    
    // Note: it-- would NOT compile for forward_list!
    
    return 0;
}

Forward iterators are multi-pass (unlike input/output iterators) so you can save a copy and revisit elements. They support both reading and writing. The forward_list is a singly-linked list that only supports forward traversal, making it memory-efficient but limited to forward iteration.

Bidirectional Iterator

Bidirectional iterators add backward movement with the -- operator. You can traverse in both directions, which enables algorithms like reverse iteration. list, set, and map provide bidirectional iterators.

#include <iostream>
#include <list>
#include <set>
using namespace std;

int main() {
    list<int> numbers = {10, 20, 30, 40, 50};
    
    // Bidirectional - can go forward AND backward
    auto it = numbers.end();  // Past the last element
    
    cout << "Backward traversal: ";
    while (it != numbers.begin()) {
        --it;  // Move backward first (since end() is past-the-end)
        cout << *it << " ";
    }
    cout << endl;
    // Output: Backward traversal: 50 40 30 20 10
    
    // Set also has bidirectional iterators
    set<string> words = {"apple", "banana", "cherry"};
    
    cout << "Set backward: ";
    auto sit = words.end();
    while (sit != words.begin()) {
        --sit;
        cout << *sit << " ";
    }
    cout << endl;
    // Output: Set backward: cherry banana apple
    
    return 0;
}

Bidirectional iterators support --it in addition to ++it. This is necessary for containers like list (doubly-linked) and tree-based containers (set, map). Note the pattern for backward iteration: start at end() and decrement first before dereferencing.

Random Access Iterator

Random access iterators are the most powerful - they support all operations including arithmetic (it + n, it - n), subscript (it[n]), and comparison (<, >, etc.). This enables O(1) jumps to any position. vector, deque, and arrays provide these.

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50, 60, 70};
    
    auto it = nums.begin();
    
    // Jump forward by n positions
    cout << "it + 3: " << *(it + 3) << endl;      // 40
    
    // Jump backward
    auto it2 = nums.end();
    cout << "end - 2: " << *(it2 - 2) << endl;    // 60
    
    // Subscript access
    cout << "it[4]: " << it[4] << endl;            // 50
    
    // Calculate distance
    auto first = nums.begin();
    auto last = nums.end();
    cout << "Distance: " << (last - first) << endl; // 7
    
    // Comparison operators
    auto mid = nums.begin() + 3;
    cout << "begin < mid: " << (first < mid) << endl;   // 1 (true)
    cout << "mid < end: " << (mid < last) << endl;      // 1 (true)
    
    // Compound assignment
    it += 2;
    cout << "After it += 2: " << *it << endl;     // 30
    it -= 1;
    cout << "After it -= 1: " << *it << endl;     // 20
    
    return 0;
}

Random access iterators behave almost exactly like pointers. You can do pointer arithmetic (it + n), compute distances (it2 - it1), use subscript notation (it[n]), and compare with <, >, etc. This enables efficient algorithms like binary search and random shuffling. Only contiguous containers (vector, deque, array) support this.

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

int main() {
    vector<int> vec = {10, 20, 30, 40, 50};
    list<int> lst = {10, 20, 30, 40, 50};
    
    auto vit = vec.begin();
    auto lit = lst.begin();
    
    cout << "=== Vector (Random Access Iterator) ===" << endl;
    
    // All these work for vector:
    cout << "*(vit + 3): " << *(vit + 3) << endl;  // 40 - arithmetic
    cout << "vit[2]: " << vit[2] << endl;          // 30 - subscript
    ++vit;
    --vit;                                          // decrement works
    cout << "After ++, --: " << *vit << endl;      // 10
    
    auto vit2 = vec.begin() + 3;
    cout << "vit < vit2: " << (vit < vit2) << endl; // 1 - comparison
    
    cout << "\n=== List (Bidirectional Iterator) ===" << endl;
    
    // These work for list:
    ++lit;
    --lit;                                          // decrement works
    cout << "After ++, --: " << *lit << endl;      // 10
    cout << "lit == lst.begin(): " << (lit == lst.begin()) << endl; // 1
    
    // These DON'T work for list (would not compile):
    // cout << *(lit + 3);     // ERROR: no operator+
    // cout << lit[2];         // ERROR: no operator[]
    // cout << (lit < lit2);   // ERROR: no operator<
    
    cout << "\n(lit + 3, lit[2], and lit < lit2 would NOT compile for list)" << endl;
    
    return 0;
}
// Output:
// === Vector (Random Access Iterator) ===
// *(vit + 3): 40
// vit[2]: 30
// After ++, --: 10
// vit < vit2: 1
// === List (Bidirectional Iterator) ===
// After ++, --: 10
// lit == lst.begin(): 1
// (lit + 3, lit[2], and lit < lit2 would NOT compile for list)

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

int main() {
    forward_list<int> flist = {1, 2, 3, 4, 5};
    
    // Print all elements
    cout << "Original: ";
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // Output: Original: 1 2 3 4 5
    
    // Double each element (forward iterator supports read AND write)
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        *it = *it * 2;
    }
    
    // Print again
    cout << "Doubled: ";
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // Output: Doubled: 2 4 6 8 10
    
    // Note: This would NOT compile:
    // auto it = flist.end();
    // --it;  // ERROR: forward_list iterators don't support --
    
    cout << "\nForward iterators support ++ but not --" << endl;
    
    return 0;
}

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

int main() {
    vector<int> nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 1. Every other element starting from index 0
    cout << "Every other element: ";
    for (auto it = nums.begin(); it < nums.end(); it += 2) {
        cout << *it << " ";
    }
    cout << endl;
    // Output: Every other element: 0 2 4 6 8
    
    // 2. Elements from index 2 to 7 using iterator subtraction
    auto start = nums.begin() + 2;
    auto stop = nums.begin() + 8;  // 8 because end is exclusive
    
    cout << "Elements [2,7]: ";
    for (auto it = start; it < stop; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    cout << "Count (using subtraction): " << (stop - start) << endl;
    // Output: Elements [2,7]: 2 3 4 5 6 7
    // Count (using subtraction): 6
    
    // 3. Middle element using arithmetic
    auto mid = nums.begin() + nums.size() / 2;
    cout << "Middle element (index " << (mid - nums.begin()) << "): " << *mid << endl;
    // Output: Middle element (index 5): 5
    
    // Alternative: using distance from both ends
    auto middle = nums.begin() + (nums.end() - nums.begin()) / 2;
    cout << "Middle (alternative): " << *middle << endl;
    
    return 0;
}

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

int main() {
    list<string> words = {"one", "two", "three", "four", "five"};
    
    // Backward traversal using --
    cout << "Backward: ";
    auto it = words.end();
    while (it != words.begin()) {
        --it;  // Decrement first since end() is past-the-end
        cout << *it << " ";
    }
    cout << endl;
    // Output: Backward: five four three two one
    
    // Forward traversal - last 3 elements only
    // For bidirectional iterators, we need to manually advance
    cout << "Last 3 elements: ";
    
    // Start at end and go back 3 positions
    it = words.end();
    --it; --it; --it;  // Now at "three"
    
    while (it != words.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // Output: Last 3 elements: three four five
    
    // Alternative using advance (works with any iterator category)
    cout << "Using advance: ";
    it = words.begin();
    advance(it, 2);  // Move to index 2 ("three")
    while (it != words.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // Output: Using advance: three four five
    
    return 0;
}

The STL provides utility functions for working with iterators that make your code cleaner and more portable. Functions like advance(), distance(), next(), and prev() work with any iterator type and optimize based on the iterator's capabilities.

std::distance() - Count Elements

The std::distance(first, last) function returns the number of increments needed to get from first to last. For random access iterators, this is O(1) using subtraction. For other iterators, it's O(n) requiring actual iteration.

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

int main() {
    vector<int> vec = {10, 20, 30, 40, 50};
    list<int> lst = {10, 20, 30, 40, 50};
    
    // For vector: O(1) - uses subtraction internally
    auto dist1 = distance(vec.begin(), vec.end());
    cout << "Vector distance: " << dist1 << endl;  // 5
    
    // For list: O(n) - must count each increment
    auto dist2 = distance(lst.begin(), lst.end());
    cout << "List distance: " << dist2 << endl;    // 5
    
    // Distance to specific position
    auto it = vec.begin();
    advance(it, 3);
    cout << "Distance from begin to it: " << distance(vec.begin(), it) << endl;  // 3
    
    return 0;
}

std::advance() - Move Iterator

The std::advance(it, n) function moves an iterator n positions. Unlike it + n, this works with all forward iterators, not just random access. For random access iterators, it's O(1). For bidirectional, it can go backward with negative n. For forward, only positive n works.

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

int main() {
    vector<int> vec = {10, 20, 30, 40, 50, 60, 70};
    list<int> lst = {10, 20, 30, 40, 50, 60, 70};
    
    // Advance on vector (random access) - O(1)
    auto vit = vec.begin();
    advance(vit, 3);
    cout << "Vector after advance(3): " << *vit << endl;  // 40
    
    // Advance on list (bidirectional) - O(n)
    auto lit = lst.begin();
    advance(lit, 3);
    cout << "List after advance(3): " << *lit << endl;    // 40
    
    // Negative advance (works for bidirectional and random access)
    advance(vit, -2);
    cout << "Vector after advance(-2): " << *vit << endl; // 20
    
    advance(lit, -2);
    cout << "List after advance(-2): " << *lit << endl;   // 20
    
    // Note: advance modifies the iterator in place (returns void)
    
    return 0;
}

Note that advance() modifies the iterator in place and returns void. If you need a new iterator without modifying the original, use std::next() or std::prev() instead.

std::next() and std::prev() - Get Adjacent Iterator

C++11 introduced std::next(it, n) and std::prev(it, n) which return a new iterator without modifying the original. The default for n is 1. These are safer and more readable than advance() when you need the original iterator preserved.

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

int main() {
    vector<int> vec = {10, 20, 30, 40, 50};
    
    auto it = vec.begin();
    
    // next() returns a new iterator, original unchanged
    auto it2 = next(it);      // Move 1 forward (default)
    auto it3 = next(it, 3);   // Move 3 forward
    
    cout << "*it: " << *it << endl;   // 10 (unchanged!)
    cout << "*it2: " << *it2 << endl; // 20
    cout << "*it3: " << *it3 << endl; // 40
    
    // prev() moves backward
    auto it4 = prev(vec.end());       // Last element
    auto it5 = prev(vec.end(), 2);    // Second to last
    
    cout << "*it4: " << *it4 << endl; // 50
    cout << "*it5: " << *it5 << endl; // 40
    
    // Useful pattern: iterate over all but first/last
    cout << "All but first and last: ";
    for (auto iter = next(vec.begin()); iter != prev(vec.end()); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;  // 20 30 40
    
    return 0;
}

std::begin() and std::end() - Unified Interface

The free functions std::begin() and std::end() (C++11) provide a unified way to get iterators from both STL containers and raw arrays. This enables writing generic code that works with any iterable type.

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

// Generic function that works with ANY iterable
template<typename Container>
void printAll(const Container& c) {
    for (auto it = begin(c); it != end(c); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    // Works with STL containers
    vector<int> vec = {1, 2, 3, 4, 5};
    printAll(vec);  // 1 2 3 4 5
    
    // Works with raw arrays!
    int arr[] = {10, 20, 30, 40, 50};
    printAll(arr);  // 10 20 30 40 50
    
    // Use with algorithms
    sort(begin(arr), end(arr), greater<int>());
    printAll(arr);  // 50 40 30 20 10
    
    // Also: cbegin/cend for const, rbegin/rend for reverse
    cout << "Reverse: ";
    for (auto it = rbegin(vec); it != rend(vec); ++it) {
        cout << *it << " ";
    }
    cout << endl;  // 5 4 3 2 1
    
    return 0;
}

Always prefer std::begin()/std::end() in generic code. For C++14 and later, you also have std::cbegin()/std::cend() (const) and std::rbegin()/std::rend() (reverse). C++17 adds std::size(), std::empty(), and std::data().

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

int main() {
    vector<int> nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // Find distance between index 2 and index 7 (inclusive)
    auto pos2 = nums.begin() + 2;  // Points to element 2
    auto pos7 = nums.begin() + 8;  // Points past element 7 (for inclusive range)
    
    auto count = distance(pos2, pos7);
    cout << "Elements from index 2 to 7 (inclusive): " << count << endl;
    // Output: Elements from index 2 to 7 (inclusive): 6
    
    // Move iterator to middle element
    auto it = nums.begin();
    advance(it, nums.size() / 2);
    
    cout << "Middle element (index " << distance(nums.begin(), it) << "): " << *it << endl;
    // Output: Middle element (index 5): 5
    
    return 0;
}

#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> letters = {"A", "B", "C", "D", "E"};
    
    // 1. Second element using next()
    auto second = next(letters.begin());
    cout << "Second element: " << *second << endl;
    // Output: Second element: B
    
    // 2. Second-to-last element using prev()
    auto secondLast = prev(letters.end(), 2);
    cout << "Second-to-last: " << *secondLast << endl;
    // Output: Second-to-last: D
    
    // 3. Elements B, C, D (skip first and last)
    cout << "Middle elements: ";
    for (auto it = next(letters.begin()); it != prev(letters.end()); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // Output: Middle elements: B C D
    
    return 0;
}

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

template<typename Container>
auto findMax(const Container& c) {
    auto maxIt = begin(c);
    for (auto it = begin(c); it != end(c); ++it) {
        if (*it > *maxIt) {
            maxIt = it;
        }
    }
    return *maxIt;
}

int main() {
    // Test with vector
    vector<int> vec = {34, 67, 23, 89, 45, 12};
    cout << "Vector max: " << findMax(vec) << endl;
    // Output: Vector max: 89
    
    // Test with raw array
    int arr[] = {15, 82, 43, 91, 27, 56};
    cout << "Array max: " << findMax(arr) << endl;
    // Output: Array max: 91
    
    // Test with different type
    double doubles[] = {3.14, 2.71, 1.41, 1.73};
    cout << "Double array max: " << findMax(doubles) << endl;
    // Output: Double array max: 3.14
    
    return 0;
}

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

pair<int, size_t> maxWindowSum(const vector<int>& nums, int windowSize) {
    if (distance(nums.begin(), nums.end()) < windowSize) {
        return {0, 0};  // Not enough elements
    }
    
    int maxSum = 0;
    size_t maxIndex = 0;
    
    // Calculate initial window sum
    int currentSum = 0;
    auto windowEnd = nums.begin();
    advance(windowEnd, windowSize);
    for (auto it = nums.begin(); it != windowEnd; ++it) {
        currentSum += *it;
    }
    maxSum = currentSum;
    
    // Slide the window
    auto left = nums.begin();
    auto right = windowEnd;
    
    while (right != nums.end()) {
        currentSum -= *left;  // Remove leftmost
        currentSum += *right; // Add rightmost
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            maxIndex = distance(nums.begin(), next(left));
        }
        
        ++left;
        ++right;
    }
    
    return {maxSum, maxIndex};
}

int main() {
    vector<int> nums = {2, 1, 5, 1, 3, 2, 8, 1, 4};
    
    auto [maxSum, startIdx] = maxWindowSum(nums, 3);
    
    cout << "Max sum of 3 consecutive: " << maxSum << endl;
    cout << "Starting at index: " << startIdx << endl;
    cout << "Elements: ";
    for (int i = 0; i < 3; ++i) {
        cout << nums[startIdx + i] << " ";
    }
    cout << endl;
    // Output:
    // Max sum of 3 consecutive: 13
    // Starting at index: 5
    // Elements: 2 8 1
    
    return 0;
}

Beyond regular iterators, C++ provides specialized iterator types for specific use cases. Reverse iterators traverse containers backward, const iterators prevent modification, and stream iterators connect containers to I/O streams.

Reverse Iterators

Reverse iterators traverse containers from end to beginning. Every container with bidirectional iterators provides rbegin() and rend(). The rbegin() points to the last element, and rend() points before the first element.

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    
    // Reverse iteration with rbegin/rend
    cout << "Reverse: ";
    for (auto rit = nums.rbegin(); rit != nums.rend(); ++rit) {
        cout << *rit << " ";  // Note: ++ moves backward!
    }
    cout << endl;  // 50 40 30 20 10
    
    // Range-based for with reverse adaptor (C++20)
    // for (int n : nums | views::reverse) { ... }
    
    // Find last occurrence using reverse iterator
    auto it = find(nums.rbegin(), nums.rend(), 30);
    if (it != nums.rend()) {
        cout << "Found 30 at reverse position: " << distance(nums.rbegin(), it) << endl;
    }
    
    // Convert reverse iterator to regular iterator using base()
    auto regular = it.base();  // Points to element AFTER the one rit points to
    cout << "Element after 30: " << *regular << endl;  // 40
    
    return 0;
}

Const Iterators

Const iterators (const_iterator) allow reading elements but prevent modification. Use cbegin()/cend() to get const iterators. This enforces const-correctness and signals intent to readers.

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

void printVector(const vector<int>& v) {
    // On const containers, begin() returns const_iterator automatically
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
        // *it = 100;  // ERROR: cannot modify through const_iterator
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    // Explicitly get const iterators with cbegin/cend
    for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
        cout << *it << " ";
        // *it = 10;  // ERROR: const_iterator prevents modification
    }
    cout << endl;
    
    // Regular iterator - can modify
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        *it *= 2;  // OK: regular iterator allows modification
    }
    
    printVector(nums);  // 2 4 6 8 10
    
    return 0;
}

Best practice: Use cbegin()/cend() when you don't need to modify elements. This makes your intent clear and can catch accidental modifications at compile time.

Stream Iterators

Stream iterators connect I/O streams to the iterator interface. istream_iterator reads from input streams, and ostream_iterator writes to output streams. This enables using algorithms directly with streams.

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    // Read integers from string stream
    istringstream input("10 20 30 40 50");
    vector<int> nums;
    
    // Copy from stream to vector using istream_iterator
    copy(istream_iterator<int>(input),
         istream_iterator<int>(),  // End-of-stream (default constructed)
         back_inserter(nums));
    
    cout << "Read from stream: ";
    for (int n : nums) cout << n << " ";
    cout << endl;  // 10 20 30 40 50
    
    // Write to cout using ostream_iterator
    cout << "Output with separator: ";
    copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, ", "));
    cout << endl;  // 10, 20, 30, 40, 50,
    
    // Transform and output
    cout << "Doubled: ";
    transform(nums.begin(), nums.end(),
              ostream_iterator<int>(cout, " "),
              [](int x) { return x * 2; });
    cout << endl;  // 20 40 60 80 100
    
    return 0;
}

Insert Iterators

Insert iterators automatically grow containers when assigned to. back_inserter appends to the end, front_inserter prepends to the front, and inserter inserts at a specified position.

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    
    // back_inserter: append to end
    vector<int> v1;
    copy(source.begin(), source.end(), back_inserter(v1));
    cout << "back_inserter: ";
    for (int n : v1) cout << n << " ";
    cout << endl;  // 1 2 3 4 5
    
    // front_inserter: prepend to front (reverses order!)
    list<int> lst;  // Note: vector doesn't support push_front
    copy(source.begin(), source.end(), front_inserter(lst));
    cout << "front_inserter: ";
    for (int n : lst) cout << n << " ";
    cout << endl;  // 5 4 3 2 1
    
    // inserter: insert at position
    vector<int> v2 = {100, 200};
    copy(source.begin(), source.end(), inserter(v2, v2.begin() + 1));
    cout << "inserter at pos 1: ";
    for (int n : v2) cout << n << " ";
    cout << endl;  // 100 1 2 3 4 5 200
    
    return 0;
}

Insert iterators are essential when using algorithms that write output. Without them, you would need to pre-allocate space in the destination container. Note that front_inserter reverses the order because each element is inserted at the front.

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

int main() {
    vector<string> words = {"one", "two", "three", "four", "five"};
    
    // Print in reverse order
    cout << "Reversed: ";
    for (auto rit = words.rbegin(); rit != words.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    // Output: Reversed: five four three two one
    
    // Find "three" using reverse iterator
    auto found = find(words.rbegin(), words.rend(), "three");
    
    if (found != words.rend()) {
        auto posFromEnd = distance(words.rbegin(), found);
        cout << "Found 'three' at position " << posFromEnd << " from end" << endl;
        // Output: Found 'three' at position 2 from end
    }
    
    return 0;
}

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

// Using cbegin/cend ensures we don't modify elements
int sumElements(const vector<int>& nums) {
    int sum = 0;
    for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
        sum += *it;
        // *it = 0;  // Would NOT compile - const_iterator prevents modification
    }
    return sum;
}

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50};
    
    cout << "Sum: " << sumElements(numbers) << endl;
    // Output: Sum: 150
    
    // Original vector unchanged (guaranteed by const_iterator)
    cout << "First element still: " << numbers[0] << endl;
    // Output: First element still: 10
    
    return 0;
}

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

int main() {
    istringstream input("3.14 2.71 1.41 1.73");
    vector<double> nums;
    
    // Read from stream
    copy(istream_iterator<double>(input),
         istream_iterator<double>(),
         back_inserter(nums));
    
    cout << "Original: ";
    copy(nums.begin(), nums.end(), ostream_iterator<double>(cout, " "));
    cout << endl;
    // Output: Original: 3.14 2.71 1.41 1.73
    
    // Square each and output with separator
    cout << "Squared: ";
    transform(nums.begin(), nums.end(),
              ostream_iterator<double>(cout, " | "),
              [](double x) { return x * x; });
    cout << endl;
    // Output: Squared: 9.8596 | 7.3441 | 1.9881 | 2.9929 |
    
    return 0;
}

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

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    
    // Copy only even numbers
    vector<int> evens;
    copy_if(source.begin(), source.end(),
            back_inserter(evens),
            [](int x) { return x % 2 == 0; });
    
    cout << "Evens: ";
    for (int n : evens) cout << n << " ";
    cout << endl;
    // Output: Evens: 2 4
    
    // Triple all numbers
    vector<int> tripled;
    transform(source.begin(), source.end(),
              back_inserter(tripled),
              [](int x) { return x * 3; });
    
    cout << "Tripled: ";
    for (int n : tripled) cout << n << " ";
    cout << endl;
    // Output: Tripled: 3 6 9 12 15
    
    return 0;
}

Using iterators correctly is essential for writing safe, efficient, and maintainable C++ code. This section covers common pitfalls, iterator invalidation rules, and modern C++ iterator patterns that will make you a better programmer.

Iterator Invalidation

Iterator invalidation is one of the most dangerous pitfalls in C++. When a container is modified, some or all iterators pointing into it may become invalid. Using an invalid iterator leads to undefined behavior (crashes, data corruption, or seemingly random errors).

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

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    // DANGEROUS: iterator invalidation
    auto it = nums.begin() + 2;  // Points to 3
    cout << "Before push_back: " << *it << endl;  // 3
    
    nums.push_back(6);  // May reallocate!
    // cout << *it;     // UNDEFINED BEHAVIOR - it may be invalid!
    
    // SAFE: Re-acquire iterator after modification
    it = nums.begin() + 2;
    cout << "After re-acquiring: " << *it << endl;  // 3
    
    // COMMON BUG: Erase in loop
    // for (auto it = nums.begin(); it != nums.end(); ++it) {
    //     if (*it % 2 == 0) nums.erase(it);  // BUG: it invalidated!
    // }
    
    // CORRECT: Use return value of erase
    for (auto it = nums.begin(); it != nums.end(); ) {
        if (*it % 2 == 0) {
            it = nums.erase(it);  // erase returns iterator to next element
        } else {
            ++it;
        }
    }
    
    cout << "After removing evens: ";
    for (int n : nums) cout << n << " ";
    cout << endl;  // 1 3 5
    
    return 0;
}

Modern C++ Iterator Patterns

Modern C++ (C++11 and later) provides cleaner ways to work with iterators. Range-based for loops, auto type deduction, and structured bindings make code more readable and less error-prone.

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    map<string, int> scores = {{"Alice", 95}, {"Bob", 87}, {"Carol", 92}};
    
    // Old style (verbose)
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Modern: auto (C++11)
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        *it *= 2;  // Can modify
    }
    
    // Modern: range-based for (C++11) - preferred for simple iteration
    for (const auto& n : nums) {  // const& prevents copy and modification
        cout << n << " ";
    }
    cout << endl;  // 20 40 60 80 100
    
    // Structured bindings with maps (C++17)
    for (const auto& [name, score] : scores) {
        cout << name << ": " << score << endl;
    }
    
    // When you need the iterator (index, erase, etc.), use traditional loop
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        cout << "Index " << distance(nums.begin(), it) << ": " << *it << endl;
    }
    
    return 0;
}

Performance Considerations

Choosing the right iterator operations and patterns can significantly impact performance. Understanding time complexity and avoiding unnecessary copies is essential.

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

int main() {
    vector<int> vec(1000000);
    list<int> lst(1000000);
    
    // O(1) for vector, O(n) for list
    auto vec_mid = vec.begin();
    advance(vec_mid, 500000);  // Fast for vector
    
    auto lst_mid = lst.begin();
    advance(lst_mid, 500000);  // Slow for list - must traverse
    
    // PREFER: Use container-specific methods when available
    // vec.erase(vec.begin()) is O(n) - shifts all elements
    // lst.erase(lst.begin()) is O(1) - just relinks nodes
    
    // EFFICIENT: Reserve capacity to avoid reallocation
    vector<int> nums;
    nums.reserve(1000);  // Pre-allocate
    for (int i = 0; i < 1000; ++i) {
        nums.push_back(i);  // No reallocation, iterators stay valid
    }
    
    // EFFICIENT: Use emplace instead of insert for objects
    vector<pair<int, string>> pairs;
    pairs.emplace_back(1, "one");  // Constructs in place
    // vs pairs.push_back(make_pair(1, "one")); // Creates temporary
    
    cout << "Optimization examples complete" << endl;
    
    return 0;
}

vector<int> nums = {30, 60, 20, 80, 40, 70, 10};
for (auto it = nums.begin(); it != nums.end(); ++it) {
    if (*it > 50) {
        nums.erase(it);  // BUG!
    }
}

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

int main() {
    vector<int> nums = {30, 60, 20, 80, 40, 70, 10};
    
    // FIXED: Use erase return value, don't increment when erasing
    for (auto it = nums.begin(); it != nums.end(); ) {
        if (*it > 50) {
            it = nums.erase(it);  // Returns iterator to next element
        } else {
            ++it;  // Only increment if we didn't erase
        }
    }
    
    cout << "After removing > 50: ";
    for (int n : nums) cout << n << " ";
    cout << endl;
    // Output: After removing > 50: 30 20 40 10
    
    // Alternative using erase-remove idiom (more idiomatic)
    vector<int> nums2 = {30, 60, 20, 80, 40, 70, 10};
    nums2.erase(
        remove_if(nums2.begin(), nums2.end(), [](int x) { return x > 50; }),
        nums2.end()
    );
    
    cout << "Using erase-remove: ";
    for (int n : nums2) cout << n << " ";
    cout << endl;
    // Output: Using erase-remove: 30 20 40 10
    
    return 0;
}

map<string, int> ages;
ages["Alice"] = 25; ages["Bob"] = 30; ages["Carol"] = 28;
for (map<string, int>::iterator it = ages.begin(); it != ages.end(); ++it) {
    cout << (*it).first << " is " << (*it).second << " years old" << endl;
}

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

int main() {
    map<string, int> ages = {{"Alice", 25}, {"Bob", 30}, {"Carol", 28}};
    
    // Modern C++11: range-based for with auto
    cout << "C++11 style:" << endl;
    for (const auto& pair : ages) {
        cout << pair.first << " is " << pair.second << " years old" << endl;
    }
    
    // Modern C++17: structured bindings
    cout << "\nC++17 style:" << endl;
    for (const auto& [name, age] : ages) {
        cout << name << " is " << age << " years old" << endl;
    }
    
    // When modification is needed
    cout << "\nAfter birthday:" << endl;
    for (auto& [name, age] : ages) {
        age++;  // Modify through reference
    }
    for (const auto& [name, age] : ages) {
        cout << name << " is " << age << " years old" << endl;
    }
    
    return 0;
}

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

void processNumbers(vector<int>& nums) {
    // Method 1: Two-pass approach (safer, cleaner)
    // First remove negatives, then double positives
    
    // Remove negatives using erase-remove
    nums.erase(
        remove_if(nums.begin(), nums.end(), [](int x) { return x < 0; }),
        nums.end()
    );
    
    // Double all remaining (positive) numbers
    for (int& n : nums) {
        n *= 2;
    }
}

void processNumbersSinglePass(vector<int>& nums) {
    // Method 2: Single pass with careful iterator handling
    for (auto it = nums.begin(); it != nums.end(); ) {
        if (*it < 0) {
            it = nums.erase(it);  // Remove negative
        } else {
            *it *= 2;  // Double positive
            ++it;
        }
    }
}

int main() {
    vector<int> nums1 = {-5, 10, -3, 20, 0, -8, 15};
    vector<int> nums2 = nums1;  // Copy for second test
    
    processNumbers(nums1);
    cout << "Two-pass result: ";
    for (int n : nums1) cout << n << " ";
    cout << endl;
    // Output: Two-pass result: 20 40 0 30
    
    processNumbersSinglePass(nums2);
    cout << "Single-pass result: ";
    for (int n : nums2) cout << n << " ";
    cout << endl;
    // Output: Single-pass result: 20 40 0 30
    
    return 0;
}

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

struct Person {
    string name;
    int age;
    
    Person(const string& n, int a) : name(n), age(a) {}
};

int main() {
    const int SIZE = 10000;
    
    // 1. Reserve space to avoid reallocations
    vector<Person> people;
    people.reserve(SIZE);  // No iterator invalidation during population
    
    // 2. Populate efficiently with emplace_back
    for (int i = 0; i < SIZE; ++i) {
        people.emplace_back("Person" + to_string(i), i % 100);
    }
    
    // 3 & 4. Count adults efficiently without creating new container
    auto adultCount = count_if(people.cbegin(), people.cend(),
                               [](const Person& p) { return p.age >= 18; });
    
    cout << "Total people: " << people.size() << endl;
    cout << "Adults (age >= 18): " << adultCount << endl;
    
    // If we need to iterate over adults without copying:
    cout << "\nFirst 5 adults:" << endl;
    int printed = 0;
    for (auto it = people.cbegin(); it != people.cend() && printed < 5; ++it) {
        if (it->age >= 18) {
            cout << it->name << " (" << it->age << ")" << endl;
            ++printed;
        }
    }
    
    // Alternative: partition to group adults at beginning (modifies order)
    // auto adultEnd = partition(people.begin(), people.end(),
    //                          [](const Person& p) { return p.age >= 18; });
    // Now [begin, adultEnd) are adults, [adultEnd, end) are minors
    
    return 0;
}

Explore how iterators move through containers. Click the buttons to see iterator operations in action.