Rust: Add a shift method to Vec

[watzon]

Vec has a pop method which is great for removing and returning the last element in a Vec, however it ends up being complicated if you want to do the same with the first element. I propose adding a shift method to do just that. It could be implemented as follows:

pub fn shift(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            unsafe {
                self.len -= 1;
                Some(ptr::read(self.get_unchecked(0)))
            }
        }
    }

[Aatch]

@iDev0urer the problem is that adding/removing from the front of a vec is an O(n) operation, whereas pop/push are O(1). You're better off using an actual queue if you need operations at both ends.

[watzon]

@Aatch would you be able to give an example? I'm still pretty new to this

[bluss]

Your implementation leaves a moved-from hole at index 0, and it loses the last element of the vec. What's missing is that all remaning elements need to be copied towards the start by 1 step, and that explains why this operation is not efficient on Vec.

[Cobrand]

I think you've missed this and it's probably perfect for your use case.

[masklinn]

What's missing is that all remaning elements need to be copied towards the start by 1 step, and that explains why this operation is not efficient on Vec.

And why a small dance with Vec::remove is probably the right choice, make it clear that this is not an innocuous operation.

[watzon]

@Cobrand thanks! I think that is exactly what I need. Man this language is confusing as hell, but it always has what you need.

[Fedcomp]

.remove requires additional boilerplate, wish it was Option. Surprised there is still no shift method.

[johnkarasev]

just use vec.reverse() and then the standard pop()

[johnkarasev]

Not sure if it is a cheap operation, but it looks like _O(n)_

pub fn reverse(&mut self) {
    let mut i: usize = 0;
    let ln = self.len();
   // For very small types, all the individual reads in the normal
    // path perform poorly.  We can do better, given efficient unaligned
    // load/store, by loading a larger chunk and reversing a register.

    // Ideally LLVM would do this for us, as it knows better than we do
    // whether unaligned reads are efficient (since that changes between
    // different ARM versions, for example) and what the best chunk size
    // would be.  Unfortunately, as of LLVM 4.0 (2017-05) it only unrolls
    // the loop, so we need to do this ourselves.  (Hypothesis: reverse
    // is troublesome because the sides can be aligned differently --
    // will be, when the length is odd -- so there's no way of emitting
    // pre- and postludes to use fully-aligned SIMD in the middle.)

    let fast_unaligned =
        cfg!(any(target_arch = "x86", target_arch = "x86_64"));

    if fast_unaligned && mem::size_of::<T>() == 1 {
        // Use the llvm.bswap intrinsic to reverse u8s in a usize
        let chunk = mem::size_of::<usize>();
        while i + chunk - 1 < ln / 2 {
            unsafe {
                let pa: *mut T = self.get_unchecked_mut(i);
                let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
                let va = ptr::read_unaligned(pa as *mut usize);
                let vb = ptr::read_unaligned(pb as *mut usize);
                ptr::write_unaligned(pa as *mut usize, vb.swap_bytes());
                ptr::write_unaligned(pb as *mut usize, va.swap_bytes());
            }
            i += chunk;
        }
    }

    if fast_unaligned && mem::size_of::<T>() == 2 {
        // Use rotate-by-16 to reverse u16s in a u32
        let chunk = mem::size_of::<u32>() / 2;
        while i + chunk - 1 < ln / 2 {
            unsafe {
                let pa: *mut T = self.get_unchecked_mut(i);
                let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
                let va = ptr::read_unaligned(pa as *mut u32);
                let vb = ptr::read_unaligned(pb as *mut u32);
                ptr::write_unaligned(pa as *mut u32, vb.rotate_left(16));
                ptr::write_unaligned(pb as *mut u32, va.rotate_left(16));
            }
            i += chunk;
        }
    }

    while i < ln / 2 {
        // Unsafe swap to avoid the bounds check in safe swap.
        unsafe {
            let pa: *mut T = self.get_unchecked_mut(i);
            let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
            ptr::swap(pa, pb);
        }
        i += 1;
    }
}`

[Fedcomp]

yeah check if vector size > 0, reverse, pop element. Too much boilerplate isn't it? :)