Idiomatically moving/sorting values from one Vec into another

Question

I recently picked up rust, coming from a python background. I'm still getting the hang of functional programming so I'm looking for insight/feedback on writing idiomatic rust.

In the example below I have a list of Parent elements and Child elements and want to sort the Child elements into their respective parents based off of an id.

In python I would nest two for loops, perform a test and continue accordingly. But I'm not quite sure if there is a better/performant/idiomatic way of doing this.

I've marked the section of the code in question. Although any feedback is great!

Here's a working playgound: 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

Popping items off the end of the vector is mostly used when you need to retain parts or all of the vector. If you need to consume the whole vector, you can pass it to the for loop directly:

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

You can use iterators to look for the parent, like this:

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

The most important issue with performance is that this needs to perform n*m iterations in total, where n and m are number of parents and children. If those numbers can go into tens of thousands, you will end up with hundreds of millions of iterations, which will slow you down. You can create a temporary mapping of id->position for the parents vector can make the operation 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);
    }
}