# How to map slices from vec, and then sort that vec based on that map

Ideally I’d like to do this all efficiently, without needing to clone things.

Here’s a concrete example of what I’m trying to do.

First I have a list of of file paths:

``````test/
test/a
test/b
test/b/1
test/b/2
test/b/3
``````

Modeled like this:

``````let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], vec!["test", "b", "1"], vec!["test", "b", "2"], vec!["test", "b", "3"]];
``````

I would like to sort this list of paths by the number of items contained in the parent folder of each path item. So first I need to calculate the number of items in each “folder”, I store those results in a map like this:

``````for each in items.iter() {
let parent = &each[0..each.len() - 1];
*map.entry(parent).or_insert(0) += 1;
}
``````

And the resulting map looks like:

``````{
[]: 1,
["test"]: 2,
["test", "b"]: 3
}
``````

Next I want to use this map to sort the collection of items. I’m trying to do that like this:

``````items.sort_unstable_by(|a, b| {
let a_parent = &a[0..a.len() - 1];
let b_parent = &b[0..b.len() - 1];
map.get(a_parent).unwrap_or(&0).cmp(&map.get(b_parent).unwrap_or(&0))
});
``````

But when I try that I’m running into borrowing problems saying “cannot borrow `items` as mutable because it is also borrowed as immutable”. I think I generally understand why rust is complaining. But I also generally think that in this case the code is OK, I want to know how to get rust to also think that it’s OK.

Here’s full (non-working) code:

``````use std::collections::HashMap;

fn main() {
let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], vec!["test", "b", "1"], vec!["test", "b", "2"], vec!["test", "b", "3"]];
let mut map: HashMap<&[&str], usize> = HashMap::new();

for each in items.iter() {
let parent = &each[0..each.len() - 1];
*map.entry(parent).or_insert(0) += 1;
}

items.sort_unstable_by(|a, b| {
let a_parent = &a[0..a.len() - 1];
let b_parent = &b[0..b.len() - 1];
map.get(a_parent).unwrap_or(&0).cmp(&map.get(b_parent).unwrap_or(&0))
});

println!("{:?}", items);
println!("{:?}", map);
}
``````

Errors:

``````   Compiling playground v0.0.1 (file:///playground)
warning: unused import: `std::cmp::Ordering`
--> src/main.rs:2:9
|
2 |     use std::cmp::Ordering;
|         ^^^^^^^^^^^^^^^^^^
|
= note: #[warn(unused_imports)] on by default

error[E0502]: cannot borrow `items` as mutable because it is also borrowed as immutable
--> src/main.rs:13:9
|
8  |         for each in items.iter() {
|                     ----- immutable borrow occurs here
...
13 |         items.sort_unstable_by(|a, b| {
|         ^^^^^ mutable borrow occurs here
...
21 |     }
|     - immutable borrow ends here

error: aborting due to previous error

error: Could not compile `playground`.

``````

• The type system is not expressive enough to express why this is valid.
• Even NLL won’t save you!

The good news:

• You’re correct; what you want to do is safe.
• Rust does kinda support what you’re trying to do, but you’ll have to twist things a bit.

``````// was
let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], ...];
// now
let mut items = vec![&["test"][..], &["test", "a"][..], &["test", "b"][..], ...];
``````

or even better (to show that we aren’t relying on `'static` lifetimes):

``````fn foo(mut items: Vec<&[&str]>) {
...
}
``````

This change is enough to make it compile. What happens is basically that:

• Let’s name some lifetimes. Consider the type of `items` to be `Vec<&'a [&'b str]>`. (`Vec<Vec<&'b str>>` in the original)
• When you call `items.iter()`, `items` is implicitly borrowed; call this lifetime `'iter`.
• In the original code:
• `items` has type `Vec<&'b str>`
• `each` has type `&'iter Vec<&'b str>`
• `each[...]` is an l-value of type `Vec<&'b str>`.
• `&each[...]` has type `&'iter Vec<&'b str>`.
• In the modified code:
• `items` has type `&'a [&'b str]`
• `each` has type `&'iter &'a [&'b str]`
• `each[...]` first copies the `&[T]` to produce a temporary `&'a [&'b str]`,
which is then indexed to produce an l-value of type `[&'b str]`
• `&each[...]` has type `&'a [&'b str]`.

In the latter case, thanks to the Copy, the `'iter` lifetime disappears from `parent` in much the same way that the `'a` disappears from a `&'a i32` when you dereference it to produce an `i32`.

1 Like