Rust泛型merge函数：不实现Copy trait解决可变引用后移动问题

核心问题分析 #

当传入可变引用（如&mut [T]）时，into_iter()返回的迭代器元素类型是&mut T而非T，无法直接移动元素，这是Rust所有权机制的固有限制。

方案1：非原地归并（仅需PartialOrd约束） #

让merge函数接收两个可消费的迭代器（实现IntoIterator<Item = T>），直接获取T类型元素并移动到结果集合中，无需额外约束：

use std::cmp::PartialOrd;

fn merge<T: PartialOrd>(left: impl IntoIterator<Item = T>, right: impl IntoIterator<Item = T>) -> Vec<T> {
    let mut left_iter = left.into_iter();
    let mut right_iter = right.into_iter();
    let mut left_val = left_iter.next();
    let mut right_val = right_iter.next();
    let mut merged = Vec::new();

    loop {
        match (left_val.take(), right_val.take()) {
            (Some(l), Some(r)) => {
                if l <= r {
                    merged.push(l);
                    right_val = Some(r);
                    left_val = left_iter.next();
                } else {
                    merged.push(r);
                    left_val = Some(l);
                    right_val = right_iter.next();
                }
            }
            (Some(l), None) => {
                merged.push(l);
                merged.extend(left_iter);
                break;
            }
            (None, Some(r)) => {
                merged.push(r);
                merged.extend(right_iter);
                break;
            }
            (None, None) => break,
        }
    }

    merged
}

使用示例 #

fn main() {
    let left = vec![1, 3, 5];
    let right = vec![2, 4, 6];
    let merged = merge(left, right);
    println!("{:?}", merged); // 输出 [1, 2, 3, 4, 5, 6]

    // 处理切片（需T实现Clone）
    let left_slice = &[1, 3, 5];
    let right_slice = &[2, 4, 6];
    let merged_from_slice = merge(left_slice.iter().cloned(), right_slice.iter().cloned());
    println!("{:?}", merged_from_slice);
}

方案2：原地归并（需PartialOrd + Clone约束） #

如果必须在原切片上完成归并，需先复制左半部分到临时存储，再通过双指针将较小元素回填到原数组：

use std::cmp::PartialOrd;

fn merge_in_place<T: PartialOrd + Clone>(arr: &mut [T], mid: usize) {
    let (left, right) = arr.split_at_mut(mid);
    let mut left_temp = left.to_vec();
    let mut left_iter = left_temp.iter();
    let mut right_iter = right.iter_mut();
    let mut arr_iter = arr.iter_mut();

    while let (Some(l), Some(r)) = (left_iter.next(), right_iter.next()) {
        let target = arr_iter.next().unwrap();
        if l <= r {
            *target = l.clone();
        } else {
            std::mem::swap(target, r);
        }
    }

    // 回填剩余的左半部分元素
    for (target, l) in arr_iter.zip(left_iter) {
        *target = l.clone();
    }
}

使用示例 #

fn main() {
    let mut arr = vec![1, 3, 5, 2, 4, 6];
    merge_in_place(&mut arr, 3);
    println!("{:?}", arr); // 输出 [1, 2, 3, 4, 5, 6]
}

方案选择建议 #

• 优先使用非原地归并方案，仅需PartialOrd约束，代码简洁且符合Rust所有权模型，适合大多数归并排序场景。
• 若必须原地修改数组，再选择原地归并方案，此时T需额外实现Clone，这是临时存储元素的必要条件。

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