What's the best way to partial reverse vec

use std::mem;

impl Solution {
    pub fn permutation(s: String) -> Vec<i32> {
        let mut start = 0;
        let mut end = 0;
        let mut search = false;
        let mut res = vec!();
        (0..=s.len()).for_each(|num| res.push( (num+1) as i32));
        for (i, item) in s.chars().enumerate() {
            if item == 'I' {
                if search {
                    end = i;
                    search = false;
                    Self::reverse(&mut res, start, end);
                }   
            }
            if item == 'D' {
                if search { continue;}
                start = i;
                search = true;
            }
        }
        if search {
            Self::reverse(&mut res, start, s.len());
        }
        res  
    }
    
    fn reverse(res: &mut Vec<i32>, mut start: usize, mut end: usize) {
        while end > start {
            let temp = res[start];
            res[start] = res[end];
            res[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

in cpp, we can do void reverse( BidirIt first, BidirIt last );, I tried mem::swap(&mut res[start], &mut res[end]); in my reverse function, it failed on multiple-borrows error. Feel like the code have space to be more idiomatic and succinct, Any suggestions is appreciate it!

    fn reverse(res: &mut Vec<i32>, mut start: usize, mut end: usize) {
        res[start..=end].reverse()
    }

https://doc.rust-lang.org/stable/std/primitive.slice.html#method.reverse

7 Likes

There's a swap method on slices to make that easier: https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.swap

But as Hyeonu said, you want the reverse method.

(And if you're curious how that works, I just made it faster in MIRI says `reverse` is UB, so replace it with something LLVM can vectorize by scottmcm · Pull Request #90821 · rust-lang/rust · GitHub)

7 Likes

Thanks for reply! reverse is the best one in this case. Specifically on my case, If already know index won't overlap and safe to swap, is there any decorator/directive to tell compiler this is a fine case for using mem::swap. Also wondering why nightly swap isn't in stable? it looks quite lego-like utility function to have.

If you're referring to the slice swap method, that's stable all the way since Rust 1.0. It's only const-unstable, meaning that on nightly with #[feature(const_swap)], it becomes a const fn (which is entirely irrelevant for your use case).

swap isn't magic; it's just a function that takes two &muts. And the borrow checker intentionally doesn't let you take &mut slice[start] and &mut slice[end] at the same time, because to be sound that would require proving that start != end, and Rust doesn't want to depend on a integer solver like that for checking.

You might be interested in this section of the nomicon: Splitting Borrows - The Rustonomicon

2 Likes