Slices, vectors, arrays, handled generically

I'm a long-time C++ programmer and am beginning to explore Rust. In order to develop some Rust skills I'm implementing standard, well-known algorithms and trying to do it in a Rust-idiomatic way. Presently, it's insertion sort.

In C++, I could write a generic insertion sort easily enough:

template<std::random_access_iterator RandomIterator>
void sort(RandomIterator first, RandomIterator last)
{
    // do magic
}

However, this doesn't seem to translate well into Rust, where (as far as I can tell) iterators are limited to purely sequential access.

I've also tried to find a trait shared by slices, vectors, and arrays to let me take a parameter of mut &T<U>, where T would be the type of the container and U the type of its contained element. So far, I'm not finding anything.

I've found a number of solutions of dubious quality, most of which seem to be awfully baroque for such a simple problem in generics. So, I've come here to ask for some help: where ought I look for a Rust way to accept generic random-access containers as mut & parameters?

Many thanks for any help y'all can give. I appreciate it. :slight_smile:

1 Like

The Rust analogue of a C++ iterator for random access use is a slice reference, i.e. &mut [T]. Any collection that is contiguous in memory can be borrowed as a slice.

4 Likes

Rust doesn't have higher-kinded types (HKT) like &T<U>. However, vectors (Vec<T>) and arrays ([T; N]) both coerce into slices [T].

For this particular problem, I would probably look at using slices and their methods directly.

(The closest thing I can think of to a "random access trait" are the Index traits, but I don't really think that's a good fit.)

3 Likes

Vec<T> implements DerefMut with Target = [T], and array types [T; N] have an unsized coercion to [T]. Consequently, &mut Vec<T> and &mut [T; N] references coerce to &mut [T] implicitly, and if you have a function that accepts a &mut [T], it can accept all three types of references (Rust Playground):

use std::cmp::Ord;

fn sort<T: Ord>(slice: &mut [T]) {
    slice.sort();
}

fn main() {
    let slice: &mut [i32] = &mut [5, 4, 3, 2, 1];
    let mut vec: Vec<i32> = vec![5, 4, 3, 2, 1];
    let mut array: [i32; 5] = [5, 4, 3, 2, 1];
    sort(slice);
    sort(&mut vec);
    sort(&mut array);
    println!("{slice:?}");
    println!("{vec:?}");
    println!("{array:?}");
}
5 Likes

@LegionMammal978 already answered how to do it with slices, but if you really want it to be generic and support data structures that are not stored in contiguous chunks of memory (which is a limitation of slices as noted by @kpreid) here is an example on how you could do it:

1 Like

Thank you: the lack of higher-kinded types is exactly the sort of thing I needed to know about (even more than the implicit conversion into slices). It's going to require me to change some of how I think about generics, since my current C++ style leans heavily on them, but I'm looking forward to getting a handle on how Rust does things. :slight_smile:

For a detour into an intermediate subject, Rust has an unstable feature called Generic Associated Types (GATs). The most common example of a GAT is a lifetime GAT for something like a lending iterator as discussed in that blog post; those can be implemented with a helper trait on stable Rust today. Another example is the concept of a type family, like the PointerFamily in the post. Those need the GAT feature.

I bring it up because type families can model HKTs as outlined in this series [1]:

Again, not stable and probably not anything to dive into before your feet are wet, but maybe something you'd be interested in circling back to later.


  1. (Associated Type Constructors is a different phrase for GATs.) ↩ī¸Ž

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.