rust - 惯用地将值从一个 Vec 移动/排序到另一个

Question

我最近接触了 rust，来自 python 背景。我仍然掌握函数式编程的窍门，所以我正在寻找有关编写惯用 Rust 的见解/反馈。

在下面的示例中，我有一个 Parent 元素和 Child 元素的列表，并希望将 Child 元素分类到它们各自的父元素中关闭 id。

在 python 中，我会嵌套两个 for 循环，执行测试并相应地继续。但我不太确定是否有更好/性能/惯用的方法来做到这一点。

我已经标记了有问题的代码部分。尽管任何反馈都很棒!

这是一个可以使用的 Playground : https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=233cfa5b5798090fa969ba348a479b1c

#[derive(Debug)]
struct Parent {
    id: String,
    children: Vec<Child>,
}

impl Parent {
    pub fn from_id(id: String) -> Self {
        Self {
            id,
            children: Vec::new(),
        }
    }
}

#[derive(Debug)]
struct Child {
    parent_id: String,
}

impl Child {
    pub fn from_parent_id(parent_id: String) -> Self {
        Self { parent_id }
    }
}

fn main() {
    let mut parents: Vec<Parent> = vec!["a", "b", "c"]
        .iter()
        .map(|s| s.to_string())
        .map(Parent::from_id)
        .collect();

    let mut children: Vec<Child> = vec!["a", "a", "b", "c", "c", "c"]
        .iter()
        .map(|s| s.to_string())
        .map(Child::from_parent_id)
        .collect();

    // Is there a better way to do this?
    while let Some(child) = children.pop() {
        for parent in parents.iter_mut() {
            if child.parent_id == parent.id {
                parent.children.push(child);
                break;
            }
        }
    }

    dbg!(parents);
    dbg!(children);
}

Answer 1

当您需要保留部分或全部向量时，通常会使用从向量末尾弹出项目。如果需要消费整个vector，可以直接传递给for循环:

for child in children {
    for parent in parents.iter_mut() {
        if child.parent_id == parent.id {
            parent.children.push(child);
            break;
        }
    }
}

您可以使用迭代器来查找父级，如下所示:

for child in children {
    parents
        .iter_mut()
        .find(|parent| parent.id == child.parent_id)
        .map(|parent| parent.children.push(child));
}

最重要的性能问题是，这需要执行总共 n*m 次迭代，其中 n 和 m 是 parent 和 child 。如果这些数字可以达到数万，您最终将进行数亿次迭代，这会减慢您的速度。您可以为父向量创建一个 id->position 的临时映射，可以使操作 O(n + m):

let parent_pos_by_id: HashMap<_, _> = parents
    .iter()
    .enumerate()
    .map(|(idx, parent)| (parent.id.clone(), idx))
    .collect();

for child in children {
    if let Some(&parent_pos) = parent_pos_by_id.get(&child.parent_id) {
        parents[parent_pos].children.push(child);
    }
}