如何在 rust 中使用可变引用作为泛型函数的参数 [duplicate]

How to use mutable references as arguments for generic functions in rust [duplicate]

提问人:Joseph Stevens 提问时间:11/18/2023 最后编辑:cafce25Joseph Stevens 更新时间:11/18/2023 访问量:56

问:

我正在尝试练习使用策略模式,并考虑使用在运行时选择的函数对向量进行排序,理想情况下能够使用可变引用就地更改数据。

我试图在多个地方添加关键字,但无法弄清楚如何让我的代码与可变引用一起使用。&mut

这是我的代码

use rand::Rng;

#[derive(Clone)]
pub struct Sorter<F: Fn(Vec<T>) -> Vec<T>, T: Ord + Eq + Copy> {
    sort_strategy: F,
    sort_data: Vec<T>,
}

impl<F: Fn(Vec<T>) -> Vec<T>, T: Ord + Eq + Copy> Sorter<F, T> {
    // return self with sorted data
    // how do i remove the return self and make it a mutable reference to self
    pub fn sort(mut self) -> Self {
        self.sort_data = (self.sort_strategy)(self.sort_data);
        self
    }

    pub fn new(sort_strategy: F, sort_data: Vec<T>) -> Sorter<F, T> {
        Sorter {
            sort_strategy,
            sort_data,
        }
    }
}

// bubble sort function
pub fn bubble_sort<T: Eq + PartialOrd + Copy>(input_vector: Vec<T>) -> Vec<T> {
    let mut output_vector = input_vector.clone();
    for _ in 0..output_vector.len() {
        for j in 0..(output_vector.len() - 1) {
            if output_vector[j] > output_vector[j + 1] {
                output_vector.swap(j + 1, j);
            }
        }
    }
    output_vector
}

// quick sort function
pub fn quick_sort<T: Eq + PartialOrd + Copy>(input_vector: Vec<T>) -> Vec<T> {
    if input_vector.len() <= 1 {
        return input_vector;
    }

    let pivot = rand::thread_rng().gen_range(0..input_vector.len());
    let pivot_val = input_vector[pivot];
    let mut little_vector: Vec<T> = Vec::new();
    let mut big_vector: Vec<T> = Vec::new();

    for i in input_vector.iter().enumerate() {
        if i.0 == pivot {
            continue;
        }
        if *(i.1) > pivot_val {
            big_vector.push(*(i.1));
            continue;
        }
        if *(i.1) <= pivot_val {
            little_vector.push(*(i.1))
        }
    }

    little_vector = quick_sort(little_vector);
    little_vector.push(pivot_val);
    quick_sort(big_vector)
        .iter()
        .for_each(|n| little_vector.push(*n));

    little_vector
}

#[cfg(test)]
mod tests {
    use std::vec;

    use super::*;

    #[test]
    // test that bubble_sort is functional
    fn test_bubble_sort() {
        let data = vec![5, 4, 3, 2, 1];
        let result = bubble_sort(data);
        assert_eq!(result, vec![1, 2, 3, 4, 5])
    }

    #[test]
    // test that quick_sort is functional
    fn test_quick_sort() {
        let data = vec![5, 4, 3, 2, 1];
        let result = quick_sort(data);
        assert_eq!(result, vec![1, 2, 3, 4, 5])
    }

    #[test]
    // test that bubble_sort works in struct Sorter
    fn test_stratergy_pattern_bubble() {
        let sorter = Sorter::new(bubble_sort, vec![5, 4, 3, 2, 1]);
        let sorter = sorter.sort();
        assert_eq!(sorter.sort_data, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    // test that quick_sort works in struct Sorter
    fn test_stratergy_pattern_quick() {
        let sorter = Sorter::new(quick_sort, vec![5, 4, 3, 2, 1]);
        let sorter = sorter.sort();
        assert_eq!(sorter.sort_data, vec![1, 2, 3, 4, 5]);
    }
}

或者在 Rust 操场上

算法 rust 传递引用 策略模式

评论

0赞 user4815162342 11/30/2023
如果我的答案回答了你的问题,你可能要考虑接受它。

答:

0赞 user4815162342 11/18/2023 #1

作为第一步,“删除返回的 self 并使其成为对 self 的可变引用”意味着我们希望看起来像这样:Sorter::sort()

pub fn sort(&mut self) {
    self.sort_data = (self.sort_strategy)(self.sort_data);
}

这样做会抱怨无法移出引用。原因是您不能只获取驻留在 中的值,并将其传递给需要拥有值的函数,例如 .这样做会使状态保持部分移动状态 - 借用检查器支持该状态,但随后它将不允许进一步使用移动的字段,例如分配给 .self.sort_dataself.sort_strategyselfself.sort_data

如果您不想更改 的签名,那么最简单的方法是替换为空向量,即使用 .对于实现 的类型,例如 ,有一个函数可以替换为默认值。然后看起来像这样:sort_dataself.sort_datastd::mem::replace(&mut self.sort_data, vec![])DefaultVecstd::mem::take()sort()

pub fn sort(&mut self) {
    self.sort_data = (self.sort_strategy)(std::mem::take(&mut self.sort_data));
}

在对测试套件进行微不足道的更改后,无法捕获 的结果,您的测试通过。 (游乐场sort)

下一步是保持一致并调整排序函数以使其也能就地工作,即将边界从 更改为 或者,更好的是,(因为您不需要增大或缩小向量,因此您可以直接对切片进行排序)。在这种情况下,将如下所示:Fn(Vec<T>) -> Vec<T>Fn(&mut Vec<T>)Fn(&mut [T])Sorter

#[derive(Clone)]
pub struct Sorter<F, T> {
    sort_strategy: F,
    sort_data: Vec<T>,
}

impl<F: Fn(&mut [T]), T: Ord + Eq> Sorter<F, T> {
    pub fn sort(&mut self) {
        (self.sort_strategy)(&mut self.sort_data);
    }

    // new is unchanged
}

排序函数不再返回值,而只是就地获取和排序,而不是分配 - 这就是在标准库中定义排序方法的方式。就您而言:bubble_sort()&mut [T]

pub fn bubble_sort<T: Eq + Ord>(vector: &mut [T]) {
    for _ in 0..vector.len() {
        for j in 0..(vector.len() - 1) {
            if vector[j] > vector[j + 1] {
                vector.swap(j + 1, j);
            }
        }
    }
}

操场

(quick_sort()像这样重写需要更多的工作,所以我跳过了它。

旁注:

  • 你不需要,交换值是通过移动来工作的。T: Copy
  • require 而不是 ,因为排序取决于总顺序,这是 提供的保证。T: OrdT: PartialOrdOrd
  • 即使在分拣机取回 a 的设计中,分拣机也会自然而然地分拣到位。在这种情况下,它可以在输入向量上工作并返回它,没有理由将其克隆为“输出”向量。Vecbubble_sort()