How would you write a generic reverse function?


#1

As an exercise in learning Rust I want to implement a generic reverse function which takes a vector or an array as input and returns a new vector or an array with the input elements in the reverse order. The input vector remains untouched.

In other words a function with the following signature…

fn reverse(input: &[T]) -> &[T];

But it seems this is not possible since you cannot return slices from a function. So the next best thing which I can think of is…

fn reverse(input: Box<[T]>) -> Box<[T]>;

But now this will not work with arrays and even if it could it will lead to an unnecessary heap allocation.

How would you implement such a reverse function?

Note: Since I have already specified that the input vector/array remains undisturbed we will have to assume T is cloneable (copyable?).


#2

You can take a slice, and return a Vec<T>. I’d say the implementation would be input.iter().rev().cloned().collect()


#3

Oli thanks for reminding me about iterators and showing your awesome implementation. What if reverse took an iterator instead of a slice and returned another iterator? If I understand correctly I now want to re-implement rev()! Let me give this a try.


#4

rev is kind of a bad example because it delegates almost all the work to the DoubleEndedIterator trait implementation, which means that the logic for rev is effectively spread throughout std — every iterator type defines for itself how to reverse.

If you just want to write a loop, the proper signature would be fn reverse<T>(input: Vec<T>) -> Vec<T> or fn reverse<T>(input: &[T]) -> Vec<T>; Box<[T]> is used very little in Rust (essentially because you have to create the entire thing at once. You can’t push to a Box<[T]>.)

If you want to write a loop reversing a vector in place, you’ll find that the borrow checker makes this impossible without some help. A swap operation needs to be atomic to avoid any possibility of leaving the vector in a broken state; luckily mem::swap does precisely that. Then the problem becomes getting simultaneous exclusive access to two different array indices — slice::swap or slice::split_at_mut are needed here.


#5

Thanks sorear!


#6

You can use both next() and next_back() on the iterator to swap fronts and backs in a loop.