std::iter::once开销解析：链式迭代器消费时是否存在O(n)成本？

你给出的代码如下：

pub fn f(x: u16) -> impl Iterator<Item = u16> {
    std::iter::once(0).chain((x >> 10)..x)
}

核心结论 #

这个链式迭代器在消费时不会产生O(n)的额外开销，只有常数级的极小开销。

原因解释 #

• Rust迭代器是惰性求值的：chain只是把两个迭代器包装成一个Chain结构体，不会提前预先生成所有元素或者分配额外的内存空间。
• 两个子迭代器都是零开销实现：std::iter::once是仅存单个元素的迭代器，(x >> 10)..x是范围迭代器（Range类型），它们都只在栈上存储少量状态（比如once是否已经产出过元素、Range的当前位置和结束值），完全不需要堆内存。
• 消费过程的开销：迭代时会先取出once里的0，之后直接切换到遍历Range迭代器，每一个元素的访问都是O(1)操作，没有批量处理带来的O(n)额外开销。

如何验证判断 #

1. 查看迭代器实现逻辑：
   Rust标准库的迭代器适配器（比如chain）都是惰性的，你可以直接看Chain的源码——它只是持有两个子迭代器的所有权，每次调用next()时，先尝试从第一个迭代器取元素，取完后再从第二个迭代器取，全程没有O(n)的批量操作。

2. 基准测试对比：
   写一个简单的基准测试，对比手动先输出0再遍历范围，和使用链式迭代器的性能差异：

   #[cfg(test)]
   mod benches {
       use super::*;
       use test::Bencher;
   
       #[bench]
       fn bench_chain_iter(b: &mut Bencher) {
           let x = 0xFFFF;
           b.iter(|| {
               let mut sum = 0u64;
               for num in f(x) {
                   sum += num as u64;
               }
               sum
           });
       }
   
       #[bench]
       fn bench_manual_iter(b: &mut Bencher) {
           let x = 0xFFFF;
           let start = x >> 10;
           b.iter(|| {
               let mut sum = 0u64;
               sum += 0;
               for num in start..x {
                   sum += num as u64;
               }
               sum
           });
       }
   }
   

   运行cargo bench后，如果两个测试的耗时差距在误差范围内，就足以证明链式迭代器没有额外的O(n)开销。

内容的提问来源于stack exchange，提问作者user1002430