如何在不使用make_contiguous()的情况下对Rust的VecDeque排序或反转？

由于Rust 1.42.0尚未提供make_contiguous()，我们可以通过unsafe代码直接操作VecDeque的内部结构来实现高效的原地反转和排序，避免转换为Vec的开销。

原地反转 #

VecDeque的底层是环形缓冲区，反转的核心是交换环形中对称位置的元素。我们可以通过unsafe访问其私有字段（buf、head、tail），直接操作内存中的元素：

use std::collections::VecDeque;

unsafe fn reverse_vec_deque<T>(dq: &mut VecDeque<T>) {
    let len = dq.len();
    if len <= 1 {
        return;
    }

    // 定义与1.42.0版本VecDeque内部结构匹配的私有结构体
    #[repr(C)]
    struct VecDequePrivate<T> {
        buf: Vec<T>,
        head: usize,
        tail: usize,
    }

    // 转换为私有结构体指针以访问内部字段
    let private = dq.as_mut_ptr().cast::<VecDequePrivate<T>>();
    let head = (*private).head;
    let buf_ptr = (*private).buf.as_mut_ptr();
    let cap = (*private).buf.capacity();

    // 交换环形中对称位置的元素
    for i in 0..len / 2 {
        let left_idx = (head + i) % cap;
        let right_idx = (head + len - 1 - i) % cap;
        std::ptr::swap(buf_ptr.add(left_idx), buf_ptr.add(right_idx));
    }
}

使用示例：

let mut dq = VecDeque::from(vec![3, 4, 1, 2]);
unsafe { reverse_vec_deque(&mut dq) };
assert_eq!(dq, VecDeque::from(vec![2, 1, 4, 3]));

原地排序 #

排序需要随机访问连续的内存区域，我们可以手动实现make_contiguous()的核心逻辑：将环形缓冲区中的元素移动到内存起始位置使其连续，再调用切片的sort()方法：

use std::collections::VecDeque;

unsafe fn make_contiguous_142<T>(dq: &mut VecDeque<T>) -> &mut [T] {
    #[repr(C)]
    struct VecDequePrivate<T> {
        buf: Vec<T>,
        head: usize,
        tail: usize,
    }

    let private = dq.as_mut_ptr().cast::<VecDequePrivate<T>>();
    let head = (*private).head;
    let tail = (*private).tail;
    let buf = &mut (*private).buf;
    let len = dq.len();

    // 元素已经连续，直接返回切片
    if head == 0 {
        return &mut buf[0..len];
    }

    let cap = buf.capacity();
    if head < tail {
        // 元素是连续的一段，直接移动到缓冲区起始位置
        buf.copy_within(head..tail, 0);
    } else {
        // 元素分为两段，先将后半段移到缓冲区末尾，再将前半段移到起始位置
        buf.copy_within(0..tail, cap - tail);
        buf.copy_within(head..cap, 0);
    }

    // 更新head和tail，指向连续的元素范围
    (*private).head = 0;
    (*private).tail = len;

    &mut buf[0..len]
}

unsafe fn sort_vec_deque<T: Ord>(dq: &mut VecDeque<T>) {
    let contiguous_slice = make_contiguous_142(dq);
    contiguous_slice.sort();
}

使用示例：

let mut dq = VecDeque::from(vec![3, 4, 1, 2]);
unsafe { sort_vec_deque(&mut dq) };
assert_eq!(dq, VecDeque::from(vec![1, 2, 3, 4]));

说明 #

• 代码依赖1.42.0版本VecDeque的内部结构，若版本结构变化会失效，但完全符合题目版本限制。
• 使用#[repr(C)]保证结构体布局与标准库VecDeque一致，确保unsafe访问的安全性。
• 所有操作均在原地完成，无额外内存分配，效率与1.48+版本的make_contiguous()方案一致。

内容的提问来源于stack exchange，提问作者ynn