I was trying to solve a problem of sorting parallel vectors (i.e. vectors that contain an attribute of the same entity for each index). I have multiple vectors and I need to sort them using one of these vectors' values as a key. The common way to do that in Rust is to allocate a vector of tuples, sort it by one of its fields and unzip it back into vectors. The word I don't like here is "allocate". I just want to sort the reference vector in-place and for each element swap perform the same swap in all the other vectors, there is no need to allocate anything.
So I started to look for a solution in other languages and found this article: https://www.lukas-barth.net/blog/cpp23-zip-range-sort-parallel-arrays. In short, the code looks like this:
std::vector<size_t> keys { 1, 4, 3, 0, 2, 8, 6, 5, 7, 9 };
std::vector<char> values {'E', 'O', 'L', 'H', 'L', 'L', 'O', 'W', 'R', 'D'};
auto zip = std::ranges::views::zip(keys, values);
std::ranges::sort(zip, [](const auto & lhs, const auto & rhs) {
return std::get<0>(lhs) < std::get<0>(rhs);
});
It sorts values using keys as reference.
The article states that with this approach "no temporary vectors are created, no objects are (unnecessarily) copied". As I understand it, this code does exactly what I want. Am I correct? And if I am, how would I do this in Rust?
Rust's standard library doesn't provide a facility to sort two vectors at once. For one, it lacks an equivalent to std::ranges::views::zip. More importantly, and unlike C++, Rust's std doesn't include functionality for sorting arbitrary containers with random access, you can only sort contiguous data (a slice). This limitation also extends to the popular external sorting crates1.
However, Rust generics are powerful enough to implement this kind of facility. Starting with a "sortable" trait with operations needed for a comparison sort, one can write a sort that equally applies to slices, paired vectors, or any other structure that implements the trait. The downside is that you will need to provide the sorting routine.
First create a trait like this, inspired by golang's sort interface:
trait Sortable {
fn len(&self) -> usize;
fn cmp(&self, a: usize, b: usize) -> Ordering;
fn swap(&mut self, a: usize, b: usize);
}
Now write a sort implementation that assumes nothing about the type except that it satisfies Sortable:
// Simple quicksort for demonstration purposes - in production you'd use a better
// implementation, possibly copied from std or from a crate that specializes
// in sorting.
fn quicksort(data: &mut (impl Sortable + ?Sized)) {
quicksort_rec(data, 0, data.len());
fn quicksort_rec(data: &mut (impl Sortable + ?Sized), from: usize, to: usize) {
if to - from <= 1 {
return;
}
let pivot = partition(data, from, to);
quicksort_rec(data, from, pivot);
quicksort_rec(data, pivot + 1, to);
}
fn partition(data: &mut (impl Sortable + ?Sized), from: usize, to: usize) -> usize {
let pivot = to - 1;
let mut i = from;
for j in from..pivot {
if data.cmp(j, pivot).is_le() {
data.swap(i, j);
i += 1;
}
}
data.swap(i, pivot);
i
}
}
This is how to apply it to sorting slices:
impl<T: Ord> Sortable for [T] {
fn len(&self) -> usize {
self.len()
}
fn cmp(&self, a: usize, b: usize) -> Ordering {
self[a].cmp(&self[b])
}
fn swap(&mut self, a: usize, b: usize) {
self.swap(a, b)
}
}
fn main() {
let mut numbers = vec![64, 34, 25, 12, 22, 11, 90];
quicksort(numbers.as_mut_slice());
println!("Sorted array: {numbers:?}");
}
With the trait and sort working, we can proceed to sorting zipped vectors. All we need to do is write a wrapper that implements Sortable:
// this struct doesn't allocate, it just holds two references
struct Zip<'a, K, V> {
keys: &'a mut [K],
values: &'a mut [V],
}
impl<'a, K, V> Zip<'a, K, V> {
fn new(keys: &'a mut [K], values: &'a mut [V]) -> Self {
Zip { keys, values }
}
}
impl<K: Ord, V> Sortable for Zip<'_, K, V> {
fn len(&self) -> usize {
self.keys.len()
}
fn cmp(&self, a: usize, b: usize) -> Ordering {
self.keys[a].cmp(&self.keys[b])
}
fn swap(&mut self, a: usize, b: usize) {
self.keys.swap(a, b);
self.values.swap(a, b);
}
}
This is used as you'd expect:
fn main() {
let mut keys = vec![1, 4, 3, 0, 2, 8, 6, 5, 7, 9];
let mut values = vec!['E', 'O', 'L', 'H', 'L', 'L', 'O', 'W', 'R', 'D'];
quicksort(&mut Zip::new(&mut keys, &mut values));
println!("sorted keys: {keys:?}");
println!("sorted values: {values:?}");
}
1 The index-sort crate supports sorting of random-access containers like shown in this answer, and implements several sort algorithms. It appears unmaintained, though, so use at your own risk. Using index-sort the parallel sorting boils down to just providing Zip, and looks like this. (The code won't compile on the playground because the playground only includes popular crates, but you can copy it to your own project and cargo add index-sort.)