096: ExactSizeIterator

Difficulty: 3 Level: Intermediate Iterators that know their remaining length — enabling O(1) `.len()`, perfect pre-allocation, and progress tracking.

The Problem This Solves

When building a `Vec` from an iterator, Rust needs to know how much memory to allocate. If the iterator can report its exact size upfront, a single allocation suffices. If it can't, the runtime resizes the buffer repeatedly — wasting allocations. Progress bars, batch processors, and capacity-constrained buffers all benefit from knowing "how many are left" without consuming the iterator. `ExactSizeIterator` is the trait that exposes this: `.len()` returns the exact remaining count in O(1). Without it, your only option is `size_hint()` — which gives a fuzzy lower/upper bound, not a guarantee.

The Intuition

Most concrete iterators you use daily implement `ExactSizeIterator`: slices, ranges, `Vec::iter()`, the output of `.map()`, `.zip()`, `.enumerate()`. The catch: some adapters lose exact size information. `.filter()` can't know how many elements will pass. `.chain()` loses it if either side doesn't have it. `.take(n)` keeps it (min of n and remaining). Knowing which adapters preserve it helps you design pipelines that stay allocation-friendly. OCaml doesn't have this concept — `List.length` is O(n), arrays have O(1) length but you can't query it mid-pipeline.

How It Works in Rust

// .len() on ExactSizeIterator — O(1), doesn't consume
fn show_progress(data: &[i32]) {
 let iter = data.iter();
 println!("About to process {} items", iter.len()); // works because slice iter is ExactSize
}

// Pre-allocate exactly: Vec::with_capacity from .len()
fn map_preallocated<T, U>(data: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
 let mut result = Vec::with_capacity(data.len()); // no reallocations
 for item in data { result.push(f(item)); }
 result
}

// map() preserves ExactSize — safe to call .len() on mapped iterator
fn demonstrate() {
 let data = vec![1, 2, 3, 4, 5];
 let mapped = data.iter().map(|x| x * 2);
 println!("{}", mapped.len()); // ✓ works

 // filter() does NOT implement ExactSizeIterator — unknown how many pass
 // let filtered = data.iter().filter(|&&x| x > 2);
 // filtered.len(); // ✗ compile error
}

// Custom iterator: implement ExactSizeIterator manually
struct Counter { current: usize, end: usize }

impl Iterator for Counter {
 type Item = usize;
 fn next(&mut self) -> Option<usize> {
     if self.current < self.end { let v = self.current; self.current += 1; Some(v) }
     else { None }
 }
 fn size_hint(&self) -> (usize, Option<usize>) {
     let remaining = self.end - self.current;
     (remaining, Some(remaining)) // exact lower and upper bound
 }
}
// ExactSizeIterator has no required methods — size_hint must be exact
impl ExactSizeIterator for Counter {}

What This Unlocks

Zero-realloc pipelines: `Vec::with_capacity(iter.len())` allocates once, no growth.
Progress tracking: display `n/total` without a separate counter variable.
Split and stride: split a known-size iterator into equal halves with `.len() / 2`.

Key Differences

Concept	OCaml	Rust
O(1) length	`Array.length` (not mid-pipeline)	`.len()` on `ExactSizeIterator`
Pre-allocation	`Array.make n`	`Vec::with_capacity(iter.len())`
map preserves	N/A	Yes
filter preserves	N/A	No
Custom impl	N/A	`impl ExactSizeIterator` (no methods required)

// Example 096: ExactSizeIterator
// When you know the length upfront

// === Approach 1: Using len() on ExactSizeIterator ===
fn process_with_progress(data: &[i32]) -> Vec<String> {
    let total = data.len();
    data.iter().enumerate().map(|(i, &x)| {
        format!("[{}/{}] Processing {}", i + 1, total, x)
    }).collect()
}

fn progress_bar(completed: usize, total: usize, width: usize) -> String {
    let filled = completed * width / total;
    let empty = width - filled;
    format!("[{}{}] {}/{}",
        "#".repeat(filled), ".".repeat(empty), completed, total)
}

// === Approach 2: Pre-allocation with known size ===
fn map_preallocated<T, U>(data: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
    let mut result = Vec::with_capacity(data.len()); // exact pre-allocation
    for item in data {
        result.push(f(item));
    }
    result
}

// ExactSizeIterator enables size_hint optimization
fn demonstrate_size_hint() {
    let data = vec![1, 2, 3, 4, 5];
    let iter = data.iter();

    // ExactSizeIterator provides .len()
    println!("Remaining: {}", iter.len());

    let mapped = data.iter().map(|x| x * 2);
    println!("Mapped remaining: {}", mapped.len()); // map preserves ExactSize

    let filtered = data.iter().filter(|&&x| x > 2);
    // filtered does NOT implement ExactSizeIterator (unknown how many pass)
    let (lower, upper) = filtered.size_hint();
    println!("Filter hint: ({}, {:?})", lower, upper);
}

// === Approach 3: Splitting with known size ===
fn split_evenly<T: Clone>(data: &[T]) -> (Vec<T>, Vec<T>) {
    let mid = data.len() / 2;
    (data[..mid].to_vec(), data[mid..].to_vec())
}

// Custom ExactSizeIterator
struct Countdown {
    remaining: usize,
}

impl Countdown {
    fn new(from: usize) -> Self {
        Countdown { remaining: from }
    }
}

impl Iterator for Countdown {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        if self.remaining == 0 {
            None
        } else {
            self.remaining -= 1;
            Some(self.remaining + 1)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl ExactSizeIterator for Countdown {}

// Generic function requiring ExactSizeIterator
fn with_percentage<I: ExactSizeIterator>(iter: I) -> Vec<(I::Item, f64)> {
    let total = iter.len();
    iter.enumerate().map(|(i, item)| {
        let pct = (i + 1) as f64 / total as f64 * 100.0;
        (item, pct)
    }).collect()
}

fn main() {
    let progress = process_with_progress(&[10, 20, 30]);
    for p in &progress { println!("{}", p); }

    println!("{}", progress_bar(3, 10, 20));

    demonstrate_size_hint();

    let (a, b) = split_evenly(&[1,2,3,4,5,6]);
    println!("Split: {:?} {:?}", a, b);

    let countdown: Vec<_> = Countdown::new(5).collect();
    println!("Countdown: {:?}", countdown);

    let with_pct = with_percentage(Countdown::new(4));
    for (val, pct) in &with_pct {
        println!("{}: {:.0}%", val, pct);
    }
}

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

    #[test]
    fn test_progress() {
        let p = process_with_progress(&[10, 20, 30]);
        assert_eq!(p[0], "[1/3] Processing 10");
        assert_eq!(p.len(), 3);
    }

    #[test]
    fn test_progress_bar() {
        assert_eq!(progress_bar(3, 10, 20), "[######..............] 3/10");
        assert_eq!(progress_bar(10, 10, 10), "[##########] 10/10");
    }

    #[test]
    fn test_preallocated() {
        let result = map_preallocated(&[1,2,3], |x| x * 2);
        assert_eq!(result, vec![2, 4, 6]);
    }

    #[test]
    fn test_split_evenly() {
        let (a, b) = split_evenly(&[1,2,3,4,5,6]);
        assert_eq!(a, vec![1,2,3]);
        assert_eq!(b, vec![4,5,6]);
    }

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

    #[test]
    fn test_countdown_len() {
        let c = Countdown::new(10);
        assert_eq!(c.len(), 10);
    }

    #[test]
    fn test_countdown_exact_size() {
        let c = Countdown::new(5);
        assert_eq!(c.size_hint(), (5, Some(5)));
    }

    #[test]
    fn test_with_percentage() {
        let result = with_percentage(Countdown::new(4));
        assert_eq!(result.len(), 4);
        assert!((result[0].1 - 25.0).abs() < 1e-10);
        assert!((result[3].1 - 100.0).abs() < 1e-10);
    }
}

(* Example 096: ExactSizeIterator *)
(* When you know the length upfront *)

(* Approach 1: List.length — always available *)
let process_with_progress lst =
  let total = List.length lst in
  List.mapi (fun i x ->
    Printf.sprintf "[%d/%d] Processing %d" (i + 1) total x
  ) lst

(* Approach 2: Array-based known-size operations *)
let array_chunks_exact n arr =
  let len = Array.length arr in
  let num_chunks = len / n in
  Array.init num_chunks (fun i ->
    Array.sub arr (i * n) n
  )

let progress_bar completed total width =
  let filled = completed * width / total in
  let empty = width - filled in
  Printf.sprintf "[%s%s] %d/%d"
    (String.make filled '#') (String.make empty '.') completed total

(* Approach 3: Pre-allocate based on known size *)
let map_preallocated f lst =
  let len = List.length lst in
  let arr = Array.make len (f (List.hd lst)) in
  List.iteri (fun i x -> arr.(i) <- f x) lst;
  Array.to_list arr

let parallel_process lst =
  let n = List.length lst in
  let mid = n / 2 in
  let first_half = List.filteri (fun i _ -> i < mid) lst in
  let second_half = List.filteri (fun i _ -> i >= mid) lst in
  (first_half, second_half)

(* Tests *)
let () =
  let progress = process_with_progress [10; 20; 30] in
  assert (List.hd progress = "[1/3] Processing 10");
  assert (List.length progress = 3);

  let chunks = array_chunks_exact 2 [|1;2;3;4;5;6|] in
  assert (Array.length chunks = 3);
  assert (chunks.(0) = [|1;2|]);

  assert (progress_bar 3 10 20 = "[######..............] 3/10");

  let mapped = map_preallocated (fun x -> x * 2) [1;2;3] in
  assert (mapped = [2;4;6]);

  let (a, b) = parallel_process [1;2;3;4;5;6] in
  assert (a = [1;2;3]);
  assert (b = [4;5;6]);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: ExactSizeIterator

Progress with Known Size

OCaml:

🐪 Show OCaml equivalent

let process_with_progress lst =
let total = List.length lst in
List.mapi (fun i x ->
 Printf.sprintf "[%d/%d] Processing %d" (i + 1) total x
) lst

Rust:

fn process_with_progress(data: &[i32]) -> Vec<String> {
 let total = data.len();
 data.iter().enumerate().map(|(i, &x)| {
     format!("[{}/{}] Processing {}", i + 1, total, x)
 }).collect()
}

Pre-allocation