cpp-iterators-guide.md

C++ Iterators and Containers: A Comprehensive Guide

Table of Contents

1. Introduction to Iterators
2. Iterator Categories
3. Container Types and Their Iterators
4. Iterator Operations
5. Template Type Names and Iterator Traits
6. Best Practices and Common Patterns
7. Advanced Topics
8. Practical Examples

Introduction to Iterators

What is an Iterator?

An iterator is an object that enables traversing through elements of a container (such as arrays, vectors, lists) in a sequential manner. It acts as an abstraction that provides a common interface for accessing elements, regardless of the underlying container type.

Basic Concepts

• Iterators serve as a bridge between algorithms and containers
• They provide a way to access elements without exposing the container's internal structure
• Iterator syntax is designed to mimic pointer arithmetic
• Most iterators support at least the following operations:
  • Dereferencing (*it)
  • Increment (++it)
  • Comparison (it1 == it2)

Why Use Iterators?

1. Abstraction: Hide container implementation details
2. Uniformity: Provide a consistent interface across different containers
3. Flexibility: Enable generic programming through templates
4. Efficiency: Allow for optimal traversal based on container type

Iterator Categories

1. Input Iterator

• Capabilities: Read-only, forward-moving, single-pass
• Operations:
  • Increment (++)
  • Dereference (*) for reading
  • Comparison (==, !=)
• Example Use: Reading from a stream

std::istream_iterator<int> input_it(std::cin);
int value = *input_it;  // Read a value
++input_it;            // Move to next value

2. Output Iterator

• Capabilities: Write-only, forward-moving, single-pass
• Operations:
  • Increment (++)
  • Dereference (*) for writing
• Example Use: Writing to a stream

std::ostream_iterator<int> output_it(std::cout, " ");
*output_it = 42;  // Write value
++output_it;     // Move to next position

3. Forward Iterator

• Capabilities: Read/write, forward-moving, multi-pass
• Operations:
  • Input iterator operations
  • Multi-pass guarantee
• Example Use: Forward lists

std::forward_list<int>::iterator it;
// Can traverse multiple times
for (it = list.begin(); it != list.end(); ++it) {
    // Multiple passes allowed
}

4. Bidirectional Iterator

• Capabilities: Forward iterator + backward movement
• Operations:
  • Forward iterator operations
  • Decrement (--)
• Example Use: Doubly-linked lists, sets, maps

std::list<int>::iterator it;
++it;  // Move forward
--it;  // Move backward

5. Random Access Iterator

• Capabilities: Bidirectional iterator + random access
• Operations:
  • Bidirectional iterator operations
  • Addition/subtraction (+, -)
  • Comparison (<, >, <=, >=)
  • Subscript operator ([])
• Example Use: Vectors, arrays, deques

std::vector<int>::iterator it;
it += 5;     // Move forward 5 positions
it -= 3;     // Move backward 3 positions
if (it1 < it2) { /* ... */ }  // Compare positions

Container Types and Their Iterators

Sequential Containers

Vector

std::vector<T>
- Iterator Type: Random Access
- Common Operations:
  .begin(), .end()
  .rbegin(), .rend()
  .cbegin(), .cend()

List

std::list<T>
- Iterator Type: Bidirectional
- Common Operations:
  .begin(), .end()
  .rbegin(), .rend()

Forward List

std::forward_list<T>
- Iterator Type: Forward
- Common Operations:
  .before_begin(), .begin(), .end()

Associative Containers

Set/Map

std::set<T> / std::map<Key, Value>
- Iterator Type: Bidirectional
- Common Operations:
  .begin(), .end()
  .lower_bound(), .upper_bound()

Container Adaptors

Stack/Queue

std::stack<T> / std::queue<T>
- No built-in iterators
- Can be adapted to provide iterators through underlying container

Iterator Operations

Basic Operations

// Creation and Assignment
container::iterator it = container.begin();
container::const_iterator cit = container.cbegin();

// Movement
++it;      // Move forward one position
--it;      // Move backward one position (if bidirectional)
it += n;   // Move forward n positions (if random access)
it -= n;   // Move backward n positions (if random access)

// Access
T& value = *it;             // Access current element
T& offset_value = it[n];    // Access element at offset (if random access)

// Comparison
bool equal = (it1 == it2);
bool not_equal = (it1 != it2);
bool less = (it1 < it2);    // Only for random access iterators

Advanced Operations

// Distance calculation
std::distance(it1, it2);    // Number of elements between iterators

// Advancement
std::advance(it, n);        // Move iterator forward/backward n positions

// Next/Previous
auto next_it = std::next(it);      // Get iterator to next element
auto prev_it = std::prev(it);      // Get iterator to previous element

Template Type Names and Iterator Traits

Understanding typename

template <typename Container>
void algorithm(Container& c) {
    // Tell compiler that iterator is a type
    typename Container::iterator it = c.begin();
    
    // Without typename, compiler might think iterator is a static member
    // Container::iterator it = c.begin();  // Error
}

Iterator Traits

// Iterator traits provide information about iterator capabilities
template <typename Iterator>
void process(Iterator it) {
    typename std::iterator_traits<Iterator>::value_type value;
    typename std::iterator_traits<Iterator>::difference_type dist;
    typename std::iterator_traits<Iterator>::pointer ptr;
    typename std::iterator_traits<Iterator>::reference ref;
    typename std::iterator_traits<Iterator>::iterator_category category;
}