深入 Rust 迭代器动机:从 C 风格 for 循环到零开销抽象的迭代模型 深入 Rust 迭代器动机从 C 风格 for 循环到零开销抽象的迭代模型【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust导读本文以 Google Android 团队 Rust 课程comprehensive-rust中 迭代器动机 一节为骨架系统讲解 Rust 迭代器Iterator的设计动机为什么 Rust 要把遍历一个数组所需的状态、终止条件、状态更新逻辑、元素取值逻辑统一打包成一个对象。读者读完本文将掌握手动遍历的四个必要要素、C 风格 for 循环与 Rust 迭代器模型的对应关系、Iterator/IntoIteratortrait 的底层实现原理以及迭代器适配器方法链与collect的实战组合用法。一、遍历一个数组需要什么四个必要条件任何对集合的遍历无论语言和写法如何本质上都逃不开以下四件事状态State记录当前迭代进行到哪一步例如一个下标index终止条件Condition判断迭代何时结束状态更新Update每一轮循环结束时如何推进状态例如i 1取值逻辑Fetch利用当前状态取出本轮要处理的元素。以 C 风格的for循环为例这四个要素被分散写在循环结构的三个位置里for (int i 0; i array_len; i 1) { int elem array[i]; }其中int i 0是状态初始化i array_len是终止条件i 1是状态更新array[i]是取值逻辑。这种写法直观但存在一个结构性问题遍历逻辑与业务处理逻辑耦合在同一个循环体里且遍历细节下标管理、边界判断散落在各处难以复用和组合。而在 Rust 中我们把这四样东西捆绑bundle成一个对象这个对象就是迭代器iterator。这正是 src/iterators/motivation.md 一节的核心理念先用读者熟悉的 C 风格for循环建立遍历需要状态加逻辑的直觉再引出迭代器就是把这些打包起来的抽象。1.1 没有 C 风格 for 循环的 Rust用 while 表达同一件事Rust 语言本身没有C 风格的for (int i 0; ...)循环语法。但同一套逻辑可以直接用while循环原样表达出来这恰好可以直观地对比分散的四要素与打包的迭代器# // Copyright 2024 Google LLC # // SPDX-License-Identifier: Apache-2.0 # let array [2, 4, 6, 8]; let mut i 0; while i array.len() { let elem array[i]; i 1; }可以看到let mut i 0承担状态职责i array.len()是终止条件i 1更新状态array[i]取值。这正是下一节Iteratortrait 中next方法内部要做的事——只不过把这份家务活收进了迭代器自己的结构体里。1.2 扩展视角指针版本的 C/C 遍历除了下标法C/C 还允许用首尾指针实现遍历以指针比较作为终止条件for (int *ptr array; ptr array len; ptr 1) { int elem *ptr; }这个版本值得特别说明Rust 标准库中 slice 与数组的迭代器底层正是以这种方式工作的——通过指向切片首尾的指针来推进和判断结束而不是逐次做下标运算唯一的差别是它在 Rust 中被实现为一种迭代器。这为后文为什么标准库迭代器可以消除边界检查埋下伏笔。二、Iteratortrait迭代器的契约与手动实现把状态 逻辑打包成对象之后就需要一个统一的接口来描述这个对象如何产生一个值序列——这就是Iterator。Iteratortrait 的核心只有一个抽象方法next它同时回答了何时结束返回None与下一个值是什么返回Some(item)# // Copyright 2023 Google LLC # // SPDX-License-Identifier: Apache-2.0 # struct SliceIters { slice: s [i32], i: usize, } impls Iterator for SliceIters { type Item s i32; fn next(mut self) - OptionSelf::Item { if self.i self.slice.len() { None } else { let next self.slice[self.i]; self.i 1; Some(next) } } } fn main() { let slice [2, 4, 6, 8]; let iter SliceIter { slice, i: 0 }; for elem in iter { dbg!(elem); } }对比第一节的while版本可以发现i slice.len()就是原终止条件self.i 1就是状态更新self.slice[self.i]就是取值逻辑。SliceIter完整复刻了 C 风格 for 循环的全部逻辑只是把它们收纳进了结构体与next方法内部。同时这个例子也是一个包含引用的结构体因此必须书写生命周期标注s是理解结构体生命周期的一个绝佳样例。2.1 迭代器是惰性的Lazy从源码实现可以清晰看出SliceIter { slice, i: 0 }只是初始化了一个结构体构造迭代器本身不执行任何遍历工作所有工作都推迟到next被调用时才发生。这就是迭代器的惰性lazy特性它让描述一次遍历与真正执行遍历解耦是后续各种适配器方法能够零开销组合的基础。2.2 迭代器不必是有限的next返回None才代表结束因此一个永远产生值的迭代器是完全合法的。例如半开区间0..会一直向后推进直到整数溢出为止届时标准库实现会通过内部检查使其在 debug 与 release 模式下都安全地结束。2.3 标准库的真实实现slice::Iter课堂上动手实现的SliceIter是对标准库slice::Iter的教学简化版。两者的关键差异是标准库版本底层使用指针指向切片首尾而非下标从而消除每次取值的边界检查bounds check。这印证了 1.2 节的说法也解释了越复杂的组合迭代器依然可以编译出与手写命令式循环同等高效的代码详见第四节。三、IntoIterator让 for 循环跑起来的那条 traitIterator描述的是拿到迭代器之后怎么迭代而IntoIterator。IntoIterator的实现者必须声明两个关联类型Item要迭代的元素类型例如i32IntoIterinto_iter方法返回的迭代器类型。注意IntoIter与Item是绑定的该迭代器的Iterator::Item必须与IntoIterator::Item一致即它必须产出OptionItem。下面是一个为自定义Grid类型实现IntoIterator的完整示例它按行主序产出所有 (x, y) 坐标组合# // Copyright 2023 Google LLC # // SPDX-License-Identifier: Apache-2.0 # struct Grid { x_coords: Vecu32, y_coords: Vecu32, } impl IntoIterator for Grid { type Item (u32, u32); type IntoIter GridIter; fn into_iter(self) - GridIter { GridIter { grid: self, i: 0, j: 0 } } } struct GridIter { grid: Grid, i: usize, j: usize, } impl Iterator for GridIter { type Item (u32, u32); fn next(mut self) - Option(u32, u32) { if self.i self.grid.x_coords.len() { self.i 0; self.j 1; if self.j self.grid.y_coords.len() { return None; } } let res Some((self.grid.x_coords[self.i], self.grid.y_coords[self.j])); self.i 1; res } } fn main() { let grid Grid { x_coords: vec![3, 5, 7, 9], y_coords: vec![10, 20, 30, 40] }; for (x, y) in grid { println!(point {x}, {y}); } }3.1 为什么some_vec.next()不存在IntoIterator由VecT、VecT、[T]、区间range等集合类型实现。这正是for i in some_vec { .. }能直接工作的原因同时也是some_vec.next()不存在的原因——Vec本身不是Iterator它只是可以被转换成迭代器的IntoIterator。3.2 所有权陷阱into_iter会消费self试着在main中对同一个grid迭代两次会编译失败。原因在于IntoIterator::into_iter按值接收self即取得所有权。标准库类型同样如此for e in some_vector会消费some_vector并迭代其拥有的元素如果只想借用应写for e in some_vector迭代元素的引用。对应的修复方式是再为Grid实现IntoIterator并创建一个按引用迭代的GridRefIterGrid的Item相应变为(u32, u32)从而支持多次迭代。四、70 适配器方法与collect把遍历变成函数式管道Iteratortrait 的价值不止于next它还提供了70 多个辅助方法详见 src/iterators/helpers.md可以组合出定制化的遍历行为。4.1 方法链示例filter → map → sum# // Copyright 2024 Google LLC # // SPDX-License-Identifier: Apache-2.0 # fn main() { let result: i32 (1..10) // Create a range from 1 to 10 .filter(|x| x % 2 0) // Keep only even numbers .map(|x| x * x) // Square each number .sum(); // Sum up all the squared numbers println!(The sum of squares of even numbers from 1 to 10 is: {}, result); }这些辅助方法可分为两类适配器方法iterator adapter methods如map、filter接收原迭代器、产出一个行为不同的新迭代器保持惰性不立即求值消费方法consuming methods如sum、count会把迭代器里的元素全部拉出来再计算。由于方法设计为可链式调用chaining你可以像搭管道一样拼出恰好满足需求的定制迭代器。更重要的是性能Rust 的迭代器组合经过 LLVM 优化后即使串联大量适配器也能生成与等价命令式实现同等高效的机器码——零成本抽象。4.2collect把迭代器变回集合适配器链的终点通常是collect详见 src/iterators/collect.md它把一个Iterator构建成一个具体集合# // Copyright 2024 Google LLC # // SPDX-License-Identifier: Apache-2.0 # fn main() { let primes vec![2, 3, 5, 7]; let prime_squares primes.into_iter().map(|p| p * p).collect::Vec_(); println!(prime_squares: {prime_squares:?}); }任意迭代器都可以收集为Vec、VecDeque或HashSet产出键值对二元组的迭代器还能收集为HashMap和BTreeMap。指定返回集合类型有两种写法turbofish 形式some_iterator.collect::COLLECTION_TYPE()上例中的_让编译器推断Vec的元素类型类型推断形式let prime_squares: Vec_ some_iterator.collect();。之所以collect常常需要类型标注是因为它对返回类型B是泛型的编译器难以在多数场景自行推断。4.3 背后的机制FromIterator如果学生好奇collect是如何工作的答案是FromIteratortrait——它定义了每种集合如何从迭代器构建。除Vec、HashMap等基础实现外还有一些特殊实现例如能把IteratorItem ResultV, E直接转换成ResultVecV, E遇错即停并返回首个错误。五、实战验证练习offset_differences与仓库内测试为了把上述概念落到可运行、可验证的代码上本课程配套了练习 src/iterators/exercise.md要求只用一个迭代器表达式完成任务并通过全部单元测试完整答案位于 src/iterators/solution.md其源码在 src/iterators/exercise.rs 中可见。题目定义如下计算values中相隔offset的元素之差且从末尾回绕到开头即结果第n项为values[(noffset)%len] - values[n]。经典解法把回绕翻译为无限循环 跳过前 offset 个// 摘自 src/iterators/exercise.rsANCHOR: solution fn offset_differences(offset: usize, values: Veci32) - Veci32 { let a values.iter(); let b values.iter().cycle().skip(offset); a.zip(b).map(|(a, b)| *b - *a).collect() }这条一行管道同时用到了本文学过的多个知识点.iter()通过IntoIterator拿到按引用迭代的迭代器.cycle()无限迭代器2.2 节所说的不必有限在这里就是生产力——把values的引用无限循环重复.skip(offset)适配器方法跳过前offset个元素等效于按offset偏移的起始位置.zip(b)把两个迭代器按位置配对实现(noffset)%len与n的同步对齐.map(|(a, b)| *b - *a)计算差值.collect()收集回Veci32。练习自带的单元测试同样位于 src/iterators/exercise.rs 的unit-tests锚点覆盖了多种场景可作为正确性基准测试函数覆盖场景代表性断言test_offset_one偏移 1 的基本情况offset_differences(1, vec![1, 3, 5, 7]) vec![2, 2, 2, -6]末尾回绕到开头test_larger_offsets偏移 2/3/4/5含偏移超过长度偏移 4 时结果为全零自我相减test_degenerate_cases单元素与空数组等退化情况单元素结果为vec![0]空数组结果为vec![]5.1 本地运行方式src/iterators/Cargo.toml将练习文件配置为一个名为iterators、库名为offset_differences的 crateedition 2024publish false。在该目录执行cargo test即可运行上述单元测试验证解法的正确性直接在 playground 中复制代码亦可得到同样结果。六、总结从分散的四要素到统一的迭代模型回看本文开头提出的四个必要条件——状态、终止条件、状态更新、取值逻辑C 风格 for 循环把四者分散在循环头与循环体中直观但难以复用Rust 迭代器通过Iteratortrait 的next方法把四者打包进一个对象并通过IntoIterator让for循环自动创建迭代器适配器方法链 collect把如何遍历抽象成可组合、惰性、零开销的管道offset_differences一行解法正是这套模型的缩影。理解了动机也就理解了Iterator一切后续便利的根基惰性、无限、可组合、可优化都源于遍历只是状态与逻辑的打包。本课程的后续章节 Iterator Helper Methods、collect、IntoIterator 及 练习 均围绕这一模型展开可以在完整课程 SUMMARY.md 中按顺序继续深入学习。【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考