Is it possible to map a function over Vec without allocating a new Vec?

Question

I have the following:

enum SomeType { VariantA(String), VariantB(String, i32), } fn transform(x: SomeType) -> SomeType { // very complicated transformation, reusing parts of x in order to produce result: match x { SomeType::VariantA(s) => SomeType::VariantB(s, 0), SomeType::VariantB(s, i) => SomeType::VariantB(s, 2 * i), } } fn main() { let mut data = vec![ SomeType::VariantA("hello".to_string()), SomeType::VariantA("bye".to_string()), SomeType::VariantB("asdf".to_string(), 34), ]; } 

Now I would like to call transform for each data element and save the resulting value back to data . I could do something like data.into_iter().map(transform).collect() , but this will data.into_iter().map(transform).collect() new Vec . Is there a way to do this in place by reusing the allocated data memory? When- Vec::map_in_place in Rust was Vec::map_in_place but it was removed some time ago.

As SomeType I added a Dummy option to SomeType and then did the following:

 for x in &mut data { let original = ::std::mem::replace(x, SomeType::Dummy); *x = transform(original); } 

This is not correct, and I have to deal with SomeType::Dummy everywhere in the code, although it should never be visible outside of this loop. Is there a better way to do this?

Answer 1

No, this is not possible at all, since the size of each element can change when performing a mapping ( fn transform(u8) → u32 ).

Even when the sizes are the same, it is not trivial.

In this case, you do not need to create a Dummy variant because creating an empty String is cheap; only 3 pointer size values ​​and no heap allocation:

 impl SomeType { fn transform(&mut self) { use SomeType::*; let old = std::mem::replace(self, VariantA(String::new())); // Note this line for the detailed explanation *self = match old { VariantA(s) => VariantB(s, 0), VariantB(s, i) => VariantB(s, 2 * i), }; } } 

 for x in &mut data { x.transform(); } 

An alternative implementation that simply replaces String :

 impl SomeType { fn transform(&mut self) { use SomeType::*; *self = match self { VariantA(s) => { let s = std::mem::replace(s, String::new()); VariantB(s, 0) } VariantB(s, i) => { let s = std::mem::replace(s, String::new()); VariantB(s, 2 * *i) } }; } } 

In general, yes, you need to create some kind of dummy value in order to do this in general and with safe code. Many times you can wrap the entire element in Option and call Option::take to achieve the same effect.

See also:

• Change the enumeration option when moving the field to the new variant

Why is it so hard?

Check out this proposed and now closed RFC for a variety of related discussions. My understanding of this RFC (and the difficulties behind it) is that there is a period of time when your value will have an indefinite value, which is unsafe . If panic happens at this moment, then when your value drops, you can cause undefined behavior, which is bad.

If your code panicked in a commented out line, then the self value is a specific, known value. If it were some unknown value, deleting this line would try to delete this unknown value, and we returned to C. It is the purpose of the Dummy value to always keep the value with a known value.

You even hinted at this (my selection):

I have to deal with SomeType::Dummy everywhere in the code, although it should never be visible outside this loop.

This "must" is a problem. During a panic, this dummy value is visible.

See also:

• How can I change the new value for a field in a mutable structure reference?
• Temporarily leave borrowed content
• How do I exit the structure field, which is an option?

Currently, the remote implementation of Vec::map_in_place takes up nearly 175 lines of code, most of which are related to unsafe code and explains why it is really safe! Some boxes re-implemented this concept and tried to make it safe; You can see an example of Sebastian Redle's answer .

Answer 2

Your first problem is not map , it is transform .

transform takes responsibility for its argument, and Vec owns its arguments. Either one should give, and punching a hole in Vec would be a bad idea: what if transform panic?

---

The best solution, therefore, is to change the transform signature to:

 fn transform(x: &mut SomeType) { ... } 

then you can just do:

 for x in &mut data { transform(x) } 

---

Other solutions will be awkward, as they will have to deal with what transform might panic.

Answer 3

You can write map_in_place in terms of take_mut or replace_with :

 fn map_in_place<T, F>(v: &mut [T], f: F) where F: Fn(T) -> T, { for e in v { take_mut::take(e, f); } } 

However, if this causes a panic in the provided function, the program is completely interrupted; You cannot recover from a panic.

Alternatively, you could provide a placeholder that is in an empty place while the internal function is executing:

 use std::mem; fn map_in_place_with_placeholder<T, F>(v: &mut [T], f: F, mut placeholder: T) where F: Fn(T) -> T, { for e in v { let mut tmp = mem::replace(e, placeholder); tmp = f(tmp); placeholder = mem::replace(e, tmp); } } 

If this panics, the placeholder you provided will be in the panic slot.

Finally, you can create a placeholder on demand; basically replace take_mut::take with take_mut::take_or_recover in the first version.