Generics in Rust

Generics let you write one piece of code that works for many types. Instead of writing largest_i32, largest_char and largest_f64, you write one largest<T> and let the compiler fill in T. You have already used generic types in every lesson so far: Vec<T>, Option<T>, Result<T, E> and HashMap<K, V> are all ordinary generic types from the standard library, with nothing magic about them. This lesson shows you how to write your own.

Rust's generics are worth understanding in detail because they behave differently from Java's and Python's. Rust checks generic code once, at its definition, against the trait bounds you declare, and then generates a separate, fully specialised copy of the code for each concrete type you use. That process, called monomorphisation, is why generic Rust code runs as fast as hand-written code for each type. By the end of this lesson you will be able to write generic functions, structs, enums and methods, add the bounds the compiler asks for, read the errors that generic code produces, use const generics for arrays of any length, and explain in an interview what "zero-cost generics" means and what it costs in compile time and binary size.

The problem generics solve

Here are two functions that find the largest item in a slice. They differ only in the type:

fn largest_i32(list: &[i32]) -> i32 {
    let mut largest = list[0];
    for &item in list {
        if item > largest {
            largest = item;
        }
    }
    largest
}

fn largest_char(list: &[char]) -> char {
    let mut largest = list[0];
    for &item in list {
        if item > largest {
            largest = item;
        }
    }
    largest
}

fn main() {
    println!("{}", largest_i32(&[34, 50, 25, 100, 65]));
    println!("{}", largest_char(&['y', 'm', 'a', 'q']));
}

Output:

100
y

The bodies are identical, character for character. If you later fix a bug in one, you have to remember to fix the other. Python would solve this with duck typing: one function, and any type that supports > will work at run time. Java would solve it with a generic method <T extends Comparable<T>> T largest(List<T> list). Rust's answer looks like Java's on the surface, but works very differently underneath, as you will see.

Generic functions

A generic function declares one or more type parameters in angle brackets after its name. By convention a type parameter is a single capital letter, usually T for "type". Inside the function, T stands for "some type the caller chooses".

A first attempt at a generic largest does not compile:

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

fn main() {
    println!("{}", largest(&[34, 50, 25, 100, 65]));
}

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

Reading the compiler error: E0369, an operator on an unbounded T

E0369 says that the binary operator > cannot be applied to &T. This is the single most important idea in Rust generics, so it is worth reading slowly.

Inside largest<T>, the compiler knows nothing about T. It could be a number, a String, a file handle or a struct with no ordering at all. Rust refuses to assume anything, so with a bare T you can only do things that work for every possible type: move it, borrow it, store it, return it. Comparing with > needs the PartialOrd trait (a trait is a named set of behaviour that types can implement; lesson 12 covers traits fully). The help line suggests the fix: restrict T to types that implement PartialOrd.

The restriction is called a trait bound, written T: PartialOrd:

fn largest<T: PartialOrd>(list: &[T]) -> &T {
    let mut largest = &list[0];
    for item in list {
        if item > largest {
            largest = item;
        }
    }
    largest
}

fn main() {
    let numbers = [34, 50, 25, 100, 65];
    let letters = ['y', 'm', 'a', 'q'];
    let words = [
        String::from("kiwi"),
        String::from("mango"),
        String::from("apple"),
    ];
    let prices = [99.5, 12.25, 149.0];

    println!("largest number: {}", largest(&numbers));
    println!("largest letter: {}", largest(&letters));
    println!("largest word:   {}", largest(&words));
    println!("largest price:  {}", largest(&prices));
}

Output:

largest number: 100
largest letter: y
largest word:   mango
largest price:  149

Step by step:

1. fn largest<T: PartialOrd> declares a type parameter T and promises that whatever type is used will implement PartialOrd, the trait behind <, >, <= and >=.
2. The parameter list: &[T] is a slice of T, and the return type &T is a reference to one element. Returning a reference means the function works for types that cannot be copied, such as String, and never clones anything.
3. At each call, the compiler infers T from the argument: i32 for numbers, char for letters, String for words, f64 for prices. You do not write the type at the call site.
4. Strings compare in dictionary order, byte by byte, so "mango" beats "kiwi" and "apple". The float 149.0 prints as 149 because {} drops a trailing .0 for f64.

The function panics on an empty slice because &list[0] is out of bounds. Exercise 6 fixes that by returning Option<&T>.

Generic structs

A struct can have type parameters too. The parameters are declared after the struct name and then used as field types:

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

#[derive(Debug)]
struct Labelled<T, U> {
    label: T,
    value: U,
}

fn main() {
    let integer = Point { x: 5, y: 10 };
    let float = Point { x: 1.5, y: -4.0 };
    let explicit: Point<u8> = Point { x: 255, y: 0 };
    println!("{integer:?} {float:?} {explicit:?}");
    println!(
        "integer.x + explicit.y = {}",
        integer.x + i32::from(explicit.y)
    );
    println!("float sum = {}", float.x + float.y);

    let score = Labelled {
        label: "maths",
        value: 92,
    };
    let ratio = Labelled {
        label: 'r',
        value: 0.75,
    };
    println!(
        "{} = {}, {} = {}",
        score.label, score.value, ratio.label, ratio.value
    );
}

Output:

Point { x: 5, y: 10 } Point { x: 1.5, y: -4.0 } Point { x: 255, y: 0 }
integer.x + explicit.y = 5
float sum = -2.5
maths = 92, r = 0.75

• Point<T> has one type parameter, used for both fields, so x and y must have the same type.
• Point { x: 5, y: 10 } is a Point<i32> (integer literals default to i32), and Point { x: 1.5, y: -4.0 } is a Point<f64>.
• let explicit: Point<u8> = ... names the type in full. You need this only when inference has nothing to go on or picks the wrong type.
• Labelled<T, U> has two independent parameters. score is a Labelled<&str, i32>, and ratio is a Labelled<char, f64>.

Point<i32> and Point<f64> are different types. You cannot put one in a Vec<Point<i32>>, and you cannot add integer.x to float.x without a conversion, just as you cannot add an i32 to an f64. That is why the program converts explicit.y from u8 with i32::from before adding.

Reading the compiler error: E0308, one T cannot be two types

Because Point<T> uses one T for both fields, both fields must agree. This does not compile:

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

fn main() {
    let p = Point { x: 5, y: 4.0 };
    println!("{p:?}");
}

error[E0308]: mismatched types
 --> point_mismatch_err.rs:8:30
  |
8 |     let p = Point { x: 5, y: 4.0 };
  |                              ^^^ expected integer, found floating-point number

The compiler sees x: 5 and decides T is some integer type. Then it sees y: 4.0, a floating-point number, which cannot also be that integer type. Read the message as "I had already decided what T is, and this does not match". There are two fixes, and the right one depends on what you mean:

• If the two fields really can differ, give them separate parameters: struct Point<T, U> { x: T, y: U }.
• If they must be the same, make the values agree: Point { x: 5.0, y: 4.0 }.

Generic enums

Enums take type parameters in exactly the same way. You have already used the two most important generic enums in the standard library. Their definitions are short:

enum Option<T> {
    Some(T),
    None,
}

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

Option<T> is generic over the type of the value that may be missing. Result<T, E> is generic over two types: the success value and the error. Neither knows or cares what those types are, which is exactly why one definition serves the whole language. Here is a small generic enum of your own that holds one of two possible types:

#[derive(Debug)]
enum Either<L, R> {
    Left(L),
    Right(R),
}

fn parse_or_keep(text: &str) -> Either<i64, &str> {
    match text.parse::<i64>() {
        Ok(n) => Either::Left(n),
        Err(_) => Either::Right(text),
    }
}

fn main() {
    for input in ["42", "forty-two", "-7"] {
        match parse_or_keep(input) {
            Either::Left(n) => println!("number {n}, doubled {}", n * 2),
            Either::Right(s) => println!("text {s:?}, {} bytes", s.len()),
        }
    }

    let maybe: Option<Either<i64, &str>> = Some(parse_or_keep("5"));
    println!("{maybe:?}");
}

Output:

number 42, doubled 84
text "forty-two", 9 bytes
number -7, doubled -14
Some(Left(5))

parse_or_keep returns Either<i64, &str>: either the parsed number or the original text. match handles both variants, and each arm sees the right type, so n * 2 is integer arithmetic and s.len() is a string method. The last line nests one generic type in another: Option<Either<i64, &str>>. There is no limit to how generic types compose.

Generic methods and impl blocks

To write methods for a generic struct, you declare the type parameter on the impl block as well: impl<T> Point<T>. The <T> after impl introduces the parameter; the <T> after Point uses it. Read it as "for any type T, here are methods for Point<T>".

#[derive(Debug, Clone, Copy)]
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
    }

    fn swap(self) -> Point<T> {
        Point {
            x: self.y,
            y: self.x,
        }
    }
}

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

impl<T> Point<T> {
    fn mixup<U>(self, other: Point<U>) -> (T, U) {
        (self.x, other.y)
    }
}

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').swap();
    println!("swapped: {q:?}");

    let (first, second) = Point::new(1, 2).mixup(Point::new("left", "right"));
    println!("mixup: {first} and {second}");
}

Output:

x = 3, distance = 5
swapped: Point { x: 'b', y: 'a' }
mixup: 1 and right

This example shows three different things:

1. Methods for every T. impl<T> Point<T> defines new, x and swap for every possible Point. They only move or borrow the fields, which works for any type, so no bound is needed.
2. Methods for one concrete type. impl Point<f64> has no <T> after impl, because it is not generic. distance_from_origin exists only on Point<f64>, because it needs multiplication and sqrt, which are f64 operations. For the point (3, 4), the distance is the square root of 9 + 16 = 25, which is 5.
3. Methods with their own type parameters. mixup<U> declares a second parameter U that belongs to the method alone. It takes self as a Point<T> and other as a Point<U>, so it can combine a Point<i32> with a Point<&str>. The result (1, "right") takes x from the first point and y from the second.

impl<T> Point<T>       ->  Point<i32>, Point<f64>, Point<char> ... all
impl Point<f64>        ->  Point<f64> only
fn mixup<U>(...)       ->  T fixed by self, U chosen at each call

Reading the compiler error: E0599, a method that exists only for another type

A method defined in impl Point<f64> is not available on Point<i32>. This does not compile:

struct Point<T> {
    x: T,
    y: T,
}

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

fn main() {
    let p = Point { x: 3, y: 4 };
    println!("{}", p.distance_from_origin());
}

error[E0599]: no method named `distance_from_origin` found for struct `Point<{integer}>` in the current scope
  --> method_missing_err.rs:14:22
   |
 1 | struct Point<T> {
   | --------------- method `distance_from_origin` not found for this struct
...
14 |     println!("{}", p.distance_from_origin());
   |                      ^^^^^^^^^^^^^^^^^^^^ method not found in `Point<{integer}>`
   |
   = note: the method was found for `Point<f64>`

E0599 means "no method with this name on this type". The type in the message is Point<{integer}>: the compiler has decided the fields are some integer type but has not picked which one yet. The note is the useful line: the method was found for Point<f64>. The fix is either to build the point with floats (Point { x: 3.0, y: 4.0 }), or, if the method should work for many numeric types, to move it into a generic impl with the bounds it needs, which lesson 12 shows how to write.

Type inference and the turbofish

Most of the time the compiler works out the type parameters from the arguments and from how the result is used. Sometimes there is not enough information, and you have to say which type you mean. You can do that in two places: on the variable, or on the function with the ::<> syntax, nicknamed the turbofish because ::<> looks a little like a fish.

fn main() {
    let a = "42".parse::<i32>().unwrap();
    let b: u8 = "200".parse().unwrap();
    let evens = (1..=10).filter(|n| n % 2 == 0).collect::<Vec<i32>>();
    let squares: Vec<_> = evens.iter().map(|n| n * n).collect();
    let empty = Vec::<String>::new();
    let size = std::mem::size_of::<(u8, u32)>();

    println!("{a} {b} {evens:?} {squares:?} {} {size}", empty.len());
}

Output:

42 200 [2, 4, 6, 8, 10] [4, 16, 36, 64, 100] 0 8

size_of::<(u8, u32)>() is 8: a u32 needs 4-byte alignment, so the tuple is one byte for the u8, three bytes of padding and four for the u32.

Reading the compiler error: E0284, type annotations needed

parse is generic over its output type, and nothing in this program says which type to produce. This does not compile:

fn main() {
    let n = "42".parse().unwrap();
    println!("{n}");
}

error[E0284]: type annotations needed
 --> infer_err.rs:2:9
  |
2 |     let n = "42".parse().unwrap();
  |         ^        ----- type must be known at this point
  |
  = note: cannot satisfy `<_ as FromStr>::Err == _`
  = note: the type must also implement `FromStr`
help: consider giving `n` an explicit type
  |
2 |     let n: /* Type */ = "42".parse().unwrap();
  |          ++++++++++++

"42" could be parsed as an i32, a u64, an f64 or an IP address. Printing n with {} does not narrow it down, because all of those implement Display. The help line suggests annotating n. Either let n: i32 = ... or "42".parse::<i32>() fixes it. You will see this error with parse, collect, into and Default::default(), which are all generic over their return type. Depending on the expression, the code may be E0282 or E0284, but the message, "type annotations needed", and the fix are the same.

Monomorphisation: why generics cost nothing at run time

Now the part that interviewers like most. What does the compiler actually do with largest<T>?

Rust uses monomorphisation (from Greek, "making into one form"). When you call largest with an i32 slice and with a char slice, the compiler generates two separate, ordinary functions, as if you had written largest_i32 and largest_char by hand. Each copy is compiled and optimised for its exact type: the i32 copy uses integer comparison instructions, the char copy compares Unicode scalar values, and the String copy calls the string comparison code directly.

your source                      what the compiler generates
-----------                      ---------------------------
fn largest<T: PartialOrd>  --+-> fn largest::<i32>(&[i32]) -> &i32
                             +-> fn largest::<char>(&[char]) -> &char
                             +-> fn largest::<String>(&[String]) -> &String
                             +-> fn largest::<f64>(&[f64]) -> &f64

calls: largest(&numbers)  ---->  largest::<i32>(&numbers)   (direct call)

The same happens to generic types. Point<u8> and Point<u64> become two different struct layouts, each exactly as large as its fields need. This program shows the concrete type behind each use:

use std::any::type_name;
use std::mem::size_of;

fn describe<T>(_value: T) -> String {
    format!("{}: size {}", type_name::<T>(), size_of::<T>())
}

struct Pair<T> {
    first: T,
    second: T,
}

fn main() {
    println!("{}", describe(7_u8));
    println!("{}", describe(7_i64));
    println!("{}", describe("seven"));
    println!("{}", describe(Some(7_u16)));

    let small = Pair {
        first: 1_u8,
        second: 2_u8,
    };
    let big = Pair {
        first: 1_u64,
        second: 2_u64,
    };
    println!(
        "Pair<u8> = {} bytes, Pair<u64> = {} bytes, sums {} and {}",
        size_of::<Pair<u8>>(),
        size_of::<Pair<u64>>(),
        small.first + small.second,
        big.first + big.second
    );
}

Output:

u8: size 1
i64: size 8
&str: size 16
core::option::Option<u16>: size 4
Pair<u8> = 2 bytes, Pair<u64> = 16 bytes, sums 3 and 3

describe was instantiated four times, once per type, and each copy knows its own T. std::any::type_name returns a human-readable name for debugging; its exact text is not guaranteed and may change between compiler versions, so never match on it in real code. The sizes confirm there is no hidden overhead: a Pair<u8> is exactly 2 bytes and a Pair<u64> exactly 16. A &str is 16 bytes on a 64-bit machine because it holds a pointer and a length. Option<u16> is 4 bytes: 2 for the value, and 1 for the tag saying whether it is Some or None, rounded up to the 2-byte alignment of u16.

What monomorphisation buys and what it costs

The phrase zero-cost abstraction means exactly the first two rows: using generics costs you nothing at run time compared with writing the specialised code yourself. It does not mean the abstraction is free in every sense; you pay at compile time and in binary size instead.

Compared with Java, Python and C++

When you need the opposite trade-off, one copy of the code that works for many types chosen at run time, Rust offers trait objects (dyn Trait). Lesson 12 compares the two in detail.

Trait bounds: a first look

You have already met one bound, T: PartialOrd. A bound is a promise in both directions: the caller must pass a type that implements the trait, and in return the function body may use what that trait provides. Lesson 12 covers bounds fully; here are the forms you will see most.

use std::fmt::Display;

fn announce<T: Display>(label: &str, value: T) {
    println!("{label}: {value}");
}

fn print_max<T>(a: T, b: T)
where
    T: Display + PartialOrd,
{
    let bigger = if a >= b { a } else { b };
    println!("max = {bigger}");
}

struct Pair<T> {
    a: T,
    b: T,
}

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

impl<T: Display + PartialOrd> Pair<T> {
    fn show_larger(&self) {
        if self.a >= self.b {
            println!("larger is a = {}", self.a);
        } else {
            println!("larger is b = {}", self.b);
        }
    }
}

fn main() {
    announce("temperature", 36.6);
    announce("city", "Pune");
    print_max(17, 42);
    print_max("apple", "banana");
    Pair::new(3, 9).show_larger();
    Pair::new('z', 'k').show_larger();
}

Output:

temperature: 36.6
city: Pune
max = 42
max = banana
larger is b = 9
larger is a = z

• Inline bound: fn announce<T: Display> lets the body format value with {}. Display is the trait behind {}.
• Several bounds are joined with +: T: Display + PartialOrd means "both".
• A where clause moves the bounds after the signature. print_max uses one; it means the same as the inline form, but long lists of bounds stay readable.
• Bounds on an impl block: impl<T: Display + PartialOrd> Pair<T> adds show_larger only for pairs whose type can be printed and compared. Pair::new is in a separate, unbounded impl<T>, so you can still build a Pair of anything; you just cannot call show_larger on it unless its type qualifies. This technique is called conditional methods.

"apple" and "banana" compare in dictionary order, so banana is larger. 'z' comes after 'k', so the second pair's larger value is a.

Reading the compiler error: E0277, a type that does not meet the bound

When a caller passes a type that does not implement the bound, the error appears at the call site. This does not compile:

use std::fmt::Display;

fn announce<T: Display>(label: &str, value: T) {
    println!("{label}: {value}");
}

struct Rupees(u64);

fn main() {
    announce("price", Rupees(499));
}

error[E0277]: `Rupees` doesn't implement `std::fmt::Display`
  --> bound_err.rs:10:23
   |
10 |     announce("price", Rupees(499));
   |     --------          ^^^^^^^^^^^ unsatisfied trait bound
   |     |
   |     required by a bound introduced by this call
   |
help: the trait `std::fmt::Display` is not implemented for `Rupees`
  --> bound_err.rs:7:1
   |
 7 | struct Rupees(u64);
   | ^^^^^^^^^^^^^
note: required by a bound in `announce`
  --> bound_err.rs:3:16
   |
 3 | fn announce<T: Display>(label: &str, value: T) {
   |                ^^^^^^^ required by this bound in `announce`

E0277 is the general "trait bound not satisfied" error, and you will see it constantly. Read it in three parts:

1. The first line names the type and the missing trait: Rupees does not implement Display.
2. "unsatisfied trait bound" points at the argument that brought the type in.
3. The note: required by a bound in announce points at the bound itself, so you can see who demanded the trait.

The fix is never in the generic function. It is either to implement the trait for your type (lesson 6 showed impl fmt::Display for Money), or to pass a value of a type that already implements it, such as rupees.0.

Const generics

Type parameters let code be generic over types. Const generics let code be generic over values, most often the length of an array. A const parameter is declared as const N: usize and can be used wherever a constant is expected, including array types.

Before const generics, you could not write one function that accepted [i32; 3] and [i32; 5], because arrays of different lengths are different types. You had to take a slice instead and lose the length from the type.

fn sum<const N: usize>(values: [i32; N]) -> i32 {
    let mut total = 0;
    for v in values {
        total += v;
    }
    total
}

#[derive(Debug)]
struct Grid<const ROWS: usize, const COLS: usize> {
    cells: [[u8; COLS]; ROWS],
}

impl<const ROWS: usize, const COLS: usize> Grid<ROWS, COLS> {
    fn new() -> Self {
        Grid {
            cells: [[0; COLS]; ROWS],
        }
    }

    fn size(&self) -> (usize, usize) {
        (ROWS, COLS)
    }
}

fn main() {
    println!("{}", sum([1, 2, 3]));
    println!("{}", sum([10, 20, 30, 40, 50]));

    let mut board: Grid<3, 3> = Grid::new();
    board.cells[1][1] = 9;
    println!("{:?} -> {:?}", board.size(), board.cells);
    println!("Grid<2, 4> is {} bytes", std::mem::size_of::<Grid<2, 4>>());
}

Output:

6
150
(3, 3) -> [[0, 0, 0], [0, 9, 0], [0, 0, 0]]
Grid<2, 4> is 8 bytes

• sum<const N: usize> accepts an array of any length. The compiler infers N = 3 for the first call and N = 5 for the second, and monomorphises a copy for each, just as with type parameters. 10 + 20 + 30 + 40 + 50 = 150.
• Grid<const ROWS: usize, const COLS: usize> is a struct whose size is part of its type. [[0; COLS]; ROWS] creates a 3 × 3 array of zeros. Inside the impl, ROWS and COLS are ordinary constants, so size simply returns them.
• Grid<2, 4> holds 2 × 4 = 8 bytes, stored inline with no heap allocation and no length field.

The real benefit is that lengths are checked at compile time. A dot product only makes sense for two vectors of the same length, and saying so in the signature turns a length mismatch into a compile error:

fn dot<const N: usize>(a: [i32; N], b: [i32; N]) -> i32 {
    a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
}

fn main() {
    println!("{}", dot([1, 2, 3], [4, 5, 6]));
    println!("{}", dot([1, 2, 3], [4, 5]));
}

This does not compile because of the second call:

error[E0308]: mismatched types
 --> const_err.rs:7:35
  |
7 |     println!("{}", dot([1, 2, 3], [4, 5]));
  |                    ---            ^^^^^^ expected an array with a size of 3, found one with a size of 2
  |                    |
  |                    arguments to this function are incorrect
  |
note: function defined here
 --> const_err.rs:1:4
  |
1 | fn dot<const N: usize>(a: [i32; N], b: [i32; N]) -> i32 {
  |    ^^^                              -----------

Both arrays share the same N. The first argument fixes N = 3, so the two-element array cannot match. Without the second call the program prints 32, because 1 × 4 + 2 × 5 + 3 × 6 = 4 + 10 + 18 = 32.

Two limits worth knowing on stable Rust 1.99: a const parameter's type must be an integer type, bool or char (not a struct or a &str), and you cannot yet compute a new length from a parameter inside a type, such as returning [i32; N + 1]. The standard library uses const generics so that arrays of every length implement traits like Debug, PartialEq and Hash; older versions of Rust implemented many of these only for lengths up to 32.

Worked example: a generic stack

Let us build a reusable data structure. The task: a stack (last in, first out) that works for any element type, with a printable form for element types that can be displayed, and then use it twice: for browser-style "back" navigation over Strings, and for checking whether brackets are balanced, over chars.

Design decisions first:

1. Stack<T> wraps a Vec<T>, which already provides push and pop at the end in O(1) amortised time. The struct definition has no bounds.
2. push, pop, peek, len and is_empty work for every T, so they go in impl<T> Stack<T>.
3. pop returns Option<T> (ownership of the removed item moves to the caller) and peek returns Option<&T> (only a borrow), because an empty stack has nothing to give.
4. render needs to turn each item into text, so it lives in a separate impl<T: Display> Stack<T>.

use std::fmt::Display;

#[derive(Debug, Default)]
struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn len(&self) -> usize {
        self.items.len()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
}

impl<T: Display> Stack<T> {
    fn render(&self) -> String {
        let parts: Vec<String> = self.items.iter().map(|item| item.to_string()).collect();
        format!("[{}] <- top", parts.join(", "))
    }
}

fn balanced(text: &str) -> bool {
    let mut open: Stack<char> = Stack::new();
    for c in text.chars() {
        match c {
            '(' | '[' | '{' => open.push(c),
            ')' | ']' | '}' => {
                let expected = match c {
                    ')' => '(',
                    ']' => '[',
                    _ => '{',
                };
                if open.pop() != Some(expected) {
                    return false;
                }
            }
            _ => {}
        }
    }
    open.is_empty()
}

fn main() {
    let mut pages: Stack<String> = Stack::new();
    pages.push(String::from("home"));
    pages.push(String::from("search"));
    pages.push(String::from("product"));
    println!("{} (len {})", pages.render(), pages.len());
    println!("back from {:?}", pages.pop());
    println!("now on {:?}", pages.peek());

    let mut numbers = Stack::new();
    for n in [3, 1, 4] {
        numbers.push(n);
    }
    println!("{}", numbers.render());

    for s in ["(a[b]{c})", "(]", "((("] {
        println!("{s:<10} balanced: {}", balanced(s));
    }
}

Output:

[home, search, product] <- top (len 3)
back from Some("product")
now on Some("search")
[3, 1, 4] <- top
(a[b]{c})  balanced: true
(]         balanced: false
(((        balanced: false

Tracing the bracket checker on "(]":

For "(((", every character is pushed and nothing is popped, so the stack is not empty at the end and the result is false. For "(a[b]{c})", every closer matches the most recent opener, letters are ignored, and the stack ends empty.

Points worth noticing:

• Stack::new() for numbers has no annotation. The compiler infers Stack<i32> from the later numbers.push(n). For pages and open the annotation is there for readability.
• open.pop() != Some(expected) compares two Option<char> values directly, because Option<T> implements PartialEq whenever T does.
• The program uses Stack<String>, Stack<i32> and Stack<char>, so three copies of the methods are generated, but only for the methods actually called.
• #[derive(Debug, Default)] on a generic struct derives Debug for Stack<T> only when T: Debug, and Default only when T: Default. Derives add the bounds for you.

Idioms and pitfalls

Exercises

Exercise 1: swap a pair

Write swap_pair that takes a tuple of any two types (T, U) and returns (U, T). Call it with an integer and a string, a String and an f32, and a bool and a char.

fn swap_pair<T, U>(pair: (T, U)) -> (U, T) {
    let (first, second) = pair;
    (second, first)
}

fn main() {
    println!("{:?}", swap_pair((1, "one")));
    println!("{:?}", swap_pair((String::from("gst"), 0.18_f32)));
    println!("{:?}", swap_pair((true, 'x')));
}

("one", 1)
(0.18, "gst")
('x', true)

Exercise 2: count matches

Write count_matching that counts how many items in a slice equal a target. It should work for integers, string slices and Strings.

fn count_matching<T: PartialEq>(items: &[T], target: &T) -> usize {
    let mut count = 0;
    for item in items {
        if item == target {
            count += 1;
        }
    }
    count
}

fn main() {
    let rolls = [6, 2, 6, 3, 6, 1];
    let words = ["to", "be", "or", "not", "to", "be"];
    let names = vec![
        String::from("Asha"),
        String::from("Ravi"),
        String::from("Asha"),
    ];

    println!("sixes: {}", count_matching(&rolls, &6));
    println!("\"be\": {}", count_matching(&words, &"be"));
    println!("Asha: {}", count_matching(&names, &String::from("Asha")));
}

sixes: 3
"be": 2
Asha: 2

Exercise 3: minimum and maximum together

Write min_max that returns Some((min, max)) for a non-empty slice and None for an empty one, in a single pass. Use T: PartialOrd + Copy.

fn min_max<T: PartialOrd + Copy>(items: &[T]) -> Option<(T, T)> {
    let first = *items.first()?;
    let mut min = first;
    let mut max = first;
    for &item in &items[1..] {
        if item < min {
            min = item;
        }
        if item > max {
            max = item;
        }
    }
    Some((min, max))
}

fn main() {
    println!("{:?}", min_max(&[42, 7, 19, 88, 3]));
    println!("{:?}", min_max(&[2.5, -1.0, 9.75]));
    println!("{:?}", min_max(&['m', 'a', 'z']));
    let empty: [u32; 0] = [];
    println!("{:?}", min_max(&empty));
}

Some((3, 88))
Some((-1.0, 9.75))
Some(('a', 'z'))
None

Exercise 4: a labelled value with a generic method

Write Labelled<T> holding a String label and a value: T. Give it new, a method map<U>(self, f: fn(T) -> U) -> Labelled<U> that transforms the value and keeps the label, and a method rounded that exists only on Labelled<f64>.

#[derive(Debug)]
struct Labelled<T> {
    label: String,
    value: T,
}

impl<T> Labelled<T> {
    fn new(label: &str, value: T) -> Self {
        Labelled {
            label: label.to_string(),
            value,
        }
    }

    fn map<U>(self, f: fn(T) -> U) -> Labelled<U> {
        Labelled {
            label: self.label,
            value: f(self.value),
        }
    }
}

impl Labelled<f64> {
    fn rounded(&self) -> i64 {
        self.value.round() as i64
    }
}

fn double(n: i32) -> f64 {
    f64::from(n) * 2.5
}

fn main() {
    let raw = Labelled::new("score", 37);
    let scaled = raw.map(double);
    println!("{scaled:?}, rounded {}", scaled.rounded());
    println!("{} = {}", scaled.label, scaled.value);
}

Labelled { label: "score", value: 92.5 }, rounded 93
score = 92.5

Exercise 5: average of a fixed-size array

Write average<const N: usize>(values: &[f64; N]) -> Option<f64> that returns None for an empty array. Try it with four marks, two values and an empty array.

fn average<const N: usize>(values: &[f64; N]) -> Option<f64> {
    if N == 0 {
        return None;
    }
    let mut total = 0.0;
    for v in values {
        total += v;
    }
    Some(total / N as f64)
}

fn main() {
    println!("{:?}", average(&[72.0, 85.5, 90.0, 64.5]));
    println!("{:?}", average(&[10.0, 20.0]));
    println!("{:?}", average(&[]));
}

Some(78.0)
Some(15.0)
None

Exercise 6: a largest that cannot panic

The largest function in this lesson panics on an empty slice. Change it to return Option<&T>.

fn largest<T: PartialOrd>(list: &[T]) -> Option<&T> {
    let mut largest = list.first()?;
    for item in list {
        if item > largest {
            largest = item;
        }
    }
    Some(largest)
}

fn main() {
    println!("{:?}", largest(&[34, 50, 25, 100, 65]));
    println!("{:?}", largest(&["pear", "fig"]));
    let none: [i32; 0] = [];
    println!("{:?}", largest(&none));
}

Some(100)
Some("pear")
None

Interview questions

Q1. What are generics, and why does Rust have them?

Generics let one definition of a function, struct, enum or method work for many types, with the type supplied as a parameter. They remove duplicated code without giving up static type checking. The standard library is built on them: Vec<T>, Option<T>, Result<T, E> and HashMap<K, V> are all generic.

Q2. What is monomorphisation?

It is how Rust compiles generic code: for every concrete set of type arguments actually used, the compiler generates a separate specialised copy of the function or type. A call to largest(&[1, 2]) becomes a direct call to a copy written for i32. The result runs as fast as hand-written code, at the cost of longer compile times and larger binaries.

Q3. What does "zero-cost abstraction" mean for generics?

It means using a generic costs nothing at run time compared with writing the specialised code by hand: no boxing, no dynamic dispatch, no type checks at run time, and the optimiser sees concrete types. It does not mean the feature is free overall, because the cost moves to compile time and code size.

Q4. How do Rust generics differ from Java generics?

Java uses type erasure: the type parameter disappears at run time, one copy of the code runs on Object, and primitives must be boxed. Rust monomorphises: each type gets its own copy, values are stored unboxed, and calls are direct. Rust also checks generic code at its definition against trait bounds, while Java checks against the declared upper bounds in a similar way but cannot specialise the generated code.

Q5. Why does fn largest<T>(list: &[T]) -> &T fail to compile when it uses >?

With no bounds, the compiler may only assume what is true of every type, and not every type can be compared. The > operator comes from the PartialOrd trait, so the error E0369 suggests adding T: PartialOrd. Bounds are both a requirement on callers and a permission for the body.

Q6. What is the difference between impl<T> Point<T> and impl Point<f64>?

The first declares a type parameter and provides methods for every Point<T>. The second is not generic; it adds methods only to Point<f64>, which is useful when the methods need operations specific to that type. Calling such a method on a Point<i32> gives E0599 with a note that the method exists for Point<f64>.

Q7. What is the turbofish, and when do you need it?

The turbofish is the ::<Type> syntax that supplies type arguments explicitly, as in "5".parse::<u8>() or collect::<Vec<_>>(). You need it, or an annotation on the variable, when the compiler cannot infer a type parameter, usually for functions generic over their return type such as parse, collect and into. The error is "type annotations needed".

Q8. Should you put trait bounds on a struct definition?

Usually not. Bounds on the struct must be repeated on every impl block and in every function that mentions the type, even where they are not needed. The common practice, followed by the standard library, is to leave the struct unbounded and put bounds on the impl blocks or methods that actually need the capabilities.

Q9. What are const generics?

Const generics let a type or function be parameterised by a constant value, such as const N: usize, rather than by a type. They let you write one function for arrays of every length ([T; N]) and make sizes part of a type, so mismatches such as adding a 3-element and a 2-element vector are compile errors. On stable Rust, const parameters must be integers, bool or char.

Q10. What are the downsides of generics?

Compile times grow because each instantiation is compiled and optimised separately, and binary size grows with the number of instantiations. Signatures with many parameters and bounds can be harder to read. When those costs matter more than speed, trait objects (dyn Trait) give one shared copy with dynamic dispatch instead.

Q11. Can a method have type parameters that the struct does not have?

Yes. A method can declare its own parameters, as in fn mixup<U>(self, other: Point<U>) -> (T, U) inside impl<T> Point<T>. T is fixed by the value the method is called on, and U is chosen separately at each call.

Key takeaways

• Generics let one definition work for many types; Vec<T>, Option<T> and Result<T, E> are ordinary generic types.
• Declare type parameters in angle brackets: fn f<T>, struct S<T>, enum E<T>, impl<T> S<T>.
• Inside generic code you can use only what the bounds promise; E0369 and E0277 tell you which bound is missing.
• impl Point<f64> adds methods to one concrete instantiation; methods can declare their own extra parameters.
• When inference fails, annotate the variable or use the turbofish, ::<T>.
• Monomorphisation generates a specialised copy per concrete type: no run-time cost, but more compile time and binary size.
• Put bounds on impl blocks and functions, not on struct definitions.
• Const generics such as const N: usize make array lengths part of the type and catch length mismatches at compile time.

Next lesson

Continue with Traits in Rust.