283 Intermediate

283: ExactSizeIterator for Known-Length Iterators

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "283: ExactSizeIterator for Known-Length Iterators" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Pre-allocating the right amount of memory before collecting an iterator avoids repeated resizing. Key difference from OCaml: 1. **Trait

Tutorial

The Problem

Pre-allocating the right amount of memory before collecting an iterator avoids repeated resizing. Displaying progress bars requires knowing total count upfront. Splitting an iterator into equally-sized chunks requires knowing its length. The ExactSizeIterator trait signals that an iterator knows its exact remaining length in O(1) time, enabling these optimizations without counting all elements first.

🎯 Learning Outcomes

• Understand ExactSizeIterator as providing O(1) len() for iterators with known size

• Implement ExactSizeIterator on a custom iterator struct with a computable length

• Use len() for pre-allocation and progress display without consuming the iterator

• Recognize which standard iterators implement ExactSizeIterator: slice iterators, ranges, Vec drains, but not filtered or chained iterators

Code Example

let arr = [1i32, 2, 3, 4, 5];
let mut iter = arr.iter();
println!("Length: {}", iter.len()); // 5
iter.next();
println!("Remaining: {}", iter.len()); // 4 - tracks consumed

let arr = [|1; 2; 3; 4; 5|] in
Printf.printf "Length: %d\n" (Array.length arr)
(* Arrays always know their length *)

Key Differences

Trait-based annotation: Rust uses a marker trait to communicate "I know my size"; OCaml has no equivalent standard mechanism.

Pre-allocation optimization: collect::<Vec<_>>() uses ExactSizeIterator to pre-allocate the exact vector capacity; OCaml's Array.of_seq must grow or traverse twice.

Composition loss: Applying filter() or flat_map() to an ExactSizeIterator loses the ExactSizeIterator implementation — only size-preserving adapters like map() retain it.

Progress bars: Libraries like indicatif use ExactSizeIterator::len() to display accurate progress without pre-consuming the iterator.

OCaml Approach

OCaml's Seq module is inherently forward-only without size information. Length is known only for Array and List (via Array.length and List.length). Sequences built from generators have no known length unless explicitly tracked alongside:

(* OCaml has no ExactSizeIterator equivalent — length must be tracked separately *)
let (length, seq) = (10, Seq.init 10 Fun.id)

Full Source

#![allow(clippy::all)]
//! # ExactSizeIterator for Known-Length Iterators
//!
//! `ExactSizeIterator` provides O(1) `len()`, enabling pre-allocation and size checks.

/// A range iterator that knows its exact size
pub struct FixedRange {
    current: usize,
    end: usize,
}

impl FixedRange {
    pub fn new(start: usize, end: usize) -> Self {
        FixedRange {
            current: start,
            end,
        }
    }
}

impl Iterator for FixedRange {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        if self.current >= self.end {
            return None;
        }
        let v = self.current;
        self.current += 1;
        Some(v)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.end.saturating_sub(self.current);
        (remaining, Some(remaining))
    }
}

impl ExactSizeIterator for FixedRange {
    fn len(&self) -> usize {
        self.end.saturating_sub(self.current)
    }
}

/// Pre-allocate and transform using ExactSizeIterator
pub fn double_elements<I>(iter: I) -> Vec<i32>
where
    I: ExactSizeIterator<Item = i32>,
{
    let mut result = Vec::with_capacity(iter.len());
    result.extend(iter.map(|x| x * 2));
    result
}

/// Alternative: using collect (also uses size_hint internally)
pub fn square_elements(slice: &[i32]) -> Vec<i32> {
    slice.iter().map(|&x| x * x).collect()
}

/// Efficient single-allocation append
pub fn append_transformed<I, F>(vec: &mut Vec<i32>, iter: I, f: F)
where
    I: ExactSizeIterator<Item = i32>,
    F: Fn(i32) -> i32,
{
    vec.reserve(iter.len());
    for x in iter {
        vec.push(f(x));
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slice_exact_size() {
        let arr = [1i32, 2, 3, 4, 5];
        assert_eq!(arr.iter().len(), 5);
    }

    #[test]
    fn test_exact_size_after_next() {
        let arr = [1i32, 2, 3];
        let mut it = arr.iter();
        it.next();
        assert_eq!(it.len(), 2);
    }

    #[test]
    fn test_custom_fixed_range_len() {
        let fr = FixedRange::new(0, 5);
        assert_eq!(fr.len(), 5);
    }

    #[test]
    fn test_custom_fixed_range_collect() {
        let result: Vec<usize> = FixedRange::new(2, 5).collect();
        assert_eq!(result, vec![2, 3, 4]);
    }

    #[test]
    fn test_fixed_range_size_hint() {
        let fr = FixedRange::new(10, 20);
        assert_eq!(fr.size_hint(), (10, Some(10)));
    }

    #[test]
    fn test_double_elements_preallocated() {
        let arr = [1i32, 2, 3, 4, 5];
        let result = double_elements(arr.iter().copied());
        assert_eq!(result, vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_square_elements() {
        let arr = [1, 2, 3, 4];
        let result = square_elements(&arr);
        assert_eq!(result, vec![1, 4, 9, 16]);
    }

    #[test]
    fn test_append_transformed() {
        let mut vec = vec![1, 2];
        let arr = [3i32, 4, 5];
        append_transformed(&mut vec, arr.iter().copied(), |x| x * 10);
        assert_eq!(vec, vec![1, 2, 30, 40, 50]);
    }
}

(* 283. ExactSizeIterator for known-length - OCaml *)
(* OCaml arrays always know their length *)

let () =
  let arr = [|1; 2; 3; 4; 5|] in
  Printf.printf "Length: %d\n" (Array.length arr);

  (* Pre-allocate based on known length *)
  let src = Array.init 100 (fun i -> i * i) in
  let target = Array.make (Array.length src) 0 in
  Array.blit src 0 target 0 (Array.length src);
  Printf.printf "Copied %d elements\n" (Array.length target);

  (* Size hint for lists *)
  let lst = List.init 5 (fun i -> i + 1) in
  Printf.printf "List length: %d\n" (List.length lst);

  (* Simulate size_hint *)
  Printf.printf "Expected items: 5\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slice_exact_size() {
        let arr = [1i32, 2, 3, 4, 5];
        assert_eq!(arr.iter().len(), 5);
    }

    #[test]
    fn test_exact_size_after_next() {
        let arr = [1i32, 2, 3];
        let mut it = arr.iter();
        it.next();
        assert_eq!(it.len(), 2);
    }

    #[test]
    fn test_custom_fixed_range_len() {
        let fr = FixedRange::new(0, 5);
        assert_eq!(fr.len(), 5);
    }

    #[test]
    fn test_custom_fixed_range_collect() {
        let result: Vec<usize> = FixedRange::new(2, 5).collect();
        assert_eq!(result, vec![2, 3, 4]);
    }

    #[test]
    fn test_fixed_range_size_hint() {
        let fr = FixedRange::new(10, 20);
        assert_eq!(fr.size_hint(), (10, Some(10)));
    }

    #[test]
    fn test_double_elements_preallocated() {
        let arr = [1i32, 2, 3, 4, 5];
        let result = double_elements(arr.iter().copied());
        assert_eq!(result, vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_square_elements() {
        let arr = [1, 2, 3, 4];
        let result = square_elements(&arr);
        assert_eq!(result, vec![1, 4, 9, 16]);
    }

    #[test]
    fn test_append_transformed() {
        let mut vec = vec![1, 2];
        let arr = [3i32, 4, 5];
        append_transformed(&mut vec, arr.iter().copied(), |x| x * 10);
        assert_eq!(vec, vec![1, 2, 30, 40, 50]);
    }
}

Deep Comparison

OCaml vs Rust: ExactSizeIterator

Pattern 1: Known-Length Collection

OCaml

let arr = [|1; 2; 3; 4; 5|] in
Printf.printf "Length: %d\n" (Array.length arr)
(* Arrays always know their length *)

Rust

let arr = [1i32, 2, 3, 4, 5];
let mut iter = arr.iter();
println!("Length: {}", iter.len()); // 5
iter.next();
println!("Remaining: {}", iter.len()); // 4 - tracks consumed

Pattern 2: Pre-allocation

OCaml

let src = Array.init 100 (fun i -> i * i) in
let target = Array.make (Array.length src) 0 in
Array.blit src 0 target 0 (Array.length src)

Rust

let source = vec![1i32, 2, 3, 4, 5];
let mut dest = Vec::with_capacity(source.iter().len());
dest.extend(source.iter().map(|&x| x * 2));
// Single allocation - no reallocs

Pattern 3: Custom ExactSizeIterator

Rust

struct FixedRange { current: usize, end: usize }

impl Iterator for FixedRange {
    type Item = usize;
    
    fn next(&mut self) -> Option<usize> { /* ... */ }
    
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.end.saturating_sub(self.current);
        (remaining, Some(remaining))  // exact bounds
    }
}

impl ExactSizeIterator for FixedRange {
    fn len(&self) -> usize {
        self.end.saturating_sub(self.current)
    }
}

Key Differences

Aspect	OCaml	Rust
Length access	`Array.length` (O(1))	`.len()` on `ExactSizeIterator`
List length	`List.length` (O(n))	N/A (iterators can be O(1))
Iterator size	Not tracked	`size_hint()` + `len()`
Pre-allocation	Manual size tracking	`Vec::with_capacity(iter.len())`
Dynamic tracking	No	`len()` decreases as items consumed

Exercises

Implement ExactSizeIterator for a custom StridedRange that yields every nth element from a range, where the exact count is computable as (end - start + step - 1) / step.

Write a function that takes an ExactSizeIterator and a progress-display closure, calling the closure with (index, total) for each element.

Show that filter() applied to an ExactSizeIterator loses the ExactSizeIterator implementation by checking the trait bounds in the type signature.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust