13.1 Introduction to Iterators

13.1.1 What Are Iterators?

An iterator is a construct that allows you to traverse a sequence of elements one at a time without exposing the underlying data structure. In Rust, iterators are central to the language's expressive data processing capabilities, enabling concise and readable code when handling collections.

Key Characteristics of Iterators:

  • Abstraction: Iterators abstract the process of traversing elements, letting you focus on what to do with the data rather than how to access it.
  • Lazy Evaluation: Many iterator operations are lazy; they don't execute until a consuming method is called.
  • Chainable Operations: Iterators can be transformed and combined using adapter methods, enabling complex data processing pipelines.
  • Trait-Based Design: The Iterator trait defines the behavior expected of any iterator, providing a consistent interface.

13.1.2 The Iterator Trait

At the core of Rust's iterator system is the Iterator trait, which defines how a type produces a sequence of values.

Definition of the Iterator Trait:

#![allow(unused)]
fn main() {
pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // Additional methods with default implementations
}
}
  • Associated Type Item: Specifies the type of elements the iterator yields.
  • Method next(): Advances the iterator and returns the next value as an Option<Self::Item>. It returns Some(item) if there's a next element or None if the iteration is complete.

Understanding Associated Types and Self::Item Syntax:

  • Associated Types: Traits can define types that are part of the trait's interface. When implementing the trait, you specify what these types are.
    • In Iterator, type Item; is an associated type that represents the element type.
  • Self::Item: Refers to the associated Item type of the implementing type. It's a way to access associated types within trait methods.

Implementing the next() method is sufficient to create a functional iterator. While next() can be called directly, it is typically used indirectly in for loops or by consuming iterator methods. We'll explore creating custom iterators in detail in Section 13.3.

13.1.3 Mutable and Immutable Iteration

Rust provides methods to create iterators that borrow items from a collection either immutably or mutably, as well as methods that consume the collection. Additionally, Rust offers iterator adapter methods that create new iterators from existing ones. The final iterator is used in for loops or with consuming methods to actually process the items.

Immutable Iteration with iter():

The iter() method borrows each element immutably.

fn main() {
    let numbers = vec![1, 2, 3];
    for number in numbers.iter() {
        println!("{}", number);
    }
}
  • Usage: When you need to read or process elements without modifying them.
  • Note: Using for number in &numbers is syntactic sugar for for number in numbers.iter().

Mutable Iteration with iter_mut():

The iter_mut() method borrows each element mutably, allowing modification.

fn main() {
    let mut numbers = vec![1, 2, 3];
    for number in numbers.iter_mut() {
        *number += 1;
    }
    println!("{:?}", numbers); // Output: [2, 3, 4]
}
  • Usage: When you need to modify elements during iteration.
  • Note: Using for number in &mut numbers is syntactic sugar for for number in numbers.iter_mut().

Consuming Iteration with into_iter():

The into_iter() method consumes the collection, taking ownership of its elements.

fn main() {
    let numbers = vec![1, 2, 3];
    for number in numbers.into_iter() {
        println!("{}", number);
    }
    // `numbers` cannot be used here as it has been moved
}
  • Usage: When you no longer need the original collection after iteration.
  • Note: Using for number in numbers is syntactic sugar for for number in numbers.into_iter().

Key Differences:

  • iter(): Borrows elements immutably; the original collection remains accessible.
  • iter_mut(): Borrows elements mutably; allows modifying elements.
  • into_iter(): Consumes the collection; transfers ownership of elements.

Understanding these methods helps manage ownership and borrowing, ensuring memory safety without sacrificing performance.

13.1.4 Peculiarities of Iterator Adapters

Some iterator adapters, like map() and filter(), have nuances worth noting, especially regarding how they handle references.

Using map() with References:

When using iter(), elements are references, so closures receive references.

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3];
let result: Vec<i32> = numbers.iter().map(|&x| x * 2).collect();
println!("{:?}", result); // Output: [2, 4, 6]
}
  • Variations:
    • |&x| x * 2: Destructures the reference.
    • |x| (*x) * 2: Dereferences inside the closure.
    • |x| x * 2: Works due to auto-dereferencing with arithmetic operations.

Using filter() with References:

Closures in filter() often involve layers of references.

#![allow(unused)]
fn main() {
let numbers = [0, 1, 2];
let result: Vec<&i32> = numbers.iter().filter(|&&x| x > 1).collect();
println!("{:?}", result); // Output: [2]
}

  • Double Reference: &&x handles the reference to a reference.

  • Variations:

    • |&x| (*x) > 1: Dereferences inside the closure.

  • Simplifying References:

    • Use |&x| x > 1 if using into_iter() to consume the collection.
    • Adjust closure parameters to match the reference level.

Key Takeaways:

  • Be mindful of reference levels when using iterator adapters.
  • Destructuring references in closures can simplify code.
  • Understand how iterator methods interact with references to write cleaner code.

13.1.5 Standard Iterable Data Types

Rust's standard library provides various iterable data types that implement the Iterator trait.

Common Iterable Data Types:

  • Vectors (Vec<T>):

    #![allow(unused)]
fn main() {
let vec = vec![1, 2, 3];
for num in vec.iter() {
    println!("{}", num);
}
}

  • Arrays ([T; N]):

    #![allow(unused)]
fn main() {
let arr = [10, 20, 30];
for num in arr.iter() {
    println!("{}", num);
}
}

  • Slices (&[T]):

    #![allow(unused)]
fn main() {
let slice = &[100, 200, 300];
for num in slice.iter() {
    println!("{}", num);
}
}

  • HashMaps (HashMap<K, V>):

    #![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("a", 1);
map.insert("b", 2);
for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}
}

  • Strings (String and &str):

    #![allow(unused)]
fn main() {
let s = String::from("hello");
for c in s.chars() {
    println!("{}", c);
}
}

  • Ranges (Range, RangeInclusive):

    #![allow(unused)]
fn main() {
for num in 1..5 {
    println!("{}", num);
}
}

Additional Iterable Types:

  • Option (Option<T>):

    #![allow(unused)]
fn main() {
let some_value = Some(42);
for val in some_value.iter() {
    println!("{}", val);
}
}

Understanding these iterable types allows you to leverage iterator methods effectively across different data structures.

13.1.6 Iterators and Closures

Iterator adapters like map() and filter(), as well as consuming methods like for_each(), rely heavily on closures to define operations on elements.

Transformation with map():

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3];
let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect();
}

Filtering with filter():

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3, 4, 5];
let even_numbers: Vec<i32> = numbers.iter().filter(|&x| x % 2 == 0).cloned().collect();
}
  • Note: cloned() converts references to owned values before collecting.

Side Effects with for_each():

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3];
numbers.iter().for_each(|x| println!("{}", x));
}

Laziness of Adapters:

  • Lazy Adapters: Methods like map() and filter() are lazy and don't execute until a consuming method is called.
  • Eager Methods: Methods like for_each() are consuming and execute immediately.

13.1.7 Basic Iterator Usage

Iterators are commonly processed in for loops or by consuming iterator methods.

Using an Iterator in a for Loop:

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    for number in numbers.iter() {
        print!("{} ", number);
    }
    // Output: 1 2 3 4 5
}

Chaining Iterator Adapters:

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    let processed: Vec<i32> = numbers
        .iter()
        .map(|x| x * 2)
        .filter(|&x| x > 5)
        .collect();
    println!("{:?}", processed); // Output: [6, 8, 10]
}
  • Explanation:
    • map(|x| x * 2): Doubles each number.
    • filter(|&x| x > 5): Keeps numbers greater than 5.
    • collect(): Gathers results into a Vec<i32>.

Style Tips:

  • Chain adapters on separate lines for readability.
  • Use method chaining to build concise data pipelines.

13.1.8 Consuming Iterators

Consuming iterator methods process the elements and produce a final value. They exhaust the iterator by calling next() until it returns None.

Common Consuming Methods:

  • collect(): Gathers elements into a collection.
  • sum(): Computes the sum of elements.
  • for_each(): Executes a function on each element.
  • find(): Searches for an element satisfying a condition.
  • any(), all(): Check conditions across elements.
  • count(): Counts elements.
  • fold(): Reduces elements to a single value.

13.1.9 Iterator Adapters

Iterator adapters transform iterators into new iterators, allowing for complex data processing. They are lazy and perform no work on their own. The final iterator is typically used in a for loop or exhausted by a method call.

Common Iterator Adapters:

  • map(): Transforms each element.
  • filter(): Selects elements based on a predicate.
  • take(): Limits the number of elements.
  • skip(): Skips elements.
  • chain(): Combines two iterators.
  • enumerate(): Adds indices.
  • flat_map(): Flattens nested iterators.
  • scan(): Applies stateful transformations.

13.1.10 The collect() Method

The consuming method collect() transforms an iterator into a collection, such as a Vec, HashMap, or any type implementing FromIterator.

Basic Usage of collect():

fn main() {
    let numbers = vec![1, 2, 3];
    let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect();
    println!("{:?}", doubled); // Output: [2, 4, 6]
}
  • Type Annotation: Often required to specify the collection type.

Collecting into a HashSet:

use std::collections::HashSet;
fn main() {
    let numbers = vec![1, 2, 2, 3, 4, 4, 5];
    let unique: HashSet<_> = numbers.into_iter().collect();
    println!("{:?}", unique); // Output: {1, 2, 3, 4, 5}
}
  • Underscore _ in HashSet<_>: Allows Rust to infer the type.

13.1.11 Creating Arrays

Mapping values into an array requires knowing the length at compile time.

Using collect() with Arrays:

fn main() {
    let numbers = [1, 2, 3];
    let doubled: [i32; 3] = numbers
        .iter()
        .map(|&x| x * 2)
        .collect::<Vec<_>>()
        .try_into()
        .unwrap();
    println!("{:?}", doubled); // Output: [2, 4, 6]
}

Explanation:

  1. Collects into a Vec.
  2. Uses try_into() to convert the Vec into an array.
  3. Uses unwrap() assuming the lengths match.

Using map() on Arrays (Since Rust 1.55):

fn main() {
    let numbers = [1, 2, 3];
    let doubled = numbers.map(|x| x * 2);
    println!("{:?}", doubled); // Output: [2, 4, 6]
}
  • Advantage: Avoids intermediate allocations.

13.1.12 Allocation Considerations and Performance Implications

Understanding how iterators affect memory allocation is crucial for efficient Rust code.

Heap Allocation with collect():

  • Collecting into dynamic collections like Vec or HashMap involves heap allocation.
fn main() {
    let numbers = vec![1, 2, 3];
    let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect();
    // `doubled` is allocated on the heap
    println!("{:?}", doubled);
}
  • Note: The Vec struct is on the stack, but its elements are on the heap.

No Heap Allocation with Iterator Adapters:

  • Methods like map(), filter(), and for_each() don't inherently cause heap allocations.

Exceptions:

  • Creating trait objects (Box<dyn Iterator>) involves heap allocation.

Performance Implications:

  • Minimal Overhead: Iterators are designed for efficiency.
  • Compiler Optimizations: Rust often inlines iterator methods and eliminates intermediate structures.