Generics, Traits and Lifetimes · about 40 min

Generics: Code for Many Types

Why this matters

You have written the same function twice for different types, or wished you could: a largest for i32 and another for f64, a pair of integers and a pair of strings. Generics let you write the code once with a type parameter and use it with many types. You have been using them all along: Vec<T>, Option<T>, Result<T, E> and HashMap<K, V> are generic types. This lesson shows how to write your own and what the compiler does with them.

Generic functions

Here is a function that only works for i32:

fn largest_i32(items: &[i32]) -> i32 {
    let mut best = items[0];
    for &x in items {
        if x > best {
            best = x;
        }
    }
    best
}

fn main() {
    println!("{}", largest_i32(&[3, 9, 4]));
}

The body would work for floats or chars too. Make the type a parameter:

fn largest<T: PartialOrd + Copy>(items: &[T]) -> T {
    let mut best = items[0];
    for &x in items {
        if x > best {
            best = x;
        }
    }
    best
}

fn main() {
    println!("{}", largest(&[3, 9, 4]));
    println!("{}", largest(&[0.5, -2.0, 1.25]));
    println!("{}", largest(&['r', 'u', 's', 't']));
}

9
1.25
u

<T> after the function name declares a type parameter. T is a placeholder for whatever type the caller uses; the name is conventional for "some type".
T: PartialOrd + Copy is a trait bound: T may be any type that can be compared with > (PartialOrd) and copied (Copy). Traits are the subject of the next lessons; for now, a bound lists what the function needs from the type.
The caller does not say which T; the compiler infers it from the argument.

Why are the bounds required? Without them:

fn largest<T>(items: &[T]) -> T {
    let mut best = items[0];
    for &x in items {
        if x > best {
            best = x;
        }
    }
    best
}

fn main() {
    println!("{}", largest(&[1, 2]));
}

error[E0369]: binary operation `>` cannot be applied to type `T`
 --> main.rs:4:14
  |
4 |         if x > best {
  |            - ^ ---- T
  |            |
  |            T
  |
help: consider restricting type parameter `T` with trait `PartialOrd`
  |
1 | fn largest<T: std::cmp::PartialOrd>(items: &[T]) -> T {
  |             ++++++++++++++++++++++

The compiler checks a generic function once, for all possible T, using only what the bounds promise. An arbitrary T might not support > (what does "greater" mean for a file handle?) and might not be copyable (a String would have to be moved out of the slice). The help even suggests the bound. This is unlike C++ templates, which are checked only when instantiated: in Rust, a generic function that compiles works for every type that satisfies its bounds.

Generic structs and enums

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

#[derive(Debug)]
struct Labeled<L, V> {
    label: L,
    value: V,
}

fn main() {
    let a = Point { x: 1, y: 2 };
    let b = Point { x: 1.5, y: -0.5 };
    let c = Labeled { label: "count", value: 42u8 };
    let d = Labeled { label: 'k', value: vec![1, 2] };
    println!("{:?} {:?}", a, b);
    println!("{:?} {:?}", c, d);
}

Point { x: 1, y: 2 } Point { x: 1.5, y: -0.5 }
Labeled { label: "count", value: 42 } Labeled { label: 'k', value: [1, 2] }

Point<T> has both fields of the same type T, so Point { x: 1, y: 2.5 } is a type error. Labeled<L, V> has two independent parameters. The standard library's enums are defined the same way:

enum Option<T> { None, Some(T) }
enum Result<T, E> { Ok(T), Err(E) }

Methods on generic types

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

impl<T> Point<T> {
    fn new(x: T, y: T) -> Self {
        Point { x, y }
    }

    fn x(&self) -> &T {
        &self.x
    }
}

impl Point<f64> {
    fn distance_from_origin(&self) -> f64 {
        (self.x * self.x + self.y * self.y).sqrt()
    }
}

fn main() {
    let p = Point::new(3.0, 4.0);
    println!("x = {}, distance = {}", p.x(), p.distance_from_origin());
    let q = Point::new("a", "b");
    println!("{}", q.x());
}

x = 3, distance = 5
a

impl<T> Point<T> declares T and implements methods for every Point<T>.
impl Point<f64> implements methods only for that concrete type: q.distance_from_origin() would not compile for a Point<&str>.

Monomorphization: what the compiler does

Generic code costs nothing at run time. For every concrete type a generic item is used with, the compiler generates a specialized copy:

 your code:                     what gets compiled:

 largest::<T>(&[T]) -> T        largest_i32(&[i32]) -> i32
 called with i32, f64, char     largest_f64(&[f64]) -> f64
                                largest_char(&[char]) -> char

Each copy is optimized for its type, exactly as if you had written it by hand. This is a zero-cost abstraction: you get the convenience of generic code with the performance of specialized code. The price is paid at compile time and in binary size (one copy per type). Lesson 3 contrasts this with dynamic dispatch, which keeps one copy and decides at run time.

Specifying the type explicitly

Usually inference figures out T. When it cannot, name it with the turbofish ::<>:

fn main() {
    let n = "42".parse::<u64>().unwrap();
    let v = Vec::<i32>::with_capacity(10);
    let parsed: Vec<i32> = "1 2 3".split(' ').map(|s| s.parse().unwrap()).collect();
    let also = "1 2 3".split(' ').map(|s| s.parse::<i32>().unwrap()).collect::<Vec<_>>();
    println!("{n} {} {:?} {:?}", v.capacity(), parsed, also);
}

42 10 [1, 2, 3] [1, 2, 3]

_ in Vec<_> means "infer this part".

Common mistakes

Missing bounds: E0369 (binary operation cannot be applied to type T), E0508/E0507 (cannot move out), E0277 (T doesn't implement Display). Add the trait the body uses to the bounds.
Mixing types in one parameter: Point { x: 1, y: 2.0 } with Point<T> is E0308. Use two parameters if the fields may differ.
Over-generalizing: generics make signatures harder to read. Write the concrete version first; generalize when you actually need a second type.
Forgetting <T> after impl: impl Point<T> without impl<T> makes the compiler look for a concrete type named T (E0412 cannot find type T).

Recap

fn f<T: Bounds>(x: T) declares a type parameter; bounds say what the body may do with T.
Generic structs and enums: struct Point<T>, enum Option<T>; methods via impl<T> Point<T>.
impl Point<f64> adds methods for one concrete instantiation only.
Generics are checked once against their bounds and compiled by monomorphization: zero run-time cost.
The turbofish ::<T> names a type parameter when inference cannot.

Going further: read the Rust Book chapter 10.1, then try writing fn count_matching<T: PartialEq>(items: &[T], target: &T) -> usize and use it with strings and numbers.

Exercises

Exercise 1 · write code

A generic Pair

Define struct Pair<T> { a: T, b: T } with #[derive(Debug)] and methods in impl<T> Pair<T>:

fn new(a: T, b: T) -> Self
fn swap(self) -> Pair<T> returning a pair with the two values exchanged
fn first(&self) -> &T

The given main uses it with integers and Strings and prints:

Pair { a: 2, b: 1 }
first: hello

File: main.rs

Starting point

fn main() {
    let p = Pair::new(1, 2).swap();
    println!("{:?}", p);
    let q = Pair::new(String::from("hello"), String::from("world"));
    println!("first: {}", q.first());
}

Example

expected output

Pair { a: 2, b: 1 }
first: hello

Hint 1

impl<T> Pair<T> { ... }: the <T> after impl declares the type parameter used in Pair<T>.

Hint 2

swap(self) can move both fields: Pair { a: self.b, b: self.a }.

Reference solution

#[derive(Debug)]
struct Pair<T> {
    a: T,
    b: T,
}

impl<T> Pair<T> {
    fn new(a: T, b: T) -> Self {
        Pair { a, b }
    }

    fn swap(self) -> Pair<T> {
        Pair { a: self.b, b: self.a }
    }

    fn first(&self) -> &T {
        &self.a
    }
}

fn main() {
    let p = Pair::new(1, 2).swap();
    println!("{:?}", p);
    let q = Pair::new(String::from("hello"), String::from("world"));
    println!("first: {}", q.first());
}

Exercise 2 · write code

A generic largest()

Write fn largest<T: PartialOrd + Copy>(items: &[T]) -> Option<T> returning the largest element, or None for an empty slice. The given main prints:

Some(42)
Some('z')
Some(2.5)
None

File: main.rs

Starting point

fn largest(items: &[i32]) -> Option<i32> {
    let mut best = *items.first()?;
    for &x in items {
        if x > best {
            best = x;
        }
    }
    Some(best)
}

fn main() {
    println!("{:?}", largest(&[3, 42, 7]));
    println!("{:?}", largest(&['a', 'z', 'q']));
    println!("{:?}", largest(&[1.5, 2.5, -3.0]));
    let empty: [u8; 0] = [];
    println!("{:?}", largest(&empty));
}

Example

expected output

Some(42)
Some('z')
Some(2.5)
None

Hint 1

Only the signature needs to change: replace i32 by a type parameter T.

Hint 2

> needs T: PartialOrd; copying values out of the slice (*items.first()?, for &x) needs T: Copy.

Reference solution

fn largest<T: PartialOrd + Copy>(items: &[T]) -> Option<T> {
    let mut best = *items.first()?;
    for &x in items {
        if x > best {
            best = x;
        }
    }
    Some(best)
}

fn main() {
    println!("{:?}", largest(&[3, 42, 7]));
    println!("{:?}", largest(&['a', 'z', 'q']));
    println!("{:?}", largest(&[1.5, 2.5, -3.0]));
    let empty: [u8; 0] = [];
    println!("{:?}", largest(&empty));
}

Exercise 3 · quiz

What does the compiler generate?

A program calls a generic function fn show<T: Display>(x: T) with an i32, a &str and an f64. How many machine-code versions of show end up in the executable?

One, which checks the type of x at run time
Three: one specialized copy per concrete type used (monomorphization)
None: generic functions are interpreted
One, which receives a pointer and a type tag

Answer

Three: one specialized copy per concrete type used (monomorphization)

Rust compiles generics by monomorphization: for each concrete type a generic function is used with, the compiler generates a specialized copy, as if you had written show_i32, show_str and show_f64 by hand. That makes generic code exactly as fast as hand-written code (no run-time type checks), at the cost of larger binaries and longer compile times. Lesson 3 shows the alternative, dyn Trait.