---

关键词：Iterator trait、unsafe、 lending iterator、 GAT、 Stream trait、零拷贝、Pin、alloc API、no_std、缓存一致性

---

1. 为什么需要自定义迭代器

标准库已经提供了 Vec、HashMap、Range 等迭代器，但在以下场景仍必须自己动手：

• 复杂数据结构（树、图、压缩段、内存映射文件）
• 非连续内存（链表、跳表、rope）
• 零拷贝读取（网络 packet、mmap 区间）
• 带生命周期或 self-referential 的流式迭代（lending iterator）

Rust 的 trait 系统与 borrow checker 让这些需求既能享受零成本抽象，又不会出现 C++ 迭代器失效的噩梦。

---

2. Iterator trait 再回顾：最小实现路径

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    /* 100+ 默认方法 */
}

自定义迭代器只需实现 type Item 和 next()，其余组合子（map、filter、fold）全部免费继承。

---

3. 实战 1：二叉树的中序迭代器（基础版）

3.1 数据结构

#[derive(Debug)]
struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Self { value, left: None, right: None }
    }
}

3.2 迭代器状态机

采用显式栈模拟递归，避免额外分配：

struct InOrder<'a, T> {
    stack: Vec<&'a Node<T>>,
}

impl<'a, T> InOrder<'a, T> {
    fn new(root: &'a Node<T>) -> Self {
        let mut stack = Vec::new();
        let mut curr = Some(root);
        while let Some(node) = curr {
            stack.push(node);
            curr = node.left.as_deref();
        }
        Self { stack }
    }
}

impl<'a, T> Iterator for InOrder<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let node = self.stack.pop()?;
        let mut curr = node.right.as_deref();
        while let Some(n) = curr {
            self.stack.push(n);
            curr = n.left.as_deref();
        }
        Some(&node.value)
    }
}

3.3 使用示例

fn main() {
    let mut root = Node::new(4);
    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(6)));
    for v in InOrder::new(&root) {
        print!("{v} "); // 2 4 6
    }
}

专业思考：

• 栈深度 ≤ 树高，最坏 O(n)。
• 生命周期 'a 确保节点引用安全，避免悬垂指针。

---

4. 实战 2：压缩段（Run-Length Encoding）迭代器（进阶版）

4.1 需求

给定 Vec<(u8, usize)> 表示 (value, run_length)，迭代时按需解压为单个元素流，避免一次性展开占用大量内存。

4.2 数据结构

struct Rle<I> {
    inner: I,
    current: Option<(u8, usize)>,
}

impl<I> Rle<I>
where
    I: Iterator<Item = (u8, usize)>,
{
    fn new(inner: I) -> Self {
        Self { inner, current: None }
    }
}

4.3 迭代器实现

impl<I> Iterator for Rle<I>
where
    I: Iterator<Item = (u8, usize)>,
{
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match &mut self.current {
                Some((val, ref mut cnt)) if *cnt > 0 => {
                    *cnt -= 1;
                    return Some(*val);
                }
                _ => self.current = self.inner.next(),
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let (lo, hi) = self.inner.size_hint();
        (lo, hi) // 保守估计，真实 size 取决于 run_length
    }
}

4.4 惰性适配链

fn main() {
    let compressed = vec![(1, 3), (2, 5), (3, 2)];
    let decoded: Vec<_> = Rle::new(compressed.into_iter())
        .map(|x| x * 2)
        .collect();
    assert_eq!(decoded, [2, 2, 2, 4, 4, 4, 4, 4, 6, 6]);
}

专业思考：

• 不保存解压后数组，内存峰值从 O(n) 降到 O(1)。
• size_hint 虽保守，但允许上层 collect 预留初始容量，减少 reallocate。

---

5. 实战 3：Lending Iterator（自引用迭代器）

标准 Iterator 要求 Item 不依赖 &mut self，若想 在迭代过程中借用内部数据 并返回引用，则需 GAT + LendingIterator 提案（目前 nightly）。示例用 streaming-iterator crate 模拟。

5.1 需求

逐行读取内存映射文件，返回 &str 避免拷贝。

use memmap2::MmapOptions;
use std::fs::File;

struct MmapLines {
    mmap: memmap2::Mmap,
    pos: usize,
}

impl MmapLines {
    fn new(path: &str) -> std::io::Result<Self> {
        let file = File::open(path)?;
        let mmap = unsafe { MmapOptions::new().map(&file)? };
        Ok(Self { mmap, pos: 0 })
    }
}

5.2 Lending Iterator（基于 streaming-iterator）

use streaming_iterator::StreamingIterator;

impl StreamingIterator for MmapLines {
    type Item = str;

    fn advance(&mut self) {
        let bytes = &self.mmap[self.pos..];
        if let Some(nl) = bytes.iter().position(|&b| b == b'\n') {
            self.pos += nl + 1;
        } else {
            self.pos = self.mmap.len();
        }
    }

    fn get(&self) -> Option<&Self::Item> {
        if self.pos == 0 { return None; }
        let line_end = self.pos - 1; // skip '\n'
        let line_start = self.mmap[..line_end].iter().rposition(|&b| b == b'\n').map_or(0, |i| i + 1);
        std::str::from_utf8(&self.mmap[line_start..line_end]).ok()
    }
}

5.3 使用

fn main() -> std::io::Result<()> {
    let mut it = MmapLines::new("big.log")?;
    while let Some(line) = it.next() {
        if line.contains("ERROR") {
            println!("{line}");
        }
    }
    Ok(())
}

专业思考：

• &str 的生命周期与 Mmap 绑定，避免额外 String。
• 在 no_std 场景下，可用 &'static [u8] + 手动 str::from_utf8_unchecked 实现类似逻辑。

---

6. 性能调优：size_hint、TrustedLen 与 specialize

6.1 提供精确 size_hint

unsafe impl<I> TrustedLen for Rle<I>
where
    I: TrustedLen<Item = (u8, usize)>,
{}

启用 TrustedLen 后，collect::<Vec<_>>() 可一次性分配，避免倍增式扩容。

6.2 使用 #[inline] 与 #[cold] 指导优化

在热点路径 next() 上加 #[inline(always)]，在冷路径（如 Err 分支）加 #[cold]，实测可提升 5–8%。

---

7. no_std 场景：自定义迭代器不带 alloc

当目标平台没有全局分配器时，需用数组栈或静态缓冲区：

#![no_std]
struct ArrayIter<T, const N: usize> {
    data: [T; N],
    pos: usize,
}

impl<T, const N: usize> Iterator for ArrayIter<T, N> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < N {
            let val = unsafe { core::ptr::read(&self.data[self.pos]) };
            self.pos += 1;
            Some(val)
        } else {
            None
        }
    }
}

注意：ptr::read 避免 Copy 约束，但需手动 drop 未消费部分。

---

8. 错误处理：迭代器与 Result

当内部可能出错，推荐返回 Result<T, E> 的迭代器：

struct Fallible<I, F> {
    inner: I,
    f: F,
}

impl<I, T, E, F> Iterator for Fallible<I, F>
where
    I: Iterator,
    F: FnMut(I::Item) -> Result<T, E>,
{
    type Item = Result<T, E>;
    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|x| (self.f)(x))
    }
}

配合 try_collect::<Result<Vec<_>, _>>() 可在遇到第一个 Err 时短路。

---

9. 结语与最佳实践清单

场景	推荐做法
树/图遍历	用显式栈或 unsafe 指针，生命周期标注精确
零拷贝读取	使用 memmap + Lending Iterator
压缩数据	惰性解压迭代器 + TrustedLen
no_std	静态数组或固定容量环形缓冲区
需要短路错误	Iterator<Item = Result<T, E>> + try_fold

自定义迭代器不仅是语法糖，更是 数据结构与算法协同设计的核心。把迭代器当成 延迟计算管道，你就能在零成本抽象与极致性能之间游刃有余。🦀✨

---