I'm trying to implement the merge function for my merge sort in Rust. The catch is that I'm trying to do it for a generic type T
, which is only restrained by std::cmp::PartialOrd
.
This is the code:
fn my_merge<T: std::cmp::PartialOrd>(a: &mut Vec<T>, mut b: &mut Vec<T>) -> Vec<T> {
let mut res: Vec<T> = Vec::new();
let mut a_iter = a.into_iter(); // !!!
let mut b_iter = b.into_iter(); // !!!
while let (Some(a_item), Some(b_iter)) = (a_iter.next(), b_iter.next()) {
if a_item <= b_item {
res.push(*a_item); // !!!
} else {
res.push(*b_item); // !!!
}
}
// ... Omitted code ...
res
}
When looking at documentation, I discovered the into_iter()
method, with which the next()
method is supposed to yield T
instead of &T
. But it only does so if the iterator isn't constructed on a reference (since I'm passing a slice into the function).
(Quick reminder: this is because of how borrowing works. See this StackOverflow question)
This is the same reason why you cannot dereference variables a_item
and b_item
on the lines with comments.
My question is: is there a way to solve this problem while keeping the generic type? It is almost paradoxical, as it is a very simple task in theory - "just move the ownership of an element from one vector to another" - but due to the ownership rules, this isn't as straightforward.
You can iterate through a Vec
while claiming ownership of the elements without consuming the original Vec
itself by using .drain(..)
:
fn my_merge<T: std::cmp::PartialOrd>(a: &mut Vec<T>, b: &mut Vec<T>) -> Vec<T> {
let mut res: Vec<T> = Vec::new();
let mut a_iter = a.drain(..);
let mut b_iter = b.drain(..);
while let (Some(a_item), Some(b_item)) = (a_iter.next(), b_iter.next()) {
if a_item <= b_item {
res.push(a_item);
} else {
res.push(b_item);
}
}
res
}
This of course will leave the inputs (a
and b
) empty but with their original capacity after merging.