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

发布于12月21日

我想要对VecDeque进行排序或倒排.在Rust 1.48.0或更高版本中，您可以使用make_contiguous()可变地访问底层片来执行以下操作:

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

然而，我不得不在竞争性编程中使用Rust 1.42.0.unsafe是允许的.夜间Rust 是不允许的.

我不想先将VecDeque收集到Vec中，然后反转或排序结果，最后将Vec收集回VecDeque，这似乎不必要地非常缓慢和冗长.

有没有更优雅的方式？

推荐答案

把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等于implemented:这是一个单一的内存分配，在结尾和开始(如果是head > tail)或中间(如果是head < tail)都有空洞.

如果孔位于起点和终点，则元素已经是连续的.
If the hole is in the middle, the front of the deque is at the end of the allocation, and the back of the deque is at the beginning of the allocation. rotate_right "pops the last k items and pushes them to the front.", i.e. it removes the elements at the start of the allocation and adds them to the elements at the back of the allocation, so the deque will be contiguous.
(The way I read the docs, there's not really a guarantee that it will always be that way, which is why I like having the assert there.)

最后，如果二人组是连续的， as_slice(和它的mut个朋友) 将返回两个切片，但第二个切片将为空，所有元素都在第一个切片中.

此外，使用SO进行编码比赛可能会被认为是作弊.