890 Intermediate

890-exact-size — ExactSizeIterator

Functional Programming

Tutorial

The Problem

When processing data with a known count, reporting progress percentages, pre-allocating output buffers, or rendering progress bars, you need the total element count upfront. Standard Iterator does not guarantee this — .count() might consume the iterator. ExactSizeIterator adds a guaranteed-O(1) .len() method for iterators that know their exact size before iteration. Slice iterators, range iterators, and many standard adapters implement it. This enables accurate progress reporting, guaranteed single-allocation output with Vec::with_capacity, and chunk-boundary calculations without consuming the source.

🎯 Learning Outcomes

• Use .len() on ExactSizeIterator for O(1) size queries

• Pre-allocate output with Vec::with_capacity(iter.len()) to avoid reallocations

• Report progress using enumerate().map(|(i, x)| format!("[{}/{}]", i+1, total, x))

• Implement a custom ExactSizeIterator with correct size_hint and len

• Understand which standard adapters preserve vs destroy ExactSizeIterator

Code Example

// Slices, Vec::iter(), ranges, .map(), .enumerate(), .zip() all implement
// ExactSizeIterator — .len() is O(1) and guaranteed exact.
pub fn process_with_progress(data: &[i32]) -> Vec<String> {
    let total = data.len(); // O(1) — ExactSizeIterator guarantee
    data.iter()
        .enumerate()
        .map(|(i, &x)| format!("[{}/{}] Processing {}", i + 1, total, x))
        .collect()
}

// Pre-allocate exactly — zero reallocations because size is known upfront
pub fn map_preallocated<T, U>(data: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
    let mut result = Vec::with_capacity(data.len());
    for item in data { result.push(f(item)); }
    result
}

(* OCaml: List.length is always O(n) — no compile-time size guarantee *)
let process_with_progress lst =
  let total = List.length lst in   (* traverses the entire list *)
  List.mapi (fun i x ->
    Printf.sprintf "[%d/%d] Processing %d" (i + 1) total x
  ) lst

(* Arrays have O(1) length, but you can't query length mid-pipeline *)
let 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)

Key Differences

Formalized guarantee: Rust ExactSizeIterator is a formal trait with a compiler-checkable contract; OCaml has no equivalent interface — length must be tracked manually.

Adapter propagation: map, zip, enumerate preserve ExactSizeIterator when both inputs implement it; filter and flat_map do not.

Pre-allocation idiom: Rust Vec::with_capacity(iter.len()) is the canonical pattern; OCaml uses Array.make for known-size output.

size_hint: ExactSizeIterator strengthens Iterator::size_hint to return (len, Some(len)) — adapters use this for optimization hints.

OCaml Approach

OCaml arrays have O(1) Array.length. OCaml lists have O(n) List.length. For pre-allocation, OCaml's Array.make n default pre-allocates; Buffer.create hint_size pre-allocates for strings. Progress reporting requires storing the length before iteration begins: let total = Array.length arr in Array.iteri (fun i x -> Printf.printf "[%d/%d]" (i+1) total) arr. The ExactSizeIterator trait has no direct OCaml equivalent as a formal interface.

Full Source

#![allow(clippy::all)]
// Example 096: ExactSizeIterator
// When you know the length upfront — O(1) .len(), exact pre-allocation, progress tracking.

// === Approach 1: Idiomatic — using ExactSizeIterator::len() on slices ===

/// Process items while reporting progress using the exact known length.
/// `.iter()` on a slice implements ExactSizeIterator, so `.len()` is O(1).
pub fn process_with_progress(data: &[i32]) -> Vec<String> {
    let total = data.len(); // O(1) via ExactSizeIterator
    data.iter()
        .enumerate()
        .map(|(i, &x)| format!("[{}/{}] Processing {}", i + 1, total, x))
        .collect()
}

/// Render an ASCII progress bar given a completed count, total, and bar width.
pub fn progress_bar(completed: usize, total: usize, width: usize) -> String {
    if total == 0 {
        return format!("[{}] 0/0", ".".repeat(width));
    }
    let filled = completed * width / total;
    let empty = width - filled;
    format!(
        "[{}{}] {}/{}",
        "#".repeat(filled),
        ".".repeat(empty),
        completed,
        total
    )
}

// === Approach 2: Pre-allocate with exact capacity from ExactSizeIterator ===

/// Map a function over a slice, pre-allocating the output Vec exactly.
/// Because `data.len()` is O(1), `Vec::with_capacity` avoids all reallocations.
pub fn map_preallocated<T, U>(data: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
    let mut result = Vec::with_capacity(data.len());
    for item in data {
        result.push(f(item));
    }
    result
}

/// Split a slice into chunks of exactly `n` elements, discarding any remainder.
/// Returns a Vec of owned Vec chunks.
pub fn chunks_exact(data: &[i32], n: usize) -> Vec<Vec<i32>> {
    if n == 0 {
        return vec![];
    }
    data.chunks_exact(n).map(|c| c.to_vec()).collect()
}

// === Approach 3: Custom ExactSizeIterator ===

/// A counter iterator that counts down from `remaining` to 0.
/// Implements ExactSizeIterator so callers can query `.len()` in O(1).
pub struct Countdown {
    remaining: usize,
}

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

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)
        }
    }

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

// Implementing ExactSizeIterator requires size_hint to be exact.
impl ExactSizeIterator for Countdown {}

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

    #[test]
    fn test_process_with_progress_empty() {
        let result = process_with_progress(&[]);
        assert_eq!(result, Vec::<String>::new());
    }

    #[test]
    fn test_process_with_progress_single() {
        let result = process_with_progress(&[42]);
        assert_eq!(result, vec!["[1/1] Processing 42"]);
    }

    #[test]
    fn test_process_with_progress_multiple() {
        let result = process_with_progress(&[10, 20, 30]);
        assert_eq!(
            result,
            vec![
                "[1/3] Processing 10",
                "[2/3] Processing 20",
                "[3/3] Processing 30",
            ]
        );
    }

    #[test]
    fn test_progress_bar_empty_total() {
        let bar = progress_bar(0, 0, 10);
        assert_eq!(bar, "[..........] 0/0");
    }

    #[test]
    fn test_progress_bar_half() {
        let bar = progress_bar(5, 10, 10);
        assert_eq!(bar, "[#####.....] 5/10");
    }

    #[test]
    fn test_progress_bar_full() {
        let bar = progress_bar(10, 10, 10);
        assert_eq!(bar, "[##########] 10/10");
    }

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

    #[test]
    fn test_map_preallocated_empty() {
        let result = map_preallocated(&[] as &[i32], |&x| x + 1);
        assert_eq!(result, Vec::<i32>::new());
    }

    #[test]
    fn test_chunks_exact() {
        let data = vec![1, 2, 3, 4, 5, 6, 7];
        let chunks = chunks_exact(&data, 3);
        assert_eq!(chunks, vec![vec![1, 2, 3], vec![4, 5, 6]]);
        // 7 is the remainder — discarded by chunks_exact
    }

    #[test]
    fn test_chunks_exact_zero_n() {
        let chunks = chunks_exact(&[1, 2, 3], 0);
        assert_eq!(chunks, Vec::<Vec<i32>>::new());
    }

    #[test]
    fn test_countdown_len() {
        let mut cd = Countdown::new(5);
        assert_eq!(cd.len(), 5);
        cd.next();
        assert_eq!(cd.len(), 4);
        cd.next();
        cd.next();
        assert_eq!(cd.len(), 2);
    }

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

    #[test]
    fn test_countdown_empty() {
        let values: Vec<usize> = Countdown::new(0).collect();
        assert_eq!(values, Vec::<usize>::new());
    }

    #[test]
    fn test_exact_size_enables_preallocation() {
        // Demonstrate that ExactSizeIterator adapters preserve size information:
        // .map() on a slice iterator is also ExactSizeIterator
        let data = [1i32, 2, 3, 4, 5];
        let mapped = data.iter().map(|&x| x * 2);
        assert_eq!(mapped.len(), 5); // preserved through .map()

        // .enumerate() also preserves it
        let enumerated = data.iter().enumerate();
        assert_eq!(enumerated.len(), 5);
    }
}

(* 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"

✓ Tests Rust test suite

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

    #[test]
    fn test_process_with_progress_empty() {
        let result = process_with_progress(&[]);
        assert_eq!(result, Vec::<String>::new());
    }

    #[test]
    fn test_process_with_progress_single() {
        let result = process_with_progress(&[42]);
        assert_eq!(result, vec!["[1/1] Processing 42"]);
    }

    #[test]
    fn test_process_with_progress_multiple() {
        let result = process_with_progress(&[10, 20, 30]);
        assert_eq!(
            result,
            vec![
                "[1/3] Processing 10",
                "[2/3] Processing 20",
                "[3/3] Processing 30",
            ]
        );
    }

    #[test]
    fn test_progress_bar_empty_total() {
        let bar = progress_bar(0, 0, 10);
        assert_eq!(bar, "[..........] 0/0");
    }

    #[test]
    fn test_progress_bar_half() {
        let bar = progress_bar(5, 10, 10);
        assert_eq!(bar, "[#####.....] 5/10");
    }

    #[test]
    fn test_progress_bar_full() {
        let bar = progress_bar(10, 10, 10);
        assert_eq!(bar, "[##########] 10/10");
    }

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

    #[test]
    fn test_map_preallocated_empty() {
        let result = map_preallocated(&[] as &[i32], |&x| x + 1);
        assert_eq!(result, Vec::<i32>::new());
    }

    #[test]
    fn test_chunks_exact() {
        let data = vec![1, 2, 3, 4, 5, 6, 7];
        let chunks = chunks_exact(&data, 3);
        assert_eq!(chunks, vec![vec![1, 2, 3], vec![4, 5, 6]]);
        // 7 is the remainder — discarded by chunks_exact
    }

    #[test]
    fn test_chunks_exact_zero_n() {
        let chunks = chunks_exact(&[1, 2, 3], 0);
        assert_eq!(chunks, Vec::<Vec<i32>>::new());
    }

    #[test]
    fn test_countdown_len() {
        let mut cd = Countdown::new(5);
        assert_eq!(cd.len(), 5);
        cd.next();
        assert_eq!(cd.len(), 4);
        cd.next();
        cd.next();
        assert_eq!(cd.len(), 2);
    }

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

    #[test]
    fn test_countdown_empty() {
        let values: Vec<usize> = Countdown::new(0).collect();
        assert_eq!(values, Vec::<usize>::new());
    }

    #[test]
    fn test_exact_size_enables_preallocation() {
        // Demonstrate that ExactSizeIterator adapters preserve size information:
        // .map() on a slice iterator is also ExactSizeIterator
        let data = [1i32, 2, 3, 4, 5];
        let mapped = data.iter().map(|&x| x * 2);
        assert_eq!(mapped.len(), 5); // preserved through .map()

        // .enumerate() also preserves it
        let enumerated = data.iter().enumerate();
        assert_eq!(enumerated.len(), 5);
    }
}

Deep Comparison

OCaml vs Rust: ExactSizeIterator

Side-by-Side Code

OCaml

(* OCaml: List.length is always O(n) — no compile-time size guarantee *)
let process_with_progress lst =
  let total = List.length lst in   (* traverses the entire list *)
  List.mapi (fun i x ->
    Printf.sprintf "[%d/%d] Processing %d" (i + 1) total x
  ) lst

(* Arrays have O(1) length, but you can't query length mid-pipeline *)
let 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)

Rust (idiomatic — ExactSizeIterator)

// Slices, Vec::iter(), ranges, .map(), .enumerate(), .zip() all implement
// ExactSizeIterator — .len() is O(1) and guaranteed exact.
pub fn process_with_progress(data: &[i32]) -> Vec<String> {
    let total = data.len(); // O(1) — ExactSizeIterator guarantee
    data.iter()
        .enumerate()
        .map(|(i, &x)| format!("[{}/{}] Processing {}", i + 1, total, x))
        .collect()
}

// Pre-allocate exactly — zero reallocations because size is known upfront
pub fn map_preallocated<T, U>(data: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
    let mut result = Vec::with_capacity(data.len());
    for item in data { result.push(f(item)); }
    result
}

Rust (functional/recursive — custom ExactSizeIterator)

pub struct Countdown { remaining: usize }

impl Iterator for Countdown {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        if self.remaining == 0 { return None; }
        self.remaining -= 1;
        Some(self.remaining)
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

// Opt into ExactSizeIterator — the compiler verifies size_hint is exact
impl ExactSizeIterator for Countdown {}

Type Signatures

Concept	OCaml	Rust
List length	`List.length : 'a list -> int` (O(n))	`<[T]>::len(&self) -> usize` (O(1))
Exact size trait	none — no trait for this	`ExactSizeIterator`
Size hint	n/a (lists are linked)	`Iterator::size_hint() -> (usize, Option<usize>)`
Array length	`Array.length arr` (O(1))	`data.len()` via `ExactSizeIterator`
Chunks without remainder	`Array.sub` + manual math	`slice::chunks_exact(n)`

Key Insights

O(n) vs O(1) length: OCaml linked lists must traverse the entire structure to count elements. Rust slices, Vec, and ranges store their length, making .len() O(1) and safe to call in hot loops.

Compile-time size contract: ExactSizeIterator is a trait — implementing it is an explicit promise that size_hint() returns exact bounds. The compiler enforces the contract at every call site; breaking it is unsafe territory.

Adapter propagation: Standard adapters like .map(), .enumerate(), .zip(), and .take(n) automatically implement ExactSizeIterator when both inputs do. Adapters like .filter() cannot, because they conditionally drop elements — the size is unknown until the predicate runs.

Pre-allocation without guessing: Vec::with_capacity(iter.len()) allocates exactly once when the iterator is ExactSizeIterator. Without it, collect() falls back to size_hint() lower bound and may reallocate several times.

Progress bars and batch processing: Knowing the exact remaining count enables correct progress fractions (completed / total) without consuming the iterator. OCaml achieves this only with arrays or by pre-computing List.length (an O(n) pass) before iteration begins.

When to Use Each Style

**Use ExactSizeIterator::len()** when building progress UIs, pre-allocating output buffers, or splitting work into batches — any time knowing "how many remain" is cheaper than a full traversal.

**Use size_hint() only** when working with adapters like .filter() that can't guarantee exact counts; treat it as an optimization hint, not a hard contract.

**Implement ExactSizeIterator on custom types** whenever your iterator wraps a fixed-size collection or counter — it's a zero-cost trait that unlocks better downstream ergonomics and avoids unnecessary reallocations for callers.

Exercises

Implement a custom ExactSizeIterator for a Grid<T> that iterates over all cells, reporting the exact cell count.

Write progress_map<T, U, F>(data: &[T], f: F, report: impl Fn(usize, usize)) that calls report(current, total) for each element.

Implement batch_process<T: Clone>(data: &[T], batch_size: usize) -> Vec<Vec<T>> using chunks_exact and pre-allocating exactly data.len() / batch_size batches.

Open Source Repos

functional-rust

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

Rust