如何在没有 `make_contigious()` 的情况下对 VecDeque 进行排序或反转？

Question

我想排序或反转

VecDeque

。在 Rust 1.48.0 或更高版本中，您可以使用

make_contiguous()

可变地访问底层切片来执行此类操作：

v.make_contiguous().reverse(); //reverse
v.make_contiguous().sort(); //sort

但是，我在竞争性编程中必须使用 Rust 1.42.0。

unsafe

是允许的。不允许夜间生锈。

我不想先将

VecDeque

收集到

Vec

中，然后对结果进行反转或排序，最后将

Vec

收集回

VecDeque

，这似乎不必要地非常缓慢和冗长。

还有更优雅的方式吗？

Answer 1

合并

as_mut_slices

和

rotate_right

。

fn sort_vecdeque<T: Ord>(x: &mut VecDeque<T>) {
    x.rotate_right(x.as_slices().1.len());
    assert!(x.as_slices().1.is_empty());
    x.as_mut_slices().0.sort();
}

这之所以有效，是因为

VecDeque

是如何实现的：它是一个单一的内存分配，在末尾和开始（如果head > tail

）或在中间（如果

head < tail

）都有孔。

如果孔位于开始和结束处，则元素已经是连续的。
如果孔在中间，则双端队列的前端位于 分配，双端队列的后面是分配的开始。
• rotate_right“弹出 最后 k 个项目并将它们推到前面。”，即它删除了 分配开始时的元素并将它们添加到元素中 位于分配的后面，因此双端队列将是连续的。 （以我阅读文档的方式，并不能真正保证它总是这样，这就是为什么我喜欢在那里有断言。）
  

最后，如果双端队列是连续的，

as_slice

（和它的mut

朋友）
将返回两个切片，但第二个切片将为空，所有元素都在第一个切片中。

此外，使用 SO 进行编码竞赛可能会被视为作弊。