Rust 中有循环旋转可变变量的标准方法吗？

Question

实现算法中一个非常常见的操作是循环旋转：给定 3 个变量 a、b、c，将它们更改为

的效果

t ⇽ c
c ⇽ b
b ⇽ a
a ⇽ t

鉴于一切都是可按位交换的，循环旋转应该是 Rust 比我所知道的任何其他语言更擅长的领域。

为了比较，在 C++ 中，旋转 N 个元素的最有效的通用方法是执行 n+1

std::move

操作，这反过来粗略地导致（对于典型的移动构造函数实现）

3 (n+1) sizeof(T)

字分配（这可以改进为POD 通过模板专门旋转，但需要工作）。

在 Rust 中，该语言可以仅通过

(n+1) size_of(T)

单词分配来实现旋转。令我惊讶的是，我找不到对轮换的标准库支持。 （

std::mem

中没有旋转方法）。它可能看起来像这样：

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    unsafe {
        let mut t: T = std::mem::uninitialized();
        std::ptr::copy_nonoverlapping(&*z, &mut t, 1);
        std::ptr::copy_nonoverlapping(&*y, z, 1);
        std::ptr::copy_nonoverlapping(&*x, y, 1);
        std::ptr::copy_nonoverlapping(&t, x, 1);
        std::mem::forget(t);
    }
}

---

要澄清为什么在 C++ 中无法有效实现旋转，请考虑：

struct String {
  char *data1;
  char *data2;
  String(String &&other) : data1(other.data1), data2(other.data2)
    { other.data1 = other.data2 = nullptr;}
  String &operator=(String &&other)
    { std::swap(data1, other.data1); std::swap(data2, other.data2);
      return *this; }
  ~String() { delete [] data1; delete [] data2; }
};

这里像

s2 = std::move(s1);

这样的操作将为每个成员字段进行 3 次指针赋值，总共 6 次赋值，因为指针交换需要 3 次赋值（1 次进入 temp，1 次离开 temp，1 次跨操作数）

Answer 1

Rust 中有循环旋转可变变量的标准方法吗？

没有。

我只需交换变量两次，不需要

unsafe

：

use std::mem;

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    mem::swap(x, y);
    mem::swap(y, z);
}

fn main() {
    let mut a = 1;
    let mut b = 2;
    let mut c = 3;

    println!("{}, {}, {}", a, b, c);
    // 1, 2, 3

    rotate(&mut a, &mut b, &mut c);

    println!("{}, {}, {}", a, b, c);
    // 2, 3, 1
}

---

这会产生 7 条

movl

指令（Rust 1.35.0、Release、x86_64、Linux）

playground::rotate:
    movl    (%rdi), %eax
    movl    (%rsi), %ecx
    movl    %ecx, (%rdi)
    movl    %eax, (%rsi)
    movl    (%rdx), %ecx
    movl    %ecx, (%rsi)
    movl    %eax, (%rdx)
    retq

相对于原来的 6

movl

说明：

playground::rotate_original:
    movl    (%rdx), %eax
    movl    (%rsi), %ecx
    movl    %ecx, (%rdx)
    movl    (%rdi), %ecx
    movl    %ecx, (%rsi)
    movl    %eax, (%rdi)
    retq

我可以为了纯粹安全的代码而放弃这条指令，这也更容易推理。

---

在“真实”代码中，我会利用所有变量都是相同类型并且存在

slice::rotate_left

和

slice::rotate_right

的事实：

fn main() {
    let mut vals = [1, 2, 3];

    let [a, b, c] = &vals;
    println!("{}, {}, {}", a, b, c);
    // 1, 2, 3

    vals.rotate_left(1);

    let [a, b, c] = &vals;
    println!("{}, {}, {}", a, b, c);
    // 2, 3, 1
}

Answer 2

更好的 Rust 实现是直接从问题顶部直接实现伪代码：

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    unsafe {
        let t = std::ptr::read(z);
        std::ptr::write(z, std::ptr::read(y));
        std::ptr::write(y, std::ptr::read(x));
        std::ptr::write(x, t);
    }
}

更短、更干净、更直接、更直观。 您不需要

mem::forget

t

，因为

x

拥有它的所有权。