如何在Rust中编写针对嵌套集合的泛型函数？

我希望在Rust中编写一个泛型函数，能够对包含嵌套集合的元素集合进行多次迭代。元素为(Label, Collection<Elem>)形式的元组，其中Label为任意类型，Collection是可多次迭代、元素类型为Elem的集合。我需要确保多次迭代过程中不会意外克隆任何集合。

此类集合示例：

let collection1 = vec![(1u8,vec![0u8,1u8]), (2u8,vec![2u8,3u8,4u8])];
let collection2 = LinkedList::from([("a",[1,2,3]), ("b",[4,5,6])]);

可对collection1进行无克隆迭代的非泛型函数示例：

fn nesting(collection : &Vec<(u8,Vec<u8>)>) -> () {
    for (l,c) in collection {
        print!("{}: ",l);
        for e in c.iter() {
            print!("{}, ",e);
        }
        for e in c.iter() {
            print!("{}, ",e);
        }
        println!();
    }
    for (l,_) in collection {
        println!("{:?}",l);
    }
}

我曾考虑过如下实现方式：

fn nesting<'a, L:'a,N:'a,I:Clone+IntoIterator<Item=&'a (L,N)>>(collection: I) -> ()
{ 
  for i in collection.clone() { /* ... */ };
  for i in collection.clone() { /* ... */ };
}

该方式可接收集合的共享引用，但也能接收包含引用的集合，此时会克隆整个集合。另外，N应满足何种类型约束？

核心思路 #

要实现无克隆的多次迭代，关键是让泛型参数接收集合的共享引用而非集合本身，同时为嵌套集合N添加能生成共享迭代器的约束——这样外层、内层集合都能通过引用多次迭代，完全避免不必要的克隆开销。

正确的泛型约束实现 #

use std::collections::LinkedList;
use std::iter::IntoIterator;

fn nesting<'a, L, N, I, InnerIter>(collection: I)
where
    // 外层迭代器输出元组的共享引用
    I: IntoIterator<Item = &'a (L, N)>,
    // 嵌套集合N能生成共享迭代器，迭代元素为Elem的共享引用
    N: 'a + IntoIterator<IntoIter = InnerIter>,
    InnerIter: Iterator<Item = &'a N::Item>,
{
    // 第一次迭代外层集合，同时多次迭代内层集合
    for (label, inner_col) in collection.into_iter() {
        print!("{}: ", label);
        // 第一次迭代内层
        for elem in inner_col.into_iter() {
            print!("{}, ", elem);
        }
        // 第二次迭代内层，无克隆
        for elem in inner_col.into_iter() {
            print!("{}, ", elem);
        }
        println!();
    }
}

针对疑问的细节说明 #

1. 避免集合克隆的关键
   如果直接接收集合类型（如Vec<(L,N)>），多次迭代要么需要克隆整个集合（性能代价高），要么会消耗集合（仅能迭代一次）。而接收集合的共享引用（如&Vec<(L,N)>），引用本身是Clone的，克隆只是复制指针，无额外开销，且能多次迭代原集合。

2. N的类型约束
   N需要实现IntoIterator，且生成的迭代器输出N::Item的共享引用（即&Elem）。这对应标准库中大多数集合的iter()方法行为——比如Vec的iter()返回Iter<'a, T>，它实现了Iterator<Item = &'a T>，满足内层多次无克隆迭代的需求。

3. 支持外层多次迭代的优化
   如果函数需要多次迭代整个外层集合，只需给外层迭代器加上Clone约束（共享引用本身就实现了Clone），示例如下：

   fn nesting<'a, L, N, I, InnerIter>(collection: I)
   where
       I: Clone + IntoIterator<Item = &'a (L, N)>,
       N: 'a + IntoIterator<IntoIter = InnerIter>,
       InnerIter: Iterator<Item = &'a N::Item>,
   {
       // 第一次迭代外层
       for (l, c) in collection.clone() {
           // ...内层迭代逻辑
       }
       // 第二次迭代外层，无克隆
       for (l, _) in collection {
           println!("{:?}", l);
       }
   }
   

测试验证 #

用你给出的集合测试上述函数：

fn main() {
    let collection1 = vec![(1u8, vec![0u8, 1u8]), (2u8, vec![2u8, 3u8, 4u8])];
    nesting(&collection1);

    let collection2 = LinkedList::from([("a", [1, 2, 3]), ("b", [4, 5, 6])]);
    nesting(&collection2);
}

运行输出：

1: 0, 1, 0, 1, 
2: 2, 3, 4, 2, 3, 4, 
1
2
a: 1, 2, 3, 1, 2, 3, 
b: 4, 5, 6, 4, 5, 6, 
"a"
"b"

全程无任何集合克隆操作。

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