我正在创建一个"排序迭代器";它取未排序项的切片并按排序顺序输出它们然后在使用堆排序时对底层切片进行排序。问题是在迭代器实现中存在冲突的生命周期。
相关代码如下:
struct SortedIterator<'a, T:'a+Ord> {
heap: &'a mut [T],
iteration: usize
}
fn getChildren(pos: usize, total_size: usize) -> (usize, usize) {
let diff = 2*(total_size - pos);
(total_size - diff - 1, total_size - diff - 2)
}
impl<'a, T:'a+Ord> Iterator for SortedIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.iteration < self.heap.len() {
self.heap.swap(self.iteration, self.heap.len());
self.iteration += 1;
// restore heap here
let mut swapped = true;
let mut current_pos = self.heap.len() -1;
while swapped {
swapped = false;
let (left, right) = getChildren(current_pos, self.heap.len() - 1);
if self.iteration > left {
// it's children have entered into the sorted part of the array
// so we're actually at a leaf
continue;
} else if self.iteration > right {
// left is the last child, potentially swap it with parent and then
// we are done iterating
if self.heap[right] < self.heap[current_pos] {
self.heap.swap(right, current_pos);
}
} else if self.heap[left] < self.heap[current_pos] || self.heap[right] < self.heap[current_pos] {
swapped = true;
// swap parent with lower item of the two children, update position in the slice
// then iterate again
if self.heap[left] < self.heap[right] {
self.heap.swap(left, current_pos);
current_pos = left;
} else {
self.heap.swap(right, current_pos);
current_pos = right;
}
}
}
// the trouble occurs here, it says it
// expects <SortedIterator<'a, T> as std::iter::Iterator>
// found <SortedIterator<'_, T> as std::iter::Iterator>
Some(&self.heap[self.iteration - 1])
} else {
None
}
}
}
我只是不确定我可能需要一个额外的注释来解决Rust的生命周期混乱。
这是货物检查的错误
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
--> srclib.rs:73:19
|
73 | Some(&self.heap[self.iteration - 1])
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime defined here...
--> srclib.rs:36:13
|
36 | fn next(&mut self) -> Option<Self::Item> {
| ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
--> srclib.rs:73:19
|
73 | Some(&self.heap[self.iteration - 1])
| ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
--> srclib.rs:34:6
|
34 | impl<'a, T:'a+Ord> Iterator for SortedIterator<'a, T> {
| ^^
note: ...so that the types are compatible
--> srclib.rs:36:46
|
36 | fn next(&mut self) -> Option<Self::Item> {
| ______________________________________________^
37 | | if self.iteration < self.heap.len() {
38 | | self.heap.swap(self.iteration, self.heap.len());
39 | | self.iteration += 1;
... |
76 | | }
77 | | }
| |_____^
= note: expected `<SortedIterator<'a, T> as Iterator>`
found `<SortedIterator<'_, T> as Iterator>`
错误的原因是我如何使用返回可变引用的迭代器创建自己的数据结构?阅读那里的详细解释，但简而言之，这段代码:
impl<'a, T: 'a + Ord> Iterator for SortedIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
Some(&self.heap[self.iteration - 1])
}
}
与以下代码形式相同(并给出类似的错误):
struct S<'a>(&'a mut i32);
impl<'a> S<'a> {
fn f<'b>(&'b mut self) -> &'a i32 { &*self.0 }
}
我明确地注释了'b，因为它很容易看到出了什么问题:你不能使用生命期'b的self引用，它可能比'a短，但返回一个可以为整个'a存活的引用。这将允许调用者持有结果引用的时间比他们应该能够持有的时间更长，并且违反了"可别名"或"可变"原则。
// (Pseudo-Rust)
'a: {
let mut i: i32 = 123;
let mut s: S<'a> = S(&'a mut i);
let r1: &'a i32 = 'b: {
let s_r: &'b mut S = &'b mut S;
S::<'a>::f::<'b>(s_r)
// Reference `s_r` is destroyed here, but the returned value is still alive!
};
let r2: &'a mut i32 = &'a mut s;
// Now we got `r1` and `r2` both pointing to `i` while `r2` is mutable, boom!
}
解决方案是分割切片，只处理剩下的部分，而将排序后的部分逐元素释放到外部。因为我们不抓住它，就不会出错。编译器不能自动跟踪，所以我们使用std::mem::take()。我不会在这里发布完整的代码，但总体思路是这样的:
fn next(&mut self) -> Option<Self::Item> {
// This allow us to get rid of the length check (but you still can check then `unwrap()`).
let (first, heap) = std::mem::take(&mut self.heap).split_first_mut()?;
self.heap = heap;
// Calculations and sorting...
Some(first)
}